Algorithms

Searching, sorting and complexity analysis.

Algorithms is taught here in 14 lessons, running from Complexity and Big-O in practice through to Verifying and benchmarking algorithms. Each lesson takes one topic, shows the working code, and links onward to the next, so the course can be read straight through in order.

Lessons

1. Complexity and Big-O in practiceReading growth rates off real loops, measuring instead of guessing, and knowing where Big-O stops predicting runtime.
2. Sorting and searchingWhich comparison sort to reach for, why stability matters, and binary search written so it cannot loop forever.
3. Graph algorithms: BFS, DFS and shortest pathsRepresenting a graph, traversing it breadth-first or depth-first, and choosing between Dijkstra, Bellman-Ford and A*.
4. Recursion, backtracking and divide and conquerDesign a recursion by its base case and its shrinking step, generate subsets and permutations, and prune a search that would otherwise explode.
5. Frequency maps, sets and hashing techniquesCount, deduplicate and group with hash containers, use the two-sum and prefix-sum patterns, and know when sorting beats hashing.
6. Two pointers, sliding window and prefix sumsReplace a nested loop with two indices that only move forward, keep a window under a constraint, and answer range queries in constant time.
7. Trees, traversals and binary search treesImplement the four traversals iteratively and recursively, use BST ordering, and find the lowest common ancestor without extra structure.
8. Heaps, priority queues and top-k problemsKnow the heap operations and their costs, use a bounded heap for top-k, merge sorted streams, and track a running median.
9. Greedy algorithms and intervalsProve a greedy choice with an exchange argument, schedule and merge intervals, build a Huffman code, and recognise when greedy fails.
10. Union-Find and minimum spanning treesImplement disjoint sets with path compression and union by rank, then use them for Kruskal, cycle detection and connectivity queries.
11. Dynamic programming: memoisation to tabulationRecognise overlapping subproblems, write the recurrence, then choose top-down memoisation or a bottom-up table with reduced space.
12. Dynamic programming patterns: knapsack, edit distance, LCSApply the knapsack family, sequence alignment, and interval DP, and reconstruct the actual solution rather than only its cost.
13. String algorithms: matching, hashing and triesMove past naive matching with KMP and rolling hashes, index prefixes with a trie, and know when a suffix structure is warranted.
14. Verifying and benchmarking algorithmsTest against a brute-force oracle, use property-based tests, generate adversarial inputs, and measure runtime without fooling yourself.

More in Computer Science Fundamentals

Data Structures Computer Networks Operating Systems Character Encodings Hashing & Checksums Data Formats Dates & Time Regular Expressions

FAQ