Greedy Algorithms I

Week 01

We introduce the paradigm of greedy algorithms with some examples.

Activity SchedulingIslands War

Greedy Algorithms II

Week 02

We introduced the theory of matroids through several examples and explored why the greedy algorithm works for finding the min/max weight basis in a matroid.

Matroids

Minimum Spanning Trees

Week 03

We introduced the Union Find data structure to appreciate how Kruskal's algorithm can be efficiently implemented.

DSU

Shortest Paths I

Week 04

In this week we wrap up our discussion on the DSU data structure and study Dijkstra's algorithm for finding shortest paths.

Shortest Paths II

Week 05

We studied how the SP structure changes if weights are changed in a systematic way (all inc/dec; scaled) and let the main ideas behind Dijkstra's algorithm evolve from generalizing BFS in a natural way.

Shortest Paths III

Week 06

We examine how to modify Dijkstra to work in the presence of negative edge weights and we introduce Bellman-Ford to detect the presence of negative cycles, and Floyd-Warshall to handle APSP.

Network Flows I

Week 07

We introduce the setting of network flows and illustrate how it can be used to model, for example, the maximum matching problem.

Network Flows II

Week 08

We continue to demonstrate applications of flows with two problems: timetable scheduling and sport elimination.

Approximation Algorithms - I

Week 09

Approximation Algorithms - II

Week 10

Randomized Algorithms - I

Week 11

Randomized Algorithms - II

Week 12

Parameterized Algorithms - I

Week 13

Parameterized Algorithms - II

Week 14