Introduction to Algorithms Revision Notes for OCR A-Level Computer Science

Introduction to Algorithms

Overview

An algorithm is a step-by-step set of instructions designed to perform a task or solve a problem. In Computer Science, algorithms are crucial for automating processes, solving complex problems efficiently, and improving programme performance. Understanding how to design, analyse, and implement algorithms is a core skill.

Algorithm Design

Purpose: To solve a specific problem efficiently and logically.
Approach:
- Understand the problem: Break it down into smaller components.
- Choose an approach: This could be iterative, recursive, or a combination.
- Design steps: Outline a clear sequence of operations to achieve the goal.

Algorithm Representation

Algorithms can be represented in various forms, such as:

Flowcharts:

A visual representation of an algorithm using symbols such as:

Oval: Start/End
Rectangle: Process (e.g., calculations)
Diamond: Decision (e.g., IF statements)
Arrow: Flow of control

lightbulbExample

Example:

[Start] --> [Input x] --> [Is x > 10?] -- Yes --> [Print "x is large"] --> [End]
                              |
                             No
                              |
                           [Print "x is small"] --> [End]

Pseudocode:

A high-level, structured, human-readable description of an algorithm.

lightbulbExample

Example:

BEGIN
   INPUT x
   IF x > 10 THEN
      OUTPUT "x is large"
   ELSE
      OUTPUT "x is small"
   ENDIF
END

Program Code:

Written in a specific programming language (e.g., Python). While you are not expected to write perfect syntax, you must demonstrate logical structures.

lightbulbExample

Example (Python-like syntax):

x = int(input("Enter a number: "))
if x > 10:
    print("x is large")
else:
    print("x is small")

Analysing Algorithms

Efficiency: How well an algorithm performs regarding time (speed) and space (memory).
Correctness: Ensures the algorithm provides the expected result for all valid inputs.

Algorithm Structures and Techniques

Iteration (Loops): Repeating steps (e.g., FOR, WHILE loops).
Selection (Decision-Making): Using conditions (e.g., IF, ELSE statements).
Variables and Data Input/Output: Handling user input and displaying results.

Examples

lightbulbExample

Example 1: Finding the Largest Number in a List Pseudocode:

BEGIN
   largest ← list[0]
   FOR each number in list
      IF number > largest THEN
         largest ← number
      ENDIF
   ENDFOR
   OUTPUT largest
END

Flowchart:

Start
Initialise largest to the first element.
Loop through the list.
Compare the current element with largest.
Update largest if the current element is larger.
End loop and output largest.

lightbulbExample

Example 2: Calculating the Factorial of a Number Pseudocode:

BEGIN
   factorial ← 1
   FOR i ← 1 TO n
      factorial ← factorial * i
   ENDFOR
   OUTPUT factorial
END

Note Summary

infoNote

Common Mistakes

Incorrect Logic in Conditions:

Using = instead of == in comparisons.
Misplacing ELSE clauses leads to incorrect outcomes.

Loop Errors:

Forgetting to update loop variables, causing infinite loops.
Off-by-one errors (e.g., iterating one too many or too few times).

Misunderstanding Data Flow in Flowcharts:

Incorrectly placing decision or process symbols.
Forgetting to connect steps with arrows.

Incomplete Pseudocode:

Missing essential steps (e.g., initialisation or output).
Not using clear, consistent structures.

infoNote

Key Takeaways

Algorithms are essential for solving problems systematically.
Common representations include flowcharts, pseudocode, and programme code.
Focus on logical structures like iteration and selection.
Analyse algorithms for efficiency and correctness.
Practice avoids common mistakes, especially in loops and conditions.

Introduction to Algorithms (OCR A-Level Computer Science): Revision Notes