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 $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
   
   

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

8. Randomized Algorithms

   • This week tutorial Tutorial8-Randomized-2011.pdf
   
   

9. Flow 1

   • This week tutorial Tutorial8-flow1.pdf
   
   

10. Edmonds Karp

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

    
    

11. Dinitz' Algorithm

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

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