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

## o
** Introduction: video**

## o
** The simplex algorithm by example: video**

## o
** The simplex algorithm: video**

** **