Contents (hide)
   1 Reductions
   2 Greedy
   3 MST
   4 Dynamic programing
   5 Dijkstra
   6 Bellman Ford
   7 DFS,Topological Sort and Gscc
   8 Flow
   9 Edmonds Karp
   10 Dinitz' Algorithm
   11 Randomized Algorithms
   12 Inroduction to Complexity (Part A)
   13 Inroduction to Complexity (Part B)

Class material Supplements

  1. Reductions

    • In some of the practical session groups the time run out too quickly…. Here is the first Tirgul Tutorial1-Reductions.pdf
    • A very nice tutorial can be found here.

      The reduction presented in this tutorial is tex. It was briefly given in class. Here it is accompanied with some very detailed comments and explanations regarding the way of thinking and the formality of proofs.


  2. Greedy


  3. MST


  4. Dynamic programing


  5. Dijkstra

    • Dijkstra running example here.
    • Dijkstra and bottle neck running example ppt
    • The missing part of the proofs for Dijkstra's algorithm is here (from Elad and Amos lectures)
    • This week tutorial Tutorial5-Dijkstra.pdf

  6. Bellman Ford


  7. DFS,Topological Sort and Gscc


  8. Flow


  9. Edmonds Karp


  10. Dinitz' Algorithm


  11. Randomized Algorithms


  12. Inroduction to Complexity (Part A)


  13. Inroduction to Complexity (Part B)