Decades of teaching algorithms in the old format made us realise that a new, gentler approach is needed that considers the challenges related to training students from much more diverse backgrounds than 20 years ago. This book attempts to address the difficulties students face when learning algorithms. [PREFACE (PDF)]
The plan and the prerequisites
Asymptotic worst-case analysis
O, Ω, Θ notation
Algorithms for binary arithmetic
Modelling problems using graphs
Graph representation
Simple graph problems
Reachability
Algorithmic mining
Augmented DFS with pre/post numbers
Cycles and DAGs
Connectivity in directed graphs
Shortest Path
Breadth First Search (BFS)
Extending BFS for weighted graphs
Priority queue implementations
Case studies
Maximum Bandwidth Path (MBP)
Travel agent problems
The cookie monster problem
The event scheduling problem
Modify The Solution ("all's well that begins well")
Greedy stays ahead
Greedy achieves the bound
Minimum Spanning Tree (MST)
Implementation of DSDS
Disjoint forest with path compression
Huffman coding
Integer multiplication
Karatsuba's algorithm
Master theorem
Toom-Cook extensions
Divide and conquer on trees
Divide and conquer in computational geometry
Divide and conquer on arrays
Fast Fourier Transform (FFT)
Backtracking
Dynamic Programming
Dynamic Programming and DAGs
Longest Common Subsequence (LCS)
RNA secondary structure
0-1 Knapsack
All Pairs Shortest Path (APSP)
Travelling Salesperson (TSP)
Maximum matching
Perfect matching
Bipartite MIS
Feasible circulation
Edge-disjoint paths
Image segmentation
Team elimination
Polynomial time reduction
Web of reductions
P, NP, NP-complete, NP-hard
Beyond worst case
Heuristica
Proofs
Algorithmic experiments