Introduction to Trace Tables and Writing Algorithms

Welcome! In this chapter, we are going to learn the art of "thinking like a computer." Have you ever written a piece of code or a set of instructions, only to find it doesn't work the way you expected? Don't worry—even professional programmers face this! The secret to fixing these problems is Trace Tables and Algorithm Design. We will learn how to track variables as they change and how to write clear, precise instructions that a computer can follow every single time.

Note: This chapter is part of the "Algorithm design and problem-solving" section. For more on how algorithms are planned, see the chapter on the Program Development Life Cycle.

1. Trace Tables: The "Dry Run"

A trace table is a tool used to follow an algorithm's logic manually on paper before you ever type it into a computer. This process is called a dry run. It helps you see exactly what is happening inside the computer’s memory.

What goes into a Trace Table?

In a typical IGCSE exam, your trace table will have columns for:

  • Variables: Every variable in the algorithm (like \( Counter \), \( Total \), or \( Score \)) gets its own column.
  • Outputs: A column to record what is displayed to the user.
  • User Prompts: A column to record any messages asking the user for input.

How to complete a Trace Table step-by-step:

  1. Initialise: Look at the start of the algorithm. If a variable is set to a value (e.g., \( Count \leftarrow 0 \)), write that number in the first row.
  2. Follow the Flow: Move through the algorithm line by line.
  3. Record Changes: ONLY write a new value in a column when that variable changes. If a variable doesn't change on a specific line, leave the cell below it blank or follow the exam's specific layout.
  4. Handle Loops: Each time a loop repeats, you will likely use a new row in your table to show the variables updating.
  5. Output: When you see an instruction like \( OUTPUT \), write the exact text or value in the Output column.

Quick Tip: If the algorithm asks for an input, check the "Test Data" provided in the question. That is the value you should use for your trace!

Key Takeaway: Trace tables are the best way to find logic errors—those pesky mistakes where the code runs but gives the wrong answer.

2. Writing and Amending Algorithms

Writing an algorithm is like writing a recipe. However, computers are not as smart as chefs—they need precision. The syllabus requires you to be exact in your notation.

Pseudocode Standards

When writing algorithms, we use Pseudocode. Here are the rules you must follow:

  • Assignment: Use the arrow \( \leftarrow \) to give a variable a value. Example: \( Price \leftarrow 10.99 \).
  • Keywords: Always use UPPER CASE for keywords like \( IF \), \( THEN \), \( ELSE \), \( FOR \), \( WHILE \), and \( REPEAT \).
  • Indentation: Indent your code (move it to the right) inside loops and \( IF \) statements to show where they start and end.
  • Comparison: Use relational operators like \( > \) (greater than), \( < \) (less than), \( >= \) (greater than or equal to), and \( <> \) (not equal to).

The "Precision" Rule

In the exam, you cannot use plain English for logic.
Wrong: "Check if the score is bigger than ten."
Right: \( IF \ Score > 10 \ THEN \)

Amending Algorithms

Sometimes, a question will give you an existing algorithm and ask you to amend (change) it. This might involve:

  • Changing a \( WHILE \) loop to a \( FOR \) loop.
  • Adding a new Validation Check (like checking if a number is within a range).
  • Adding a Totalling or Counting feature.

Did you know? In the final 15-mark scenario question of Paper 2, you can choose to write your algorithm in Python, Visual Basic, or Java, but for all other questions, Pseudocode is required!

3. Identifying and Correcting Errors

Part of being a great computer scientist is being a "Code Detective." You need to spot where an algorithm has gone wrong.

Common Errors to Look For:

  • Initialization Errors: Variables starting at the wrong number (e.g., a \( Total \) starting at \( 100 \) instead of \( 0 \)).
  • Off-by-one Errors: Using \( < \) when the algorithm should use \( <= \). This often happens in loops, causing them to run one too many or one too few times.
  • Infinite Loops: A loop where the condition never changes to \( FALSE \). For example, \( WHILE \ x < 10 \ DO \), but \( x \) never increases.
  • Wrong Operators: Using \( + \) instead of \( * \) or \( > \) instead of \( < \).

How to fix them: If you find an error, clearly state the line number or the incorrect code, and then write the corrected version using proper pseudocode syntax.

Key Takeaway: Always "dry run" the algorithm in your head with a simple number (like \( 1 \) or \( 0 \)) to see if the logic holds up.

4. Flowcharts: A Visual Algorithm

Algorithms aren't just text; they can be diagrams too! You must use the official standard symbols:

  • Terminator: Oval shape for \( Start \) and \( Stop \).
  • Process: Rectangle for calculations or assignments (e.g., \( x \leftarrow x + 1 \)).
  • Input/Output: Parallelogram for \( INPUT \) and \( OUTPUT \).
  • Decision: Diamond shape for \( IF \) questions. It must have two lines coming out, labeled Yes/No or True/False.
  • Subroutine: A rectangle with double vertical lines for calling separate procedures.

Memory Trick: Think of the Diamond as a Decision. It's the only shape that asks a question!

Quick Review: "Trace Tables & Writing Algorithms"

✓ Trace Tables: Used for dry runs; include variables, outputs, and prompts.

✓ Precision: Use \( \leftarrow \) for assignment and proper relational operators like \( <= \) or \( <> \).

✓ Loop Keywords: \( FOR \ ... \ TO \ ... \ NEXT \), \( WHILE \ ... \ DO \ ... \ ENDWHILE \), and \( REPEAT \ ... \ UNTIL \).

✓ Errors: Look for incorrect starting values, wrong comparison signs, and logic that never ends.

Don't worry if trace tables feel slow at first. They are meant to be slow! Taking your time ensures you don't miss a single change in the variable's value, which is exactly how you get full marks in the exam.