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 → Flashcards 289
0 / 57 lessons
We'll stop scheduling reviews for after it.

Orientation & the Mathematical Toolkit

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

Analyzing Algorithms: Asymptotics, Invariants, Recurrences

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

Sorting & Selection: Better, Faster, and the Limits

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

Data Structures Supporting Algorithms

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

Dynamic Programming

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

Greedy Algorithms

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

Graph Algorithms I: Search, Order, Connectivity

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

Graph Algorithms II: Spanning Trees, Shortest Paths, Flow

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

Number-Theoretic Algorithms

13 cards
  1. GCD, modular arithmetic & the Euclidean algorithm 12 min ◈ 7
  2. RSA & public-key cryptography 12 min ◈ 6

Intractability: NP-Completeness

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

Coping with Hardness: Approximation Algorithms

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

Capstone: The OilKnapsack DP Project

10 cards
  1. Modeling OilKnapsack as a DP 12 min ◈ 5
  2. Implementing & analyzing OilKnapsack 12 min ◈ 5

Exam War Room: Final Review, Reference Sheets & Mock Exam

40 cards
  1. The one-page reference sheet (memorize cold) 12 min ◈ 4
  2. Problem set: recurrences & asymptotics 12 min ◈ 5
  3. Rapid review: sorting, selection & the lower bound 11 min ◈ 4
  4. DP & greedy problem clinic (design on a novel problem) 13 min ◈ 6
  5. Graph algorithms: the decision guide + worked problems 12 min ◈ 5
  6. NP-completeness & approximation proof drills 12 min ◈ 5
  7. Mock final & how to attack the exam 15 min ◈ 11
NORMAL ~/memra/learn/comp-372 utf-8 LF