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 recognising 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 the theory of 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 →- 01 Complexity Analysis Big-O notation, best/worst/average cases, and comparing algorithms analytically.
- 02 Sorting Algorithms Bubble, insertion, merge, quick, and heap sort, the comparison-sort lower bound, and counting/radix sort: implementation, correctness, and complexity.
- 03 Search Algorithms Linear 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.
- 04 Recursion and Divide and Conquer Recursive thinking, the call stack, recurrence relations, divide-and-conquer design, and backtracking.
- 05 Dynamic Programming Memoisation and tabulation for overlapping sub-problems: from Fibonacci to the 0-1 knapsack, longest common subsequence, and Kadane's algorithm.
- 06 Greedy Algorithms Making locally optimal choices and proving when that's enough: activity selection, fractional knapsack, Huffman coding, and the exchange-argument proof technique.
- 07 Graph Algorithms Representing networks, breadth- and depth-first traversal, topological sorting, shortest paths with Dijkstra, and minimum spanning trees with Kruskal's algorithm.
- 08 String Matching Finding patterns in text efficiently: brute-force search, Rabin-Karp's rolling hash, and the Knuth-Morris-Pratt algorithm's failure function.
- 09 NP-Completeness P versus NP, polynomial-time verification, reductions, the Cook-Levin theorem, a gallery of NP-complete problems, and how to respond when you meet one.