Algorithm design and problem-solving

1. Overview

Algorithm design and problem-solving are fundamental to computer science. This topic covers the process of breaking down complex problems into manageable steps, designing solutions using various methods, and testing those solutions to ensure they work correctly. Mastering these skills is crucial for developing effective and efficient computer programs.

Key Definitions

• Algorithm: A step-by-step set of instructions designed to solve a specific problem.
• Program Development Life Cycle (PDLC): The process of creating a computer program, including analysis, design, coding, and testing.
• Decomposition: Breaking down a complex problem into smaller, more manageable sub-problems.
• Structure Diagram: A hierarchical diagram that shows the decomposition of a system into modules and sub-modules.
• Flowchart: A graphical representation of an algorithm using standard symbols to show the flow of control.
• Pseudocode: A structured English-like representation of an algorithm, used for planning before coding.
• Linear Search: A simple search algorithm that checks each element in a list sequentially until the target element is found or the end of the list is reached.
• Bubble Sort: A sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.
• Validation: Checking that data entered is reasonable and sensible.
• Verification: Checking that data was entered correctly.
• Trace Table: A table used to document the execution of an algorithm, showing the values of variables at each step.

Core Content

a) Program Development Life Cycle (PDLC)

The PDLC is an iterative process:

• Analysis:
  • Understanding the problem.
  • Identifying the requirements: what the program needs to do.
  • Defining inputs: what data will the program receive?
  • Defining outputs: what results will the program produce?
  • Determining the necessary processing steps.
• Design:
  • Planning the solution.
  • Using tools like:
    • Flowcharts
    • Pseudocode
    • Structure diagrams
• Coding:
  • Writing the program in a chosen programming language (e.g., Python).
• Testing:
  • Checking if the program works correctly.
  • Using various test data (normal, abnormal, extreme, boundary).
  • Iterative: Finding bugs may require returning to earlier stages.

b) Sub-Systems and Top-Down Design

• Every computer system is composed of sub-systems.
• Each sub-system performs a specific task.
• Top-Down Design: Breaking a large problem into smaller, manageable parts (sub-systems).
  • Benefits:
    • Easier to understand
    • Easier to develop
    • Easier to test
    • Easier to maintain
    • Enables modular programming

c) Problem Decomposition (Inputs, Processes, Outputs, Storage)

• Decomposition: Breaking down a problem into its component parts.
• Inputs: Data that enters the system:
  • Keyboard
  • Sensors
  • Files
• Processes: Operations performed on the data:
  • Calculations
  • Decisions
• Outputs: Results produced by the system:
  • Screen display
  • Printer output
  • Actuators (e.g., controlling a motor)
• Storage: Data that needs to be saved:
  • Variables
  • Files
  • Databases

d) Design Methods (Structure Diagrams, Flowcharts, Pseudocode)

• Structure Diagrams:
  • Hierarchical breakdown of the system.
  • Shows the decomposition into modules.
• Flowcharts:
  • Graphical representation of an algorithm.
  • Symbols:
    • Oval: Start/End
    • Rectangle: Process
    • Diamond: Decision
    • Parallelogram: Input/Output
    • Arrows: Flow of control

• Pseudocode:
  • Structured English describing the algorithm steps.
  • Keywords: IF, THEN, ELSE, WHILE, FOR, REPEAT, UNTIL, INPUT, OUTPUT.

INPUT age
IF age >= 18 THEN
    OUTPUT "Adult"
ELSE
    OUTPUT "Minor"
ENDIF

e) Understanding Algorithms (Purpose and Processes)

• Be able to:
  • Read and understand algorithms in flowchart or pseudocode.
  • State the overall purpose of the algorithm.
  • Describe step-by-step what the algorithm does.
  • Identify variables and their roles.
  • Trace through the algorithm with sample data.

f) Standard Algorithms

---

Linear Search

Problem: You have a list of items and need to find if a specific item exists in the list, and where it is.

Real-world example: Looking for a friend's name in an unsorted contact list by checking each name one by one.

How it works:

1. Start at the first item in the list
2. Check if it matches what you're looking for
3. If yes → you found it! Stop searching
4. If no → move to the next item
5. Repeat until you find it or reach the end of the list

