Algorithms
Learn the standard algorithms in C and how to tell which is faster before running them: searching, sorting, backtracking, greedy methods, dynamic programming, graphs, strings and bits.
- Level
- Intermediate
- Time
- About 54 hours
- Modules
- 6
- Lessons
- 18
- Exercises
- 57
An algorithm is a precise list of steps for solving a problem, and usually several different ones solve the same problem at very different speeds. This course teaches the standard algorithms in C, and how to count their cost by reading the code, so you can choose a good method before you have a million items to test it on.
You start with counting steps and binary search, then write the main sorting algorithms. After that come the big design ideas: backtracking, greedy choices, dynamic programming and divide and conquer. The rest of the course covers graph algorithms, number algorithms, string matching, grid search and bit manipulation. You can step through every example and watch the variables change, and each exercise is checked against hidden tests. Every reference solution also compiles cleanly with a real C compiler.
What you will learn
- Work out the Big-O of an algorithm by reading its code
- Write binary search and the main sorting algorithms correctly
- Solve problems with backtracking, greedy methods and dynamic programming
- Find orderings, shortest paths and spanning trees in graphs
- Analyse recursive algorithms with recurrences and the master theorem
- Search strings and grids efficiently, and use bit operations
Skills you will gain
- Counting steps and comparing growth rates
- Choosing a design technique that fits a problem
- Stating and keeping loop invariants
- Finding counter-examples to wrong ideas
- Testing with edge cases and small inputs traced by hand
Before you start
- The C course, including arrays, functions, structs and recursion
- The Data Structures course, especially stacks, queues, heaps and graphs
- School-level arithmetic, including powers and logarithms
Where it is used
- Technical interviews and programming contests
- Search engines, databases and routing systems
- Compilers, build tools and schedulers
- Security software and data compression
Modules
Module 1: Analysis and searching
How to count the cost of an algorithm by reading its loops, and how binary search finds an item in a sorted array in about log₂ n steps.
Module 2: Sorting
The simple O(n²) sorts, then merge sort, quick sort and heap sort, and counting sort, which avoids comparing items altogether. You compare them on time, memory and stability.
- 1
Bubble, selection and insertion sort
Three O(n²) sorts, step by step: swapping neighbours, picking the minimum, and inserting into a sorted part.
- 2
Merge sort
Divide and conquer: split the array in half, sort each half recursively, and merge two sorted halves in O(n).
- 3
Quick sort
Partition around a pivot, sort each side recursively; O(n log n) on average, O(n²) when the pivots are bad.
- 4
Heap sort and counting sort
Heap sort: O(n log n) in place. Counting sort: O(n + k) without comparing, and why comparison sorts cannot beat n log n.
Module 3: Backtracking, greedy and dynamic programming
Three ways of attacking a problem: try every choice with undo, commit to the best-looking choice, or store the answers to smaller problems so that nothing is solved twice.
- 1
Recursion and backtracking
Try every choice, undo it, try the next: all subsets, all permutations, and placing queens that never attack.
- 2
Greedy algorithms
Take the best-looking choice at each step: activity selection works, coin change sometimes fails, and how to tell.
- 3
Dynamic programming
Solve each subproblem once and store it: Fibonacci with a memo, and the fewest coins for any amount.
- 4
Knapsack and longest common subsequence
Two classic 2D tables: the 0/1 knapsack (take or leave each item) and the LCS of two strings.
Module 4: Graph algorithms
Putting tasks in a valid order, finding shortest paths with and without negative edges, and connecting every vertex as cheaply as possible.
- 1
Topological sort
Order the tasks of a directed acyclic graph so every task comes after the ones it depends on, with Kahn's algorithm.
- 2
Shortest paths: Dijkstra and Floyd–Warshall
The cheapest route on a weighted graph: Dijkstra from one start vertex, Floyd–Warshall between every pair.
- 3
Minimum spanning trees
Join every vertex at the smallest total cost: Kruskal with union-find, and Prim growing one tree.
Module 5: Numbers and recurrences
Fast algorithms for GCDs, primes and huge powers, then divide and conquer in general, with the master theorem for working out how fast a recursive method is.
- 1
Number algorithms
Euclid's GCD, the sieve of Eratosthenes, and fast modular exponentiation: three old ideas used in every contest.
- 2
Divide and conquer and the master theorem Intermediate
Split a problem into smaller copies of itself, solve them recursively, combine the answers, and work out the running time with the master theorem.
Module 6: Strings, grids and bits
Finding a pattern in a text without repeating work, finding routes across a grid with breadth-first search and A*, and working directly on the bits of a number.
- 1
String matching: naive search and KMP Advanced
Find every place a pattern appears in a text: the simple O(n·m) method, and Knuth–Morris–Pratt, which never moves backwards in the text.
- 2
Searching grids: BFS and A* Advanced
Treat a grid as a graph to find shortest paths through mazes and maps with BFS, then reach the goal faster with A*'s distance guess.
- 3
Bit manipulation Intermediate
Use AND, OR, XOR and shifts to test, set and clear single bits, list every subset, and solve classic problems with no extra memory.
Projects
- A sorting laboratory Build a program that runs several sorting algorithms on the same data and reports exactly how much work each one did.
- A delivery planner Build a program that plans a day's deliveries: which parcels to load on a van with a weight limit, and the cheapest route to each customer.
What to learn next
- Coding Interview Prep How coding interviews work, and the patterns behind most questions: hashing, two pointers, sliding windows, stacks, binary search, lists, trees, graphs, DP and backtracking.
- Competitive Programming Online judges and time limits, prefix sums, two pointers, binary search on the answer, greedy, DP and graphs with the STL, and contest math.
- Object-Oriented Programming in C++ Classes, constructors and destructors, operators, inheritance, virtual functions, templates, the STL and exceptions, with every object on screen.