2.1 Algorithm

Decomposition

The process of breaking down a problem into smaller, more manageable sub-problems that each accomplish a specific task.

Abstraction

The process of removing unnecessary details to focus on the essential parts of a problem.

Algorithmic Thinking

The ability to create a clear set of instructions (algorithms) to find the solution to a problem.

Pattern Recognition

The process of identifying similarities or recurring features in problems and solutions.

Inputs

What data the algorithm receives.

Processing

How the data is transformed or calculated during the algorithm.

Outputs

The result or outcome produced by the algorithm, often presented to the user.

Trace Tables

A trace table is used to track the value of variables and how they change as the algorithm runs step by step.

Pseudo-code

A simplified, informal way of describing an algorithm that is closer to human language than programming code, but structured like code.

Program Code

High level programming languages, such as Python.

Flowcharts

Diagrams that use symbols / shapes to represent the steps and decision-making processes of an algorithm.

Line

Used to connect flowchart symbols and determine the flow of the algorithm.

Input / Output

Represented by a parallelogram - used when data is entered or printed out.

Process

Represented by a rectangle - shows an operation being performed, such as a calculation.

Decision

Represented by a diamond - used when a yes/no or True/False question is asked, leading to different paths.

Sub-program

Represented by a rectangle with two vertical lines - refers to a predefined procedure or function.

Terminal (Start / Stop)

Represented by an oval - used at the beginning and end of a flowchart.

Syntax Error

Breaks the rules of the language (won't run) - Example: Missing colon in Python.

Logic Error

Code runs but produces the wrong result (harder to spot).

Searching Algorithms

Step-by-step methods used to find a specific value (target) in a list of data.

Linear Search

Starts at the first item in the list and checks each item one by one until the target is found or the end is reached.

Characteristics of Linear Search

Works on any list - sorted or unsorted; Simple to implement; Slow for large lists.

Binary Search

Can only be used on sorted lists and repeatedly divides the list in half, comparing the middle element to the target.

Characteristics of Binary Search

Much faster than linear search for large, sorted lists; More complex logic to implement; Requires the list to be sorted.

Sorting Algorithms

Methods used to arrange data (usually numbers or strings) into a specific order—typically ascending or descending.

Bubble Sort

A sorting algorithm that repeatedly goes through the list, comparing 2 adjacent items and swapping them if they are in the wrong order, until no swaps are needed.

Characteristics of Bubble Sort

Simple to understand and implement; inefficient for large datasets as it requires multiple passes; takes a long time if the list is in reverse order.

Merge Sort

A divide and conquer algorithm that continuously splits the list in half until each sublist has one item, then merges the sublists back together in the correct order.

Characteristics of Merge Sort

Faster than bubble sort for large datasets; uses more memory due to recursion and temporary lists; more complex to implement.

Insertion Sort

A sorting algorithm that starts at the second item in the list and inserts it into the correct position on its left, continuing with the rest of the items until the list is sorted.

Characteristics of Insertion Sort

Simple to understand and implement; efficient for small-medium sized lists.

Splitting in Merge Sort

In merge sort, the list is continuously split in half until each sublist has one item.

Merging in Merge Sort

In merge sort, sublists are merged back together in the correct order by comparing each element in the sublists.

Insertion in Insertion Sort

In insertion sort, items are inserted into the correct position until the list is sorted.