INPUT target
FOR i = 0 TO length(array) - 1
    IF array[i] = target THEN
        OUTPUT "Found at index " + i
        STOP
    ENDIF
ENDFOR
OUTPUT "Not found"

Example: Searching for "7" in [3, 5, 7, 2, 9]

• Check 3 → not 7
• Check 5 → not 7
• Check 7 → Found at index 2!

---

Bubble Sort

Problem: You have a list of items in random order and need to arrange them from smallest to largest (or vice versa).

Real-world example: Sorting a hand of playing cards by swapping adjacent cards until they're in order.

How it works:

1. Compare the first two items. If they're in the wrong order, swap them
2. Move to the next pair and repeat
3. After one pass, the largest item "bubbles up" to the end
4. Repeat the process, but ignore the last item (it's already sorted)
5. Keep going until no swaps are needed

FOR i = 0 TO length(array) - 2
    FOR j = 0 TO length(array) - i - 2
        IF array[j] > array[j+1] THEN
            temp = array[j]
            array[j] = array[j+1]
            array[j+1] = temp
        ENDIF
    ENDFOR
ENDFOR

Example: Sorting [5, 3, 8, 1]

• Pass 1: [3, 5, 1, 8] → 8 bubbles to end
• Pass 2: [3, 1, 5, 8] → 5 in place
• Pass 3: [1, 3, 5, 8] → Done!

---

Totalling (Sum)

Problem: You have a list of numbers and need to add them all together.

Real-world example: Adding up all the prices in a shopping cart to get the total cost.

How it works:

1. Start with a total of 0
2. Go through each number in the list
3. Add each number to the total
4. When finished, output the total

total = 0
FOR i = 0 TO length(array) - 1
    total = total + array[i]
ENDFOR
OUTPUT total

Example: Totalling [10, 25, 15, 30]

• Start: total = 0
• Add 10: total = 10
• Add 25: total = 35
• Add 15: total = 50
• Add 30: total = 80

---

Counting

Problem: You have a list and need to count how many items meet a specific condition.

Real-world example: Counting how many students scored above 50% in a test.

How it works:

1. Start with a count of 0
2. Go through each item in the list
3. If the item meets your condition, add 1 to the count
4. When finished, output the count

count = 0
FOR i = 0 TO length(array) - 1
    IF array[i] > 50 THEN
        count = count + 1
    ENDIF
ENDFOR
OUTPUT count

Example: Counting scores > 50 in [45, 67, 52, 38, 91]

• 45 > 50? No
• 67 > 50? Yes → count = 1
• 52 > 50? Yes → count = 2
• 38 > 50? No
• 91 > 50? Yes → count = 3

---

Finding Maximum

Problem: You have a list of numbers and need to find the largest one.

Real-world example: Finding the highest score in a class.

How it works:

1. Assume the first item is the largest (store it as "maximum")
2. Go through each remaining item
3. If you find something bigger than your current maximum, update it
4. When finished, you have the largest value

maximum = array[0]
FOR i = 1 TO length(array) - 1
    IF array[i] > maximum THEN
        maximum = array[i]
    ENDIF
ENDFOR
OUTPUT maximum

Example: Finding max in [23, 45, 12, 67, 34]

• Start: maximum = 23
• 45 > 23? Yes → maximum = 45
• 12 > 45? No
• 67 > 45? Yes → maximum = 67
• 34 > 67? No → Final answer: 67

---

Finding Minimum

Problem: You have a list of numbers and need to find the smallest one.

Real-world example: Finding the cheapest item in a price list.

How it works:

1. Assume the first item is the smallest (store it as "minimum")
2. Go through each remaining item
3. If you find something smaller than your current minimum, update it
4. When finished, you have the smallest value

minimum = array[0]
FOR i = 1 TO length(array) - 1
    IF array[i] < minimum THEN
        minimum = array[i]
    ENDIF
ENDFOR
OUTPUT minimum

Example: Finding min in [23, 45, 12, 67, 34]

• Start: minimum = 23
• 45 < 23? No
• 12 < 23? Yes → minimum = 12
• 67 < 12? No
• 34 < 12? No → Final answer: 12

---

Calculating Average (Mean)

Problem: You have a list of numbers and need to find their average value.

Real-world example: Calculating the average test score for a class.

How it works:

1. First, add up all the numbers (totalling)
2. Then divide by how many numbers there are
3. The result is the average

total = 0
FOR i = 0 TO length(array) - 1
    total = total + array[i]
ENDFOR
average = total / length(array)
OUTPUT average

Example: Average of [80, 70, 90, 60]

• Total = 80 + 70 + 90 + 60 = 300
• Count = 4 numbers
• Average = 300 ÷ 4 = 75

g) Validation Checks

