Curriculum Portal

neurologyYou need to know

• An algorithm is a finite, unambiguous sequence of steps that transforms input data into the required output and terminates.
• Algorithm suitability depends on correctness, the characteristics and size of the data set, execution time, memory use and implementation constraints.
• Time complexity describes how the number of operations grows with input size, while space complexity describes how memory requirements grow with input size.
• Empirical efficiency can be measured by timing executions or monitoring memory use, whereas theoretical efficiency is determined by counting key operations as input size grows.
• Big O notation describes an asymptotic upper bound on growth, ignoring constant factors and lower-order terms; for example, 3⁢𝑛2 +2⁢𝑛 +1 is 𝑂⁡(𝑛2).
• Common complexity classes, from generally most to least scalable, are constant 𝑂⁡(1), logarithmic 𝑂⁡(log⁡𝑛), linear 𝑂⁡(𝑛), polynomial such as 𝑂⁡(𝑛2), and exponential such as 𝑂⁡(2𝑛).
• Best-case, average-case and worst-case complexities describe algorithm performance under different arrangements of input data.
• A stack is a last-in, first-out data structure that uses push, pop and peek operations, while a queue is a first-in, first-out data structure that uses enqueue, dequeue and front operations.
• A linked list stores each item in a node containing data and a link to another node; insertion or deletion is 𝑂⁡(1) when the relevant node is already known, but locating a node is normally 𝑂⁡(𝑛).
• Depth-first traversal explores a branch before backtracking and can use recursion or a stack; post-order traversal visits the left subtree, then the right subtree, and then the root.
• Breadth-first traversal visits tree nodes level by level and uses a queue to store nodes that have been discovered but not yet visited.
• Linear search checks items in sequence, works on unsorted data and has worst-case time complexity 𝑂⁡(𝑛).
• Binary search repeatedly halves the remaining search interval, requires sorted data and has worst-case time complexity 𝑂⁡(log⁡𝑛).
• Bubble sort repeatedly compares adjacent items and swaps those in the wrong order; its average and worst-case time complexity is 𝑂⁡(𝑛2), and an optimised version has best-case complexity 𝑂⁡(𝑛).
• Insertion sort builds a sorted section by inserting each new item into its correct position; it has worst-case complexity 𝑂⁡(𝑛2) and best-case complexity 𝑂⁡(𝑛) for already sorted data.
• Merge sort divides data into smaller lists, recursively sorts them and merges them; its time complexity is 𝑂⁡(𝑛⁢log⁡𝑛) and its usual array implementation requires 𝑂⁡(𝑛) auxiliary space.
• Quick sort partitions data around a pivot and recursively sorts the partitions; it has average time complexity 𝑂⁡(𝑛⁢log⁡𝑛) but worst-case complexity 𝑂⁡(𝑛2) when partitions are repeatedly unbalanced.
• Dijkstra's algorithm finds shortest paths from one start node in a weighted graph with non-negative edge weights by repeatedly finalising the unvisited node with the smallest tentative distance.
• The A* algorithm selects nodes using 𝑓⁡(𝑛) =𝑔⁡(𝑛) +ℎ⁡(𝑛), where 𝑔⁡(𝑛) is the known path cost and ℎ⁡(𝑛) estimates the remaining cost to the goal.
• A* is guaranteed to find an optimal path when its heuristic does not overestimate the remaining cost; an informative heuristic can reduce the number of explored nodes compared with an uninformed search.

• Analyse a problem by identifying its inputs, required outputs, processing steps, constraints and relevant edge cases.
• Design an algorithm using precise pseudocode, flowcharts or structured English, ensuring that selection, iteration and data structures are used appropriately and that the algorithm terminates.
• Dry-run an algorithm with a trace table, recording changes to variables and data structures to verify its output and identify logical errors.
• Determine time and space complexity by identifying the dominant operations or memory allocations and expressing their growth using Big O notation.
• Compare algorithms for a task by evaluating correctness, best-, average- and worst-case execution time, auxiliary space and the properties of the data set.
• Perform stack, queue, linked-list and tree operations, including post-order depth-first traversal and breadth-first traversal in the correct visitation order.
• Trace and apply bubble sort, insertion sort, merge sort and quick sort, showing the state of the data after each significant pass, insertion, merge or partition.
• Apply linear search and binary search, updating the search position or interval correctly and recognising that binary search requires sorted data.
• Apply Dijkstra's algorithm by updating tentative distances and predecessors, then reconstruct the shortest path once the destination is finalised.
• Apply A* by calculating 𝑓⁡(𝑛) =𝑔⁡(𝑛) +ℎ⁡(𝑛), selecting the node with the lowest estimated total cost and reconstructing the route from predecessor links.