Memra

academic · advanced · ≈ 9 h · Athabasca University

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.

0 / 57 lessons
Reviews stop being scheduled for after it.

up next

What an algorithm is, and why efficiency matters

10 m

Start course

Orientation & the Mathematical Toolkit

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

Analyzing Algorithms: Asymptotics, Invariants, Recurrences

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

Sorting & Selection: Better, Faster, and the Limits

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

Data Structures Supporting Algorithms

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

Dynamic Programming

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

Greedy Algorithms

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

Graph Algorithms I: Search, Order, Connectivity

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

Graph Algorithms II: Spanning Trees, Shortest Paths, Flow

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

Number-Theoretic Algorithms

0 / 2 lessons
  1. GCD, modular arithmetic & the Euclidean algorithm 12 m
  2. RSA & public-key cryptography 12 m

Intractability: NP-Completeness

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

Coping with Hardness: Approximation Algorithms

0 / 2 lessons
  1. Approximation ratios & the vertex-cover 2-approximation 12 m
  2. TSP, set cover & the general techniques 12 m

Capstone: The OilKnapsack DP Project

0 / 2 lessons
  1. Modeling OilKnapsack as a DP 12 m
  2. Implementing & analyzing OilKnapsack 12 m

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

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