Chapter: Algorithm Design - Your Guide to Problem Solving!

Hey everyone! Welcome to one of the most important topics in ICT: Algorithm Design. Don't let the fancy name scare you. If you've ever followed a recipe to cook, or given a friend directions, you've used an algorithm!

In this chapter, we're going to learn how to think like a computer scientist. We'll break down problems into simple, logical steps that a computer can understand. This skill is super useful, not just for coding, but for solving all kinds of problems in life. Ready to become a master problem-solver? Let's get started!

What Exactly is an Algorithm?

An algorithm is a finite, step-by-step set of instructions designed to solve a specific problem or perform a task. Think of it as a perfect recipe.

Analogy: Baking a Cake
Imagine you have a recipe for a chocolate cake.

  • The Problem: You want a delicious chocolate cake.
  • The Inputs: Ingredients like flour, sugar, eggs, and cocoa powder.
  • The Algorithm: The recipe's step-by-step instructions (1. Preheat the oven. 2. Mix flour and sugar. 3. Add eggs... etc.).
  • The Output: The finished chocolate cake!

A good algorithm, like a good recipe, must be clear, precise, and have a definite end. You can't have a step that says "add some sugar" – it needs to be "add 200g of sugar".

Key Takeaway

An algorithm is simply a clear plan or a set of rules to solve a problem. It's the 'how-to' guide we write before we start coding.

Representing Algorithms: The Blueprints of Code

Before building a house, an architect draws a blueprint. Similarly, before we write a program, we create a plan. We'll learn two main ways to do this: Pseudocode and Flowcharts.

1. Pseudocode

Pseudocode means "fake code". It's a way of writing out your algorithm using a mix of plain English and programming-like statements. There are no strict rules, so you can focus on the logic without worrying about perfect syntax.

Example: An algorithm to find the average of two numbers.

INPUT Number1
INPUT Number2
Sum = Number1 + Number2
Average = Sum / 2
OUTPUT Average

See? It's simple, readable, and clearly shows the steps.

2. Program Flowcharts

A flowchart is a graphical representation of an algorithm. It uses standard symbols connected by arrows to show the flow of logic. It's great for visualizing the process.

Common Flowchart Symbols:
  • Terminal (Oval): Used for the 'Start' and 'End' points of the algorithm.
  • Input/Output (Parallelogram): Used for getting input from a user or displaying output.
  • Process (Rectangle): Used for any calculation or operation, like addition or assignment.
  • Decision (Diamond): Used for asking a question (usually with a 'Yes' or 'No' answer). This is where the algorithm branches.
  • Flow Lines (Arrows): Connect the symbols and show the direction of the flow.

Example: The same "average of two numbers" algorithm as a flowchart.

(Start) --> [Input Number1] --> [Input Number2] --> [Sum = Number1 + Number2] --> [Average = Sum / 2] --> [Output Average] --> (End)
(Imagine these are the correct shapes connected by arrows!)

Quick Review Box

Pseudocode: Writing it out in simple, structured English.
Flowchart: Drawing it out using standard symbols.

The Building Blocks: Data Types & Structures

To solve problems, we need to work with data. But computers need to know what kind of data they are dealing with. Is it a number? A word? A true/false value? This is where data types come in.

Simple Data Types

The syllabus requires us to know four simple types:

  • Integer: Whole numbers, positive or negative, with no decimal point. Examples: 10, -45, 0, 12345.
  • Real: Numbers that have a decimal point. Examples: 99.9, 3.14, -0.05.
  • Character: A single letter, digit, or symbol enclosed in single quotes. Examples: 'A', 'h', '7', '$'.
  • Boolean: Represents a truth value. It can only be one of two things: True or False. Think of it as a light switch that is either ON or OFF.

Boolean Logic (The Power of True/False)

We can combine Boolean values using logical operators. The three you need to know are AND, OR, and NOT.

  • AND: The result is True only if both conditions are True.
    Example: "You get dessert if you finish your vegetables AND clean your room." (You must do both!)
  • OR: The result is True if at least one of the conditions is True.
    Example: "I will be happy if I get an A OR a B in the exam." (Either one is good enough!)
  • NOT: Reverses the truth value. NOT True becomes False, and NOT False becomes True.
    Example: If 'isRaining' is True, then 'NOT isRaining' is False.

We often use truth tables to see all possible outcomes:

Truth Table for AND

A AND B is True?

A=True, B=True --> True
A=True, B=False --> False
A=False, B=True --> False
A=False, B=False --> False

Truth Table for OR

A OR B is True?

A=True, B=True --> True
A=True, B=False --> True
A=False, B=True --> True
A=False, B=False --> False

Simple Data Structures

Sometimes we need to group data together. That's what data structures are for.

  • String: A sequence of characters. Basically, any text, word, or sentence.
    Examples: "Hello World", "HKDSE ICT", "Student123".
  • One-Dimensional Array: A list of items that are all of the same data type. Think of it like a numbered list of lockers or an egg carton. Each item has a position (called an index), which usually starts from 0.
    Example: An array called `scores` to hold 3 test results: `[95, 88, 72]`. Here, `scores[0]` is 95, `scores[1]` is 88, and so on.
