CS600 - Introduction to Algorithm, at Stevens Insitutue of Technology. Please see the course slides below.
The corresponding textbook is Algorithm Design: Foundations, Analysis, and Internet Examples, by Michael T. Goodrich and Roberto Tamassia.
- Slide 01: Algorithm Analysis;
- Slide 02: Stacks, Queues, Lists and Trees;
- Slide 03: Priority Queues, Heaps, Dictionaries and Hash Tables;
- Slide 04: Search Trees;
- Slide 05: Red-Black Trees;
- Slide 06: Skip Lists;
- Slide 07: Sorting, Sets and Selection;
- Slide 08: Fundamental Techniques;
- Slide 09: Graphs;
- Slide 10: Weighted Graphs;
- Slide 11: Network Flows;
- Slide 12: Text Processing;
- Slide 13: NP Complete;
- Slide 14: Algorithmic Frameworks;
Please check the slides by Kevin Wayne to supplement the textbook Algorithm Design Jon Kl`einberg and and Éva Tardos. For your convenience, the slides have been listed below.
- Slide 01: Stable Matching (Gale–Shapley). See demo Gale–Shapley.
- Slide 02: Algorithm Analysis (big O notation). See demo binary search.
- Slide 03: Graphs (graph search).
- Slide 04: Greedy Algorithms I (basic techniques). See demo interval scheduling and interval partitioning.
- Slide 05: Greedy Algorithms II (shortest paths and MSTs). See demo Dijkstra, Prim, Kruskal, Borůvka, and Edmonds.
- Slide 06: Divide and Conquer I (sorting and selection). See demo merging and quickselect.
- Slide 07: Divide and Conquer II (integer and polynomial multiplication).
- Slide 08: Dynamic Programming I (basic techniques).
- Slide 09: Dynamic Programming II (sequence alignment, Bellman–Ford).
- Slide 10: Network Flow I (maximum flow theory). See demo Ford–Fulkerson.
- Slide 11: Network Flow II (maximum flow applications).
- Slide 12: Network Flow III (assignment problem).
- Slide 13: Intractability I (polynomial-time reductions).
- Slide 14: Intractability II (P, NP, and NP-complete).
- Slide 15: Intractability III (coping with intractability). See demo independent set and vertex cover.
- Slide 16: PSPACE (PSPACE complexity class).
- Slide 17: Limits of Tractability (extending limits of tractability).
- Slide 18: Approximation Algorithms (approximation algorithms). See demo list scheduling.
- Slide 19: Local Search (Metropolis, Hopfield nets).
- Slide 20: Randomized Algorithms (randomized algorithms).
- Slide 21: Data Structures I (amortized analysis). See demo dynamic table.
- Slide 22: Data Structures II (binary and binomial heaps). See demo binary heap and heapify.
- Slide 23: Data Structures III (Fibonacci heaps).
- Slide 24: Data Structures IV (union–find).
- Slide 25: Linear Programming I (simplex algorithm).
- Slide 26: Linear Programming II (linear programming duality).
- Slide 27: Linear Programming III (ellipsoid algorithm).