Chapter overview and learning outcomes
This chapter develops the conceptual and practical foundations of data structures and algorithms. It connects theory with implementation, evaluation and responsible computing practice.
- Define and explain the chapter's core concepts and terminology.
- Apply the concepts to structured examples and practical problems.
- Compare alternative methods using correctness and efficiency.
- Identify assumptions, edge cases, limitations and security considerations.
- Communicate solutions using clear diagrams, code or mathematical reasoning.
1. Algorithms and abstract data types
An algorithm is a finite, well-defined procedure for solving a problem. An abstract data type describes the values and operations of a structure without prescribing its implementation. A list, stack, queue, set, map and priority queue are examples. Choosing an appropriate abstraction reduces complexity and allows implementations to change without altering the program's conceptual interface.
Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.
Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.
2. Algorithm correctness and complexity
Correctness asks whether an algorithm produces the required result for every valid input under stated assumptions. A proof may use loop invariants, induction or reasoning about preconditions and postconditions. Complexity estimates resource use as input size grows. Time complexity counts an abstract measure of operations; space complexity considers additional memory. Best, average and worst cases describe different input behaviours.
Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.
Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.
3. Asymptotic notation and Big O
Big O gives an asymptotic upper bound on growth, ignoring constant factors and lower-order terms. Big Omega gives a lower bound; Big Theta gives a tight bound when both apply. Common growth rates include constant, logarithmic, linear, linearithmic, quadratic and exponential. For example, nested loops over n elements often produce O(n²) work, while binary search on sorted data is O(log n).
Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.
Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.
4. Arrays and dynamic arrays
An array stores elements in indexed positions, often contiguously. Index access is typically O(1), while inserting into the middle may require shifting elements and take O(n). Dynamic arrays grow capacity when needed, giving amortised efficient append operations. Bounds checking is essential to avoid invalid access. Arrays are useful when predictable indexing and cache locality are important.
Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.
Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.
5. Linked lists
A linked list stores elements in nodes connected by references. Singly linked nodes point to the next node; doubly linked nodes also point backward. Insertion or removal can be O(1) when the relevant node is already known, but searching by position is O(n). Linked lists use additional memory for references and often have poorer cache locality than arrays.
Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.
Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.
6. Stacks, queues and deques
A stack follows last-in, first-out order, supporting push and pop. It is used in function calls, expression evaluation, undo operations and depth-first search. A queue follows first-in, first-out order, supporting enqueue and dequeue; it is used in scheduling and breadth-first search. A deque supports insertion and removal at both ends.
Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.
Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.
7. Hash tables and maps
A hash table maps keys to array positions using a hash function. Collisions occur when distinct keys map to the same location and may be handled by chaining or open addressing. Expected lookup, insertion and deletion can be O(1) under suitable assumptions, but poor hashing or high load factors degrade performance. Keys should have stable equality and hash behaviour.
Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.
Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.
8. Trees, binary search trees and heaps
Trees represent hierarchical data. In a binary search tree, keys in the left subtree are smaller and keys in the right subtree are larger under the chosen ordering. An unbalanced tree can degrade to O(n); balanced trees maintain logarithmic height. A binary heap supports efficient priority queue operations, with O(log n) insertion and removal of the root.
Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.
Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.
9. Graphs and graph algorithms
Graphs model relationships among entities. Breadth-first search explores by distance in unweighted graphs; depth-first search explores paths deeply before backtracking. Dijkstra's algorithm finds shortest paths from a source when edge weights are non-negative. Minimum spanning tree algorithms such as Kruskal's and Prim's connect all vertices with minimum total edge weight in a connected weighted undirected graph.
Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.
Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.
10. Searching and sorting
Linear search examines elements sequentially and works without ordering. Binary search repeatedly halves a sorted search interval. Sorting algorithms include insertion sort, selection sort, merge sort, quicksort and heap sort. Their time, space, stability and worst-case properties differ. Merge sort guarantees O(n log n) time but uses extra space for arrays; quicksort is often fast in practice but can have quadratic worst-case behaviour without suitable pivot strategy.
Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.
Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.
11. Recursion and algorithm design paradigms
Recursion solves a problem by reducing it to smaller instances, with a base case that stops further calls. Divide and conquer splits a problem, solves subproblems and combines results. Greedy algorithms make locally optimal choices; dynamic programming stores overlapping subproblem results; backtracking explores candidates and abandons paths that cannot lead to a solution. Each strategy requires proof that it is appropriate.
Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.
Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.
Conceptual learning diagram; use alongside the explanations and practical work.
Conceptual learning diagram; use alongside the explanations and practical work.
Conceptual learning diagram; use alongside the explanations and practical work.
Practical laboratory activity
- Write a short problem specification, listing inputs, outputs and constraints.
- Draw a diagram or write pseudocode before implementation.
- Implement a small example in an appropriate language or tool.
- Test normal, boundary and invalid cases; record actual and expected results.
- Explain the design trade-offs and suggest one improvement.
Use authorised software and test environments. Do not run experiments on systems or data without permission.
Worked reasoning and self-check
For every problem, state the assumptions first. Work through a small input manually, record each important state transition and compare the final result with the specification. If the result differs, isolate the smallest failing example and revise the reasoning before changing code. For performance questions, identify the input-size variable and count the dominant operation rather than guessing from execution time alone.
Examination and revision questions
Answer with definitions, explanations, diagrams, calculations or code traces as appropriate. Show working for numerical and algorithmic questions.
Define a data structure.
Show answer guidance
A way of organising data to support particular operations efficiently.
What is Big O notation?
Show answer guidance
An asymptotic upper bound describing how resource use grows with input size.
What is the time complexity of binary search on sorted data?
Show answer guidance
O(log n).
Differentiate stack and queue.
Show answer guidance
A stack is last-in first-out; a queue is first-in first-out.
What is a linked list?
Show answer guidance
A collection of nodes connected by references or pointers.
What is a hash collision?
Show answer guidance
When two distinct keys map to the same hash-table location.
Why can an unbalanced binary search tree be slow?
Show answer guidance
Its height can approach n, making operations O(n) in the worst case.
What is a heap used for?
Show answer guidance
Efficient priority queue operations, especially access to the minimum or maximum element.
Differentiate BFS and DFS.
Show answer guidance
BFS explores breadth-wise by layers; DFS explores paths deeply before backtracking.
What is the worst-case time complexity of merge sort?
Show answer guidance
O(n log n).
What is recursion?
Show answer guidance
A technique in which a function solves a problem by calling itself on smaller instances.
What is dynamic programming?
Show answer guidance
A method that stores solutions to overlapping subproblems to avoid repeated computation.
What is a greedy algorithm?
Show answer guidance
An algorithm that repeatedly makes a locally optimal choice according to a rule.
What is a stable sorting algorithm?
Show answer guidance
A sort that preserves the relative order of equal-key elements.
Why analyse space complexity?
Show answer guidance
To understand memory requirements and whether an algorithm fits resource constraints.
Revision checklist
- Can I define the key terms accurately?
- Can I reproduce and explain the diagrams?
- Can I solve a worked example step by step?
- Can I compare at least two approaches and justify a choice?
- Can I identify edge cases, errors and security risks?
- Can I explain the limits of the model or method?
Further study and references
Consult current university textbooks, peer-reviewed computing research, official language and standards documentation, processor or operating-system manuals, and reputable open educational resources. Check edition, publication date and technical version. Programming language behaviour, security recommendations and software tools evolve; verify details against current official documentation.