Class material Supplements

1. Reductions

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

     The reduction presented in this tutorial is . 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
   
   

3. MST

   • This week tutorial Tutorial3-MST.pdf
   • Invariant for Kruskal correctness proof
   
   

4. Dynamic programing

   • This week tutorial Tutorial4-Dynamic.pdf
   
   

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-Gscc2010.pdf
   
   

8. Flow 1

   • This week tutorial Tutorial8-flow1.pdf
   
   

9. Edmonds Karp

   • This week tutorial Tutorial9-FordFulkerson,EdmondsKarp,Hall.pdf
   • Ford-Fulkerson running example here

   
   

10. Dinitz' Algorithm

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

11. Randomized Algorithms

    • This week tutorial Tutorial11-Randomized-Verifying.pdf

    
    

12. Inroduction to Complexity (Part A)

    • This week tutorial Tutorial12-Reductions.pdf
    
    

13. Inroduction to Complexity (Part B)

    • This week tutorial Tutorial13-NP-2.pdf