Memra
academic · advanced

COMP 372 — Design & Analysis of Algorithms

Implement, run, and analyze the algorithms — exam-ready

A full algorithms course in the CLRS tradition: prove running times with asymptotics and the master theorem, implement and run sorting, dynamic programming, greedy, and graph algorithms in your browser, and master the proof techniques (loop invariants, exchange arguments, NP-completeness reductions) the exam rewards. Includes the OilKnapsack DP capstone.

Start course →
0 / 50 lessons

Orientation & the Mathematical Toolkit

  1. What an algorithm is, and why efficiency matters 10 min
  2. Summations you will reuse forever 11 min
  3. Probability & expectation in one page 9 min

Analyzing Algorithms: Asymptotics, Invariants, Recurrences

  1. Insertion sort & the loop-invariant method 12 min
  2. Asymptotic notation: Θ, O, Ω (and o, ω) 12 min
  3. Merge sort & divide-and-conquer 12 min
  4. Solving recurrences I: recursion-tree & substitution 12 min
  5. Solving recurrences II: the master theorem 12 min

Sorting & Selection: Better, Faster, and the Limits

  1. Heaps & heapsort 12 min
  2. Priority queues 10 min
  3. Quicksort & PARTITION 12 min
  4. Randomized quicksort & expected analysis 11 min
  5. The Ω(n lg n) comparison-sort lower bound 9 min
  6. Sorting in linear time 11 min
  7. Medians & order statistics 12 min

Data Structures Supporting Algorithms

  1. Stacks, queues & linked lists 11 min
  2. Binary search trees 11 min
  3. Balanced trees: the red-black guarantee 8 min
  4. Hash tables & chaining 10 min
  5. Amortized analysis 11 min
  6. Disjoint sets & union-find 12 min

Dynamic Programming

  1. The DP method & rod cutting 12 min
  2. Elements of DP & proving optimal substructure 11 min
  3. Longest common subsequence 11 min
  4. Matrix-chain multiplication 11 min
  5. 0/1 knapsack DP — the OilKnapsack bridge 12 min

Greedy Algorithms

  1. Greedy strategy & activity selection 12 min
  2. When greedy works vs when it fails: knapsack 11 min
  3. Huffman codes 12 min

Graph Algorithms I: Search, Order, Connectivity

  1. Graph representations: lists vs matrices 10 min
  2. Breadth-first search & shortest paths 11 min
  3. Depth-first search & edge classification 12 min
  4. Topological sort & strongly connected components 12 min

Graph Algorithms II: Spanning Trees, Shortest Paths, Flow

  1. Minimum spanning trees & the cut property 11 min
  2. Kruskal's algorithm 11 min
  3. Prim's algorithm 11 min
  4. Shortest paths: the relaxation framework 10 min
  5. Bellman-Ford & DAG shortest paths 12 min
  6. Dijkstra's algorithm 12 min
  7. All-pairs shortest paths: Floyd-Warshall 11 min
  8. Maximum flow (concept + Ford-Fulkerson) 12 min

Number-Theoretic Algorithms

  1. GCD, modular arithmetic & the Euclidean algorithm 12 min
  2. RSA & public-key cryptography 12 min

Intractability: NP-Completeness

  1. P, NP, and verification 11 min
  2. Polynomial-time reductions 11 min
  3. NP-complete problems & how to prove one 12 min

Coping with Hardness: Approximation Algorithms

  1. Approximation ratios & the vertex-cover 2-approximation 12 min
  2. TSP, set cover & the general techniques 12 min

Capstone: The OilKnapsack DP Project

  1. Modeling OilKnapsack as a DP 12 min
  2. Implementing & analyzing OilKnapsack 12 min
NORMAL ~/memra/learn/comp-372 utf-8 LF