IGCSE Computer Science - Algorithm Design and Problem-Solving

Objective: Write and amend algorithms using pseudo-code, program code and flowcharts

1. Introduction to Algorithms

An algorithm is a finite sequence of well-defined, ordered steps that, when executed, solves a specific problem or achieves a particular task. Algorithms are fundamental to computer science and are used in everything from simple calculations to complex artificial intelligence.

Key characteristics of an algorithm:

• Finite: It must terminate after a finite number of steps.
• Definite: Each step must be precisely defined and unambiguous.
• Effective: Each step must be feasible and can be carried out in a practical amount of time.

2. Pseudo-code

Pseudo-code is an informal way of describing an algorithm. It uses a combination of natural language and mathematical-like notation to outline the steps involved. It's easier to understand than actual program code but more structured than plain English.

Common Pseudo-code constructs:

• Assignment: `x = 10`
• Conditional statement: IF (condition) THEN [statements] ELSE [statements] ENDIF
• Looping: WHILE (condition) DO [statements] ENDWHILE, FOR i = start TO end DO [statements] STEP increment ENDFOR
• Function Call: FUNCTION function_name(parameters) [statements] RETURN value ENDFUNCTION

3. Flowcharts

Flowcharts are visual representations of algorithms, using standardized symbols to illustrate the flow of control. They provide a clear and easy-to-understand overview of the algorithm's logic.

Common flowchart symbols:

Symbol	Description
	Represents the start and end of the algorithm.
	Represents a process or operation.
	Represents a decision point (e.g., a condition).
	Represents input or output operations.
	Represents the direction of flow.

4. Example Algorithm: Finding the Maximum of Two Numbers

4.1 Pseudo-code

START
  INPUT number1
  INPUT number2
  IF number1 > number2 THEN
    maximum = number1
  ELSE
    maximum = number2
  ENDIF
  OUTPUT maximum
END

4.2 Flowchart

4.3 Program Code (Python)

def find_maximum(num1, num2):
  if num1 > num2:
    return num1
  else:
    return num2

number1 = float(input("Enter the first number: "))
number2 = float(input("Enter the second number: "))

maximum_number = find_maximum(number1, number2)
print("The maximum number is:", maximum_number)

5. Algorithm Amendment

Amending an algorithm involves modifying it to correct errors, improve efficiency, or add new features. This often requires careful analysis of the original algorithm and a systematic approach to making changes.

Common amendment techniques:

• Error Correction: Fixing logical errors in the algorithm.
• Efficiency Improvement: Reducing the number of steps or the time complexity of the algorithm.
• Adding Features: Incorporating new functionalities into the algorithm.

Example: Consider the previous maximum-finding algorithm. We could amend it to handle negative numbers more robustly.

5.1 Amended Pseudo-code

START
  INPUT number1
  INPUT number2
  IF number1 > number2 THEN
    maximum = number1
  ELSE
    maximum = number2
  ENDIF
  OUTPUT maximum
END

In this case, the original algorithm already handles negative numbers correctly, so no amendment is needed. However, if we wanted to add a check for invalid input (e.g., non-numeric input), we would add a conditional statement to handle that.

6. Algorithm Complexity

Algorithm complexity describes how the execution time or memory usage of an algorithm grows as the input size increases. Common notations include Big O notation.

Examples:

• O(1): Constant time - execution time is independent of input size.
• O(n): Linear time - execution time grows linearly with input size.
• O(log n): Logarithmic time - execution time grows logarithmically with input size.

7. Practice Problems

Consider the following problem: Write an algorithm to calculate the area of a triangle, given its base and height.

Try to:

• Write pseudo-code for the algorithm.
• Create a flowchart to represent the algorithm.
• Write program code (in any language you are familiar with) to implement the algorithm.