We introduce the paradigm of greedy algorithms with some examples.
Activity SchedulingIslands War
Greedy Algorithms II
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.
Minimum Spanning Trees
We introduced the Union Find data structure to appreciate how Kruskal's algorithm can be efficiently implemented.
Shortest Paths I
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
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
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
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
We continue to demonstrate applications of flows with two problems: timetable scheduling and sport elimination.