The course describes basic algorithms in graph theory such as graph traversing algorithms, spanning trees algorithms, shortest path algorithms, strongly connected components, cut vertices, matching, and maximum network flow algorithms. The course also contains topics in nondeterministic algorithms, polynomial problem reduction, and approximation algorithms.

After the course, the students should be able to design and analyse algorithms for graph problems. Also they should be able to decide correctly whether to choose a precise, approximate, or heuristic algorithm for new given problems.

Active participation from the class is very important for this course to be successful.

Fall 2014

Sunday and Tuesday: 9 - 10:30

Discrete Mathematics, Data Structure, Algorithm Design.

Assignments | 14% |

Quizes | 28% |

Final Exam | 38% |

Final Projects | 20% |

1 | Sunday | 30 Shahrivar | Introduction | |||

2 | Tuesday | 1 Mehr | Algorithms by Induction | Problem Set 1 Upload | ||

3 | Sunday | 6 Mehr | Elementary Graph Algorithms, DFS, BFS, Topological Sort | |||

4 | Tuesday | 8 Mehr | Minimum Spanning Tree - Prime and Kruskal | Problem Set 2 Upload | Problem Set 1 Due | |

Sunday | 13 Mehr | |||||

5 | Tuesday | 15 Mehr | Shortest Path - Bellman Ford and Dijkstra | Problem Set 2 Due | ||

6 | Sunday | 20 Mehr | Shortest Path - Floyd | Quiz 1 | Problem Set 3 Upload | |

7 | Tuesday | 22 Mehr | Strongly Connected Components | |||

8 | Sunday | 27 Mehr | Cut Vertices | Quiz 2 | Problem Set 4 Upload | Problem Set 3 Due |

9 | Tuesday | 29 Mehr | Matching and Hall Condition | |||

10 | Sunday | 4 Aban | Network Flow - Fordfulkerson | Quiz 3 | Problem Set 5 Upload | Problem Set 4 Due |

11 | Tuesday | 6 Aban | Game Theory Applications in Intelligence Systems | |||

12 | Sunday | 11 Aban | Game Theory Applications | |||

13 | Tuesday | 13 Aban | Game Theory Applications in Sensor Networks | Problem Set 5 Due | ||

Sunday | 18 Aban | |||||

14 | Tuesday | 20 Aban | Game Theory Applications in Security | |||

15 | Sunday | 25 Aban | Nondeterministic Algorithms | Quiz 4 | ||

16 | Tuesday | 27 Aban | NP-Completeness and Reduction | |||

17 | Sunday | 2 Azar | Reduction | Problem Set 6 Upload | ||

18 | Tuesday | 4 Azar | Approximation Algorithms - Vertex Cover | Quiz 5 | ||

19 | Sunday | 9 Azar | Approximation Algorithms - TSP 1 | Problem Set 6 Due | ||

20 | Tuesday | 11 Azar | Approximation Algorithms TSP 2 | Problem Set 7 Upload | ||

21 | Sunday | 16 Azar | Final Project presentations | Quiz 6 | ||

22 | Tuesday | 18 Azar | Final Project presentations | Problem Set 7 Due | ||

23 | Sunday | 23 Azar | Final Project presentations | |||

24 | Tuesday | 25 Azar | Final Project presentations | Quiz 7 | ||

Sunday | 30 Azar | |||||

Tuesday | 2 Dey | |||||

25 | Sunday | 7 Dey | Problem Solving | |||

26 | Tuesday | 9 Dey | Problem Solving |