Key Takeaway

Choosing the right data type (Integer, Real, etc.) and structure (like an Array) is a crucial first step in designing a good algorithm.

Controlling the Flow: The Three Basic Structures

Amazingly, any algorithm, no matter how complex, can be built using just three basic control structures. Let's master them!

Did you know? This concept is part of the "structured program theorem," a fundamental principle in computer science which proves that these three structures are all you need to solve any computable problem!

1. Sequence

This is the most straightforward structure. Instructions are executed one after another, in the order they are written. No steps are skipped, and there are no branches.
Our "average of two numbers" algorithm was a perfect example of a sequence.

2. Selection

This is about making choices. The algorithm follows different paths based on whether a condition is true or false. This is done using IF-THEN-ELSE logic.

  • Binary Selection (IF-ELSE): There is one condition and two possible paths.
    Example Pseudocode:
    INPUT score
    IF score >= 50 THEN
        OUTPUT "Pass"
    ELSE
        OUTPUT "Fail"
    ENDIF
  • Multi-way Selection: Used when there are more than two possible paths. You can do this with multiple IF-ELSEIF statements.
    Example Pseudocode:
    INPUT score
    IF score >= 80 THEN
        OUTPUT "Grade A"
    ELSEIF score >= 60 THEN
        OUTPUT "Grade B"
    ELSE
        OUTPUT "Grade C"
    ENDIF

3. Iteration (Loops)

This is for repeating a set of instructions multiple times. This is also called looping.
Analogy: Imagine you have to wash 10 dishes. You repeat the same process (scrub, rinse) for each dish. That's a loop!

Example Pseudocode: A loop to print the numbers from 1 to 5.
FOR counter FROM 1 TO 5
    OUTPUT counter
ENDFOR
This would output: 1, 2, 3, 4, 5.

Key Takeaway

Every algorithm is a mix of Sequence (doing things in order), Selection (making choices), and Iteration (repeating things).

Testing Your Algorithm: Will It Work?

Creating an algorithm is great, but how do we know it's correct? We need to test it! We don't just hope for the best; we actively try to find mistakes.

Dry Runs and Trace Tables

A dry run is the process of manually stepping through your algorithm with a set of test data, pretending you are the computer. The best way to organize a dry run is with a trace table.

A trace table is a table that tracks the value of each variable in your algorithm at each step. This is the single most powerful tool for finding logic errors!

Step-by-Step Example: Using a Trace Table

Algorithm Purpose: Find the largest number in a list. The list is `[5, 8, 3]`.

Pseudocode:
1. numbers = [5, 8, 3]
2. largest = numbers[0]
3. FOR i FROM 1 TO 2
4.     IF numbers[i] > largest THEN
5.         largest = numbers[i]
6.     ENDIF
7. ENDFOR
8. OUTPUT largest

Trace Table:
| Step | i | numbers[i] | Condition: numbers[i] > largest | largest | | :--- | :-: | :---: | :---: | :---: | | 1-2 | - | - | - | 5 | | 3 | 1 | 8 | 8 > 5 is True | 5 | | 4-5 | 1 | 8 | True | 8 | | 3 | 2 | 3 | 3 > 8 is False | 8 | | 4 | 2 | 3 | False | 8 | | 7 | - | - | - | 8 | | 8 | - | - | - | Output: 8 |

By tracing the values, we can see exactly how `largest` changes from 5 to 8, and we can confirm the final output is correct.

Finding Logic Errors

A logic error is a mistake in the algorithm's design that causes it to produce an incorrect result, even though the program may run without crashing.
Example: If we had written `numbers[i] < largest` in our condition, the trace table would have shown us that the algorithm was finding the smallest number, not the largest.

Common Mistake to Avoid

Be careful with loop counters and array indices! A common error is the "off-by-one" error, where a loop runs one too many or one too few times. A trace table is perfect for catching this!

Building Big: The Power of Modularity

What if you have a really big, complex problem, like building a whole app? Trying to write it all as one giant algorithm would be a nightmare!

The solution is modularity. This means breaking down a large problem into smaller, simpler, more manageable sub-problems called modules.

Analogy: Building a Car
You don't build a car all at once. You have separate teams for the engine, the body, the wheels, and the electronics. Each part is a module. They are built and tested separately, then put together at the end.

Advantages of Modularity:
  • Easier to Understand: Small modules are easier to read and manage than one huge block of code.
  • Easier to Test and Debug: You can test each module individually to make sure it works perfectly before combining it with others.
  • Reusable: You can often reuse a module (like a module for calculating tax) in many different programs.
  • Teamwork: Different programmers can work on different modules at the same time.
Key Takeaway

For any complex problem, always think: "How can I break this down into smaller pieces?" This modular approach is key to successful problem-solving.