University algorithms and data structures: what first-year modules cover

What first-year algorithms modules cover

Most courses mix proofs of correctness, running-time analysis and programming exercises. Your module handbook gives the exact syllabus and whether the exam asks for code, pseudocode or proofs.

The core topics

• Asymptotic analysis: Big O, Big Omega and Big Theta, and solving recurrences such as T(n) = 2T(n/2) + n.
• Sorting: insertion sort, merge sort, quicksort, heapsort, and linear-time sorts such as counting sort.
• Hashing: hash functions, collisions and their resolution, expected constant-time lookups.
• Trees and heaps: binary search trees, balanced trees such as AVL trees, binary heaps and priority queues.
• Graphs: representations, breadth-first and depth-first search, shortest paths, minimum spanning trees.
• Design paradigms: divide and conquer, greedy algorithms, dynamic programming.
• Complexity: P, NP and NP-completeness.

Worked examples

Binary search: why log n matters

A binary search halves the range at every step, so on a sorted list of a million items it needs at most about log₂(1,000,000) ≈ 20 comparisons, against up to a million for a linear search.

Hashing and collisions

With h(k) = k mod 11, the keys 22, 35 and 13 go to buckets 0, 2 and 2. Keys 35 and 13 collide, so the table must resolve it, for example by chaining both in a list at bucket 2 or by probing for the next free slot.

Merge sort's running time

Each level of recursion does about n work in total, and there are about log₂ n levels.

Dijkstra's algorithm

Edges: A to B costs 4, A to C costs 1, C to B costs 2, B to D costs 1 and C to D costs 5. Dijkstra settles A (0), then C (1), then B (via C, 1 + 2 = 3, beating 4), then D (via B, 3 + 1 = 4, beating 1 + 5 = 6). The shortest path from A to D is A, C, B, D with cost 4.

When greedy fails

To make 6 from coins worth 1, 3 and 4, the greedy choice takes 4, then 1 and 1: three coins. Dynamic programming finds the optimum, 3 + 3, with two coins, by building up the best answer for every amount from 1 to 6.

Work out which bucket a key lands in using a hash function in our Search Algorithms course, then press Mark to check your answer in the course:

Use the daily paper as practice

Uni-Sine publishes a free daily University Algorithms & Data Structures paper. It is a short timed practice paper: 8 questions worth 25 to 35 marks, with a suggested 40 to 55 minutes, marked when you finish. It is not your university's exam, so use it alongside your module's problem sheets and past papers.

• What it covers well: asymptotic analysis, hash tables, balanced search trees, heaps and priority queues, divide and conquer, greedy algorithms, dynamic programming, graph algorithms and NP-completeness.
• What it does not cover: programming exercises and proofs of correctness, and topics some courses add, such as maximum flow, bipartite matching and amortised analysis.

Common mistakes in algorithms

• Confusing worst case and average case. Quicksort is O(n log n) on average but O(n²) in the worst case.
• Running Dijkstra with negative edges. Use Bellman-Ford when edge weights can be negative.
• Trusting greedy without a proof. Check for a counterexample, like the coin example above.
• Dropping the base case of a recurrence or DP. Define the smallest cases first.

Read next

Computer Science · CoursesSearch algorithms course: binary search, Big O, BFS and DFSAn interactive search algorithms course in 24 short sections: linear and binary search, Big O notation, hash tables, trees and graphs, and BFS vs DFS.