Check Type	Description	Example
Range Check	Value within an allowed range.	Age between 0 and 120.
Length Check	Correct number of characters.	Password between 8 and 20 characters.
Type Check	Correct data type.	Age is an integer.
Presence Check	Required field is not empty.	Username must be entered.
Format Check	Matches an expected pattern.	Email address format (e.g., [email protected]).
Check Digit	Calculated digit verifies other digits are correct.	ISBN or credit card number.

h) Verification Checks

Check Type	Description
Visual Check	User reviews entered data before submission to confirm it's correct.
Double Entry Check	Data entered twice (by same or different people) and compared for a match.

i) Test Data Types

Data Type	Description	Example (Age: 1-100)
Normal	Typical valid data.	25
Abnormal	Invalid data that should be rejected.	-5, "hello"
Extreme	Valid data at the limits, but not the boundaries.	5, 95
Boundary	Valid data at the exact boundaries.	1, 100

j) Trace Tables

Example: Trace table for summing array [5, 3, 8, 2]

Iteration	i	array[i]	total
Initial	-	-	0
1	0	5	5
2	1	3	8
3	2	8	16
4	3	2	18

The trace table shows how variables change with each step of the algorithm.

k) Identifying and Correcting Errors

• Syntax Errors: Code won't run (typos, missing punctuation).
• Logic Errors: Code runs, but produces the wrong result (wrong formula, incorrect condition).
• Common Errors:
  • Loop runs the wrong number of times.
  • Condition is the wrong way around.
  • Uninitialised variables.
  • Wrong operators.
• Debugging: Use trace tables, test with known data, check conditions.

l) Writing and Amending Algorithms

• Use pseudocode, program code, or flowcharts.
• Include: variable declarations, input/output, conditions, loops as needed.
• Be able to modify existing algorithms to change functionality or fix errors.

Exam Focus

• PDLC: Understand the stages and their importance.
• Design Methods: Be able to create and interpret structure diagrams, flowcharts, and pseudocode. Know the symbols for each.
• Standard Algorithms: Be able to write algorithms for searching, sorting, totalling, counting, finding max/min/average.
• Validation/Verification: Know the different types and when to use them.
• Test Data: Be able to suggest suitable test data (normal, abnormal, extreme, boundary). Explain why each type is important.
• Trace Tables: Be able to complete a trace table accurately.
• Error Identification: Be able to identify and correct errors in algorithms.
• Writing Algorithms: Be able to write complete, working algorithms for given problems.

Common Mistakes to Avoid

• ❌ Missing variable value in trace tables or incorrect array indexing. ✓ Double-check each line of pseudocode and array indexes.
• ❌ Identifying the maximum value instead of the minimum (or vice-versa). ✓ Carefully analyze the problem statement.
• ❌ Using your own variable names instead of those provided in the question. ✓ Adhere strictly to the given variable names.
• ❌ Using incorrect flowchart symbols or omitting arrows. ✓ Memorize the correct symbols and arrow placement and use them correctly.
• ❌ Confusing pre- and post-condition loops, or misinterpreting FOR loops. ✓ Understand the difference between loop types.

Exam Tips

• Read the question carefully and understand the requirements before starting to write any code or pseudocode.
• Use comments in your pseudocode to explain your logic. This can help you get partial credit even if your solution is not perfect.
• When creating flowcharts, use a ruler to draw straight lines and neat shapes.
• Practice completing trace tables to become familiar with how algorithms work.