Computer Science (9645) | Following and writing algorithms

Welcome to Following and Writing Algorithms!

Hello future programmer! This chapter is absolutely critical because algorithms are the heart and soul of Computer Science. Think of an algorithm as a set of perfect, foolproof instructions. Whether you're making toast or building the next big app, you need clear steps.

In this section, we will learn how to read and follow these instructions, how to translate them into actual programming language, and, most importantly, how to manually check if they work correctly—a skill known as "hand tracing." Even if writing code seems daunting, mastering the logic here will make programming much easier. Let's dive in!

1. Understanding the Algorithm (3.3.3 Content)

Before we can follow instructions, we need to know exactly what those instructions are.

What is an Algorithm?

An algorithm is defined as a sequence of steps that can be followed to complete a task and that always terminates.

• Sequence of steps: The instructions must be ordered logically. Step 2 happens after Step 1.
• Completes a task: It must achieve the intended goal (e.g., sort a list, calculate tax, bake a cake).
• Always terminates: This is crucial! An algorithm must eventually finish. It cannot run forever in an infinite loop.

Analogy: Think of an algorithm like a recipe.
If you follow the recipe step-by-step, you should successfully complete the task (bake the cake), and the process will stop once the cake is ready (it terminates). If the recipe told you to "keep stirring until the cows come home," it wouldn't be an algorithm because it might never terminate!

2. Expressing Algorithms using Pseudocode (3.3.3 Content)

Algorithms are often expressed using pseudocode. Pseudocode is not a real programming language; it's an informal, high-level description of the steps in a program.

It helps programmers design the logic without getting bogged down in the specific syntax rules of languages like Python or Java.

Important Note for Exams: You are expected to be familiar with the use of pseudocode to express algorithms and understand algorithms written in pseudocode. However, you will not be expected to write pseudocode yourself in the exam. This means your focus should be on reading and interpreting it accurately.

Key Pseudocode Structures to Recognise

To understand pseudocode, you must recognize the fundamental control structures:

1. Sequence: Simple step-by-step execution.
Example:

INPUT Number1
INPUT Number2
Total = Number1 + Number2
OUTPUT Total


2. Selection (Decisions): Choosing between paths based on a condition.
Example:

IF Score >= 50 THEN
OUTPUT "Pass"
ELSE
OUTPUT "Fail"
ENDIF


3. Iteration (Loops): Repeating a block of code.

• Definite Iteration (FOR Loop): Used when you know exactly how many times the loop will run.
  Example: FOR Count = 1 TO 10 DO ... ENDFOR
• Indefinite Iteration (WHILE Loop or REPEAT UNTIL): Used when the number of repetitions is unknown, and the loop continues until a certain condition is met.
  Example: WHILE UserInput <> "Stop" DO ... ENDWHILE

Did you know? Many programming languages use slightly different rules for pseudocode. The key is that the *logic* always remains clear, regardless of the exact keywords used.

3. Converting Pseudocode to High-Level Code (3.3.3 Content)

The next major skill is translating the abstract logic expressed in pseudocode into concrete instructions using a specific high-level language (like Python, Java, or C#).

This step requires you to understand the syntax rules of your chosen programming language and map the pseudocode structure to the corresponding code structure.

Step-by-Step Translation Example

Let's convert a simple pseudocode segment that calculates the factorial of a number $N$.

Pseudocode:

Factorial = 1
INPUT N
FOR Count = 1 TO N DO
    Factorial = Factorial * Count
ENDFOR
OUTPUT Factorial

Conversion (Thinking in Python/similar language):

1. Initialization: The pseudocode sets `Factorial = 1`. In code, we assign this value.
2. Input: The pseudocode gets `N`. In code, we use an input function and ensure the variable is an integer.
3. Iteration: The `FOR Count = 1 TO N` loop. In code, this becomes a `for` loop or similar construct (`for i in range(1, N+1):`).
4. Calculation: The core calculation `Factorial = Factorial * Count` remains almost identical.
5. Output: Displaying the result.

Resulting Code Structure (Example using Python concepts):

Factorial = 1
N = int(input("Enter number: ")) # Get input

for Count in range(1, N + 1):
    Factorial = Factorial * Count

print(Factorial)

The challenge is making sure that the specific rules of your chosen language (like Python's zero-indexing or how `range` functions work) correctly mirror the logical intention of the pseudocode.

4. Hand Tracing Algorithms (3.3.3 Content)

Hand tracing is the process of manually simulating the execution of an algorithm, step-by-step, using a specific set of input data. It is essential for finding logical errors (bugs) before running the code on a computer.

To trace an algorithm efficiently, we use a trace table.

The Trace Table: Your Detective Tool

A trace table tracks the value of every relevant variable and the resulting output at each step of the algorithm.

Structure of a Trace Table:

• One column for the Line Number/Step of the algorithm being executed.
• One column for each variable used in the algorithm.
• One column for any Condition Check (e.g., if a WHILE condition is True or False).
• One column for the Output generated by the algorithm.

Encouragement: Don't worry if this seems tricky at first. It just takes practice! Tracing is like learning to read sheet music—you are training your brain to follow the flow perfectly.

Hand Tracing Example Walkthrough

Trace the following pseudocode with the input N = 3.

1. Factorial = 1
2. INPUT N
3. FOR Count = 1 TO N DO
4.     Factorial = Factorial * Count
5. ENDFOR
6. OUTPUT Factorial

Trace Table:

Step	N	Count	Factorial	Output
1	-	-	1
2 (Input 3)	3	-	1
3 (Start loop, Count=1)	3	1	1
4 (1 * 1)	3	1	1
3 (Next iteration, Count=2)	3	2	1
4 (1 * 2)	3	2	2
3 (Next iteration, Count=3)	3	3	2
4 (2 * 3)	3	3	6
3 (Loop finished, Count > N)	3	-	6
6	3	-	6	6

Key Takeaway from Tracing:

The final output is 6 (which is 3 factorial: \(3 \times 2 \times 1\)). By meticulously tracking every change in the Factorial variable, we confirmed the algorithm works as intended for the input N=3.