Algorithms, Spring
19/20, 0368.2160
Lectures:
4. Applications of DFS (1)
6. Applications of DFS (2)
o
Strongly Connected Components in one DFS (Tarjan, 1972)
video 1,2,3,4,5,
presentation, annotated presentation 1,2,3,4,5.
o
A correction to the proof of Thm 9 at the end of part 1 and the beginning of part 2: video, annotated presentation
o
Intro and safe edge video 1,2
o
Kruskal’s algorithm video 1,2
o
Prim’s algorithm video
8. Dynamic programming
o
Longest Increasing Subsequence (LIS): video 1,2, presentation 1,2, annotated presentation 1,2
9. Shortest paths
10. All pair shortest paths
11. Linear programming: presentation
(for all parts)
o
Introduction: video
o
The simplex algorithm by example: video
o
The simplex algorithm: video