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.

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   A visualization to the proof of Thm 9: video, annotated presentation

7.    Minimum spanning trees: presentation, 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   Fibonacci numbers: video, presentation

o   Binomial coefficients and Maximum weighted independent set in a path: video, presentation, annotated presentation

o   Longest Common Subsequence (LCS): video, presentation, annotated presentation

o   Longest Increasing Subsequence (LIS): video 1,2, presentation 1,2, annotated presentation 1,2

o   Knapsack: video, presentation, annotated presentation

o   Optimal static binary search trees: video 1,2, presentation, annotated presentation

9.    Shortest paths

o   Relaxations and Bellman-Ford: video 1,2,3,4, presentation, annotated presentation

o   Shortest paths in DAGs: video, presentation, annotated presentation

o   Dijkstraís algorithm: video, presentation, annotated presentation

o   Bidirectional Dijkstra for p2p shortest paths: video, presentation, annotated presentation

o   Goal directed Dijkstra (A*): video, presentation, annotated presentation

10. All pair shortest paths

o   Johnsonís algorithm: video, presentation, annotated presentation

o   Min-Sum product: video, presentation, annotated presentation

o   Floyd-Warshall: video, presentation, annotated presentation

o   Transitive-closure: video, presentation, annotated presentation

11. Linear programming: presentation (for all parts)

o    Introduction: video

o    The simplex algorithm by example: video

o    The simplex algorithm: video

The following videos