Algorithms
Sorting, searching, recursion, graph algorithms, dynamic programming, greedy strategies, string matching, and the limits of efficient computation — reasoning rigorously about correctness and efficiency, in C.
Algorithmic thinking is the skill of reasoning rigorously about how long a program will take, why it produces a correct answer, and how to make it faster — and recognizing when “faster” stops being possible at all. This course moves from measuring complexity through recursion, sorting, searching, dynamic programming, greedy design, graph algorithms, and string matching, to NP-completeness — building, chapter by chapter, both a working toolkit of algorithms implemented in C and the proof techniques (loop invariants, exchange arguments, reductions) that let you trust them.
Outcomes
- Apply asymptotic analysis, including amortized and average-case reasoning, to compare the efficiency of algorithms
- Design solutions using divide-and-conquer, greedy strategies, and dynamic programming, and prove when each is the right tool
- Prove algorithm correctness rigorously using loop invariants and exchange arguments
- Implement canonical sorting, searching, graph, and string-matching algorithms in C
- Recognise NP-complete problems and choose a sound engineering response: approximation, restriction, pruning, or pseudo-polynomial techniques
Outline
Start →- 01Complexity AnalysisBig-O notation, best/worst/average cases, and comparing algorithms analytically.
- 02Sorting AlgorithmsBubble, insertion, merge, quick, and heap sort, the comparison-sort lower bound, and counting/radix sort: implementation, correctness, and complexity.
- 03Search AlgorithmsLinear and binary search, a rigorous proof of the O(log n) bound, search variants, and interpolation search as a case study in exploiting data distribution.
- 04Recursion and Divide and ConquerRecursive thinking, the call stack, recurrence relations, divide-and-conquer design, and backtracking.
- 05Dynamic ProgrammingMemoization and tabulation for overlapping sub-problems: from Fibonacci to the 0-1 knapsack, longest common subsequence, and Kadane's algorithm.
- 06Greedy AlgorithmsMaking locally optimal choices and proving when that's enough: activity selection, fractional knapsack, Huffman coding, and the exchange-argument proof technique.
- 07Graph AlgorithmsRepresenting networks, breadth- and depth-first traversal, topological sorting, shortest paths with Dijkstra, and minimum spanning trees with Kruskal's algorithm.
- 08String MatchingFinding patterns in text efficiently: brute-force search, Rabin-Karp's rolling hash, and the Knuth-Morris-Pratt algorithm's failure function.
- 09NP-CompletenessP versus NP, polynomial-time verification, reductions, the Cook-Levin theorem, a gallery of NP-complete problems, and how to respond when you meet one.