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 (LP): presentation (for all parts)

o    Introduction: video (LP1)

o    The simplex algorithm by example: video (LP2)

o    The simplex algorithm: video (LP3)

o    The simplex algorithm – termination: video (LP4)

o    The simplex algorithm – initialization: video (LP5)

o   ---------------Material for 24/05/20 – 30/05/20 -----------------------

o    LP duality: video (LP6)

o    LP duality – interpretation: video (LP7)

o    LP duality – proof: video (LP8)

o    LP duality – Farkas’ Lemma: video : video (LP9)

o    Linear Programming vs. Integer Programming: video (LP10)

o    Single Source Shortest Paths as an LP problem: video (LP11)

o    Flow problems as LP problems: video (LP12)

o    Dual LPs for flow and shortest paths problems: video (LP13)

o   -------------------------------------------------------------------------------