Topics

CGP, PG Online, and more
Amazon amazon.co.uk
Python Books
Beginner to advanced Python
Amazon amazon.co.uk
Raspberry Pi Kits
For programming projects
Amazon amazon.co.uk
Fastmail — Private Email
Privacy-first email with no ads and no tracking
fastmail.com
Dynadot — Domain Registration →
Register or transfer domains with free SSL and affordable pricing
dynadot.com
Zen Internet — UK Broadband →
Award-winning UK broadband with no data caps and great customer service
zen.co.uk
CS Revision Guides
A-Level Revise Aid: This resource is designed to support your revision and may contain errors. If you find a discrepancy with your class teaching, your teacher is correct -- please let us know at alevelrevise@scott.scottrix.co.uk.

Data Structures and Algorithms

Year 1 / ASYear 2 / A-Level All Boards (AQA, Edexcel, OCR, WJEC, CCEA) AQA

A-Level Computer Science revision: Data Structures and Algorithms. Learning objectives, key points, worked examples and practice questions across AQA, Edexcel, OCR, WJEC and CCEA.

Fastmail

📌 Key Points

Key Fact: Arrays: contiguous, O(1) access; Lists: dynamic, O(1) append amortised; Stacks: LIFO, push/pop; Queues: FIFO, enqueue/dequeue
Key Fact: Linked lists: singly/doubly, O(1) insert/delete at known position, O(n) access
Key Fact: Trees: binary, BST (left<root<right), AVL/Red-Black (balanced); traversals: pre/in/post-order, level-order
Key Fact: Graphs: adjacency matrix/list; directed/undirected, weighted/unweighted; BFS/DFS
Key Fact: Hash tables: O(1) average, collisions (chaining, open addressing), load factor
Key Fact: Big-O: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2ⁿ); best/average/worst case
Key Fact: Search: linear O(n), binary O(log n) sorted, hash O(1); Sort: bubble/insertion O(n^2), merge/quick/heap O(n log n)
Key Fact: Recursion: base case, recursive case; Tree traversals; Graph: Dijkstra (shortest path), Prim/Kruskal (MST), Topological sort (DAG)

🎯 Learning Objectives

  • Implement and use arrays, lists, stacks, queues, linked lists, trees, graphs, hash tables
  • Analyse time and space complexity using Big-O notation
  • Implement and trace search algorithms: linear, binary, hash-based
  • Implement and trace sorting algorithms: bubble, insertion, merge, quick, heap
  • Understand recursion and divide-and-conquer; apply to tree/graph traversals
  • Apply algorithms to problems: shortest path (Dijkstra), MST (Prim/Kruskal), topological sort

💡 Worked Example

Exam-Style Question

Question: Trace quicksort on [3, 6, 8, 10, 1, 2, 1] with pivot as first element

Model Answer:

Pivot=3. Partition: [1,2,1] + [3] + [6,8,10]. Recurse left: pivot=1 -> [1] + [1] + [2]. Right: pivot=6 -> [] + [6] + [8,10] -> pivot=8 -> [] + [8] + [10]. Result: [1,1,2,3,6,8,10]

❓ Practice Questions

Questions:

  • Implement stack using list
  • Write binary search recursive
  • Trace merge sort on [38,27,43,3,9,82,10]
  • Implement BFS for shortest path in unweighted graph
  • Design hash function for string keys

🎬 Video Resources

📄 Past Papers & Exam Resources

🔗 Further Reading & Resources