Algorithms, Spring 19/20, 0368.2160

 

Uri Zwick and Haim Kaplan

 

Algorithms wiki website

 

Lectures:

1.    Graph representations, presentation

2.    Breadth First Search: video 1, 2, 3, presentation, annotated presentation

3.    Depth First Search: video 1, 2, 3, presentation, annotated presentation

4.    Applications of DFS (1)

o   Topological sort: video, presentation. annotated presentation

o   Strongly Connected Components (Kosaraju, Sharir, 1981, also in the book section 22.5): video, presentation, annotated presentation

5.    DFS in undirected graphs: video, presentation, annotated presentation

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.

   A correction to the proof of Thm 9 at the end of part 1 and the beginning of part 2: video, annotated presentation

   A visualization to the proof of Thm 9: video, annotated presentation

7.    Minimum spanning trees