SAM HARRIS TECH REVISION

OCR GCSE CS - 2.1 Algorithms (Deep Dive)

2.1 Algorithms (OCR J277)

Abstraction: Removing unnecessary details (e.g., in a map, removing trees and house colours to focus on road connections).
Decomposition: Breaking a large task (like making a game) into smaller modules (player movement, graphics, scoring).
Algorithmic Thinking: Creating a logical, step-by-step process to solve a problem that can be repeated by anyone or any computer.

Standard Flowchart Symbols:
- Oval: Terminator (Start/Stop)
- Rectangle: Process (Calculation or assignment)
- Diamond: Decision (Yes/No questions)
- Parallelogram: Input/Output
Trace Tables: Used to record the value of each variable, the output, and the condition of any decision steps as an algorithm runs. Essential for spotting zero errors.
Refining: The process of making an algorithm more efficient or robust (e.g., adding input validation).

Binary Search:
- Requires the list to be sorted.
- Checks the middle item, discards the half that doesn't contain the target, and repeats. Very fast for large lists.
Linear Search:
- Works on unsorted lists.
- Starts at the beginning and checks every item sequentially until the target is found or the end is reached.

Bubble Sort: Steps through the list, compares adjacent items, and swaps them if they are in the wrong order. Requires multiple passes.
Merge Sort: A "divide and conquer" algorithm. Splits the list into individual items, then merges them back together in the correct order. Very efficient but uses more memory.
Insertion Sort: Builds the final sorted list one item at a time by taking each new item and "inserting" it into its correct position among the already-sorted items.