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)

12.  Network flow (FLOW): presentation (for all parts)

o   ---------------- Material for 31/05/20 – 06/06/20 ----------------------

o   Network flow: Flows and cuts video (FLOW1)

o   Network flow: Augmenting paths video (FLOW2)

o   Network flow: Maximum flow minimum cut video (FLOW3)

o   Network flow: The Ford-Fulkerson method (part a) video (FLOW4a)

o   Network flow: The Ford-Fulkerson method (part b) video (FLOW4b)

o   Network flow: Bipartite matching video (FLOW5)

o   ------------------------------------------- Material for 07/06/20 – 13/06/20 --------------------------------------

o   Network flow: The Edmonds-Karp algorithm (part a) video (FLOW6a)

o   Network flow: The Edmonds-Karp algorithm (part b) video (FLOW6b)

o   Network flow: The Edmonds-Karp algorithm - examples video (FLOW7)

o   Network flow: Residual flows video (FLOW8)

o   Network flow: Dinic’s algorithm video (FLOW9)

o   -------------------------------------------- Material for 14/06/20 – 20/06/20 --------------------------------------

o   Network flow: Dinic’s algorithm – Finding blocking flows video (FLOW10)

o   Network flow: Dinic’s algorithm on unit networks video (FLOW11)

o   Network flow: Dinic’s algorithm on unit capacity networks video (FLOW12)

o   Network flow: Allowing antiparallel edges video (FLOW13)

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

The online sessions scheduled for June 21 and June 23 are postponed.
(See the message sent to the mailing list.)