Class material Supplements

1. Reductions

   • This week tutorial Tutorial1-Reductions.pdf
   • A very nice tutorial can be found here.

     The reduction presented in this tutorial is $SP \le SEP$. 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

   • This week tutorial Tutorial2-Greedy.pdf
   • Notes by Prof Dinitz are available here
   • Running example can be find here
   
   

3. MST

   • This week tutorial Tutorial3-MST.pdf
   
   

4. Dynamic programing

   • This week tutorial Tutorial4-Dynamic.pdf
   • Dynamic helper
   
   

5. Dijkstra

   • Dijkstra running example here.
   • This week tutorial Tutorial5-Dijakstra.pdf
   
   

6. Bellman Ford

   • This week tutorial Tutorial6-BellmanFord.pdf
   
   

7. DFS,Topological Sort and G^scc

   • This week tutorial Tutorial7-DFS-Topological_Sort-Gscc.pdf
   
   

8. Flow 1

   • This week tutorial Tutorial8-flow1.pdf
   • Please bring this handout to the practical session Tutorial8-flow1-2012-handout.pdf
   • See this example of Ford Fulkerson.
   
   

9. Dinitz' Algorithm

   • This week tutorial Tutorial10-Dinitz.pdf Please note that this is a draft version
   • Dinitz running example here
   
   

10. Flow, Randomized Algorithms

    • This week tutorial Tutorial11-Flow, Randomized.pdf
    
    

11. Inroduction to Complexity and more Randomized….

    • This week tutorial Tutorial11-Verifying-partB.pdf
    • Randomized Equality Tutorial8-Randomized-2011.pdf
    
    

12. Inroduction to Complexity (Part A)

    • This week tutorial Tutorial12-Complexaty1.pdf

    
    

13. Inroduction to Complexity (Part B)

    • This week tutorial Tutorial13-NP-2.pdf
    • and Tutorial14-NAE.pdf