7.1 Algorithm design and problem-solving

Computational Thinking

1. What is an Algorithm?

An Algorithm is a set of step-by-step instructions used to solve a specific problem or complete a task.

Input ➔ Process ➔ Output

An algorithm must be finite (it must end), unambiguous (clear instructions), and effective (it must actually solve the problem).

2. Key Concepts in Computational Thinking

Abstraction

The process of filtering out unnecessary details and focusing only on the information needed to solve the problem.

Example: A map of a subway doesn't show buildings or trees, only the stations and lines.

Decomposition

Breaking down a complex problem into smaller, more manageable sub-problems that are easier to solve individually.

Example: Breaking the task of "Making a Cake" into "Buying ingredients," "Mixing," and "Baking."

3. The Program Development Life Cycle (PDLC)

Developing software is a structured process. Each stage depends on the completion of the previous one.

Stages of the PDLC
1. Analysis
Understanding the problem. Outcome: Requirements Specification (Input, Process, Output requirements).
2. Design
Planning how the software will look and work. Outcome: Flowcharts, Pseudocode, and Structure Diagrams.
3. Coding
Writing the actual program using a high-level language. Outcome: Source Code.
4. Testing
Running the program to find and fix errors. Outcome: Test Report and Bug-free software.
5. Maintenance
Updating the program over time. Outcome: Updated software and patches.

4. Testing: Ensuring Accuracy

During the testing stage, we use different types of data to see if the program breaks. Here is the Testing Toolkit at a glance:

  • Normal Data: Expected data that should be accepted (e.g., age 25).
  • Abnormal/Erroneous Data: Data of the wrong type or outside limits that should be rejected (e.g., "twenty" or -5).
  • Extreme Data: The largest and smallest values at the very edges of the valid range (e.g., 1 and 100).
  • Boundary Data: Pairs of values at the limit: one just valid (e.g., 100) and one just invalid (e.g., 101).
⚠️ Exam Tip: When asked for the difference between Extreme and Boundary data: Extreme data is valid; Boundary data includes one valid and one invalid value.

Flowchart Symbols

1. Standard Flowchart Symbols

Using the correct shapes is essential for exam marks. Each shape represents a specific type of instruction.

Shape Name Function
START / STOP
 Terminator Used at the very beginning and the end of every flowchart.
X ← A + B
 Process Used for calculations or assigning values to variables.
INPUT / OUTPUT
 Input / Output Used when the program gets data from a user or displays a result.
Decision Used for Selection (IF statements). Has two exit paths: Yes and No.
PRE-DEFINED
 Pre-defined Process Used for Subroutines or Functions defined elsewhere.

2. Example Algorithm: Pass/Fail Checker

Let's represent an algorithm that asks for a student's mark and tells them if they passed (Pass mark = 50).

START
↓
INPUT Mark
↓
Mark ≥ 50?
YES
↓
OUTPUT "Pass"
NO
↓
OUTPUT "Fail"
↓
STOP

3. Drawing Rules

  • Flowcharts should generally flow from top to bottom or left to right.
  • Arrowheads must be used on all lines to show the direction of flow.
  • Decision symbols must have exactly two output lines, clearly labeled (e.g., True/False or Yes/No).
⚠️ Exam Warning: Do not confuse the Process (Rectangle) with the Input/Output (Parallelogram). Marks are frequently lost for using a rectangle when asking for a user's name!

Trace Tables

1. What is a Trace Table?

A Trace Table is a tool used to track the values of variables as an algorithm executes line by line. Its primary purpose is to find Logic Errors that a compiler might miss.

2. Example: Totaling & Counting

Let's trace this pseudocode algorithm which finds the total and count of 3 numbers entered by a user.

Total ← 0
Count ← 0
WHILE Count < 3 DO
  INPUT Num
  Total ← Total + Num
  Count ← Count + 1
ENDWHILE
OUTPUT Total

Trace Table (Test Data: 10, 5, 20)

Total Count Num OUTPUT
0 0
10
10 1
5
15 2
20
35 3
35

3. Rules for Drawing Trace Tables

  • Each row represents a change in a variable's value or an input.
  • Do not repeat values in a row if they haven't changed (leave the cell blank or use a dash).
  • Output only goes in the output column when the program explicitly executes an OUTPUT or PRINT command.
  • Calculations (like Total + Num) are performed first, then the new value is written in the table.

4. Why use Trace Tables?

  • To verify that an algorithm works correctly with Test Data.
  • To identify Infinite Loops (where a variable never meets the exit condition).
  • To find "Off-by-one" errors (e.g., using Count < 3 vs Count <= 3).
⚠️ Exam Warning: When filling out a trace table in an exam, be very careful with Loops. The most common mistake is forgetting to increment the counter or stopping one iteration too early.

Structure Diagrams

1. Top-Down Design

Top-Down Design is the process of breaking a main problem into smaller parts (sub-problems) until each part is simple enough to be solved. A Structure Diagram is the visual tool used to show this hierarchy.

2. Example: Smart Alarm Clock System

Notice how the main system is decomposed into three main modules, which are then broken down further.

Smart Alarm Clock
Set Alarm
Input Time
Check Time
Compare to Current
Trigger Alarm
Sound Buzzer

3. Key Rules for Structure Diagrams

  • Hierarchy: The "Parent" module is at the top; "Children" modules are below.
  • No Logic: Unlike flowcharts, structure diagrams do not show decisions (IF) or loops (WHILE). They only show the components of the system.
  • Modularization: Each box represents a discrete task that could be written as a separate subroutine (function/procedure).

4. Advantages of Modular Design

Easier Debugging: It is easier to find and fix an error in a small module of 10 lines than in a program of 1,000 lines.
Collaboration: Different programmers can work on different modules at the same time.
Reusability: Once a module is written (e.g., a "Calculate Tax" module), it can be used in other programs.
Maintenance: Modules can be updated or replaced individually without breaking the entire system.
⚠️ Exam Tip: If an exam asks you to "Complete a structure diagram," remember to check the levels. Ensure the new module you add is a sub-task of the module directly above it.