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 (LP): presentation
(for all parts)
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 – interpretation: video (LP7)
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.)