Graph Algorithms Fall 2014

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

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, "Introduction to Algorithms", Third edition, MIT Press, 2009.

Udi Manber, "Introduction to Algorithms, A Creative Approach", Addison-Wesley, 1989.

Alan Gibbons, "Algorithmic Graph Theory", Cambridge University Press, 1985.

Maarten van Steen , "Graph Theory and Complex Networks: An Introduction", Maarten van Steen , 2010.

Discrete Mathematics, Data Structure, Algorithm Design.

Assignments 14%
Quizes 28%
Final Exam 38%
Final Projects 20%
1Sunday30 ShahrivarIntroduction
2Tuesday1 MehrAlgorithms by InductionProblem Set 1 Upload
3Sunday6 MehrElementary Graph Algorithms, DFS, BFS, Topological Sort
4Tuesday8 MehrMinimum Spanning Tree - Prime and KruskalProblem Set 2 UploadProblem Set 1 Due
Sunday13 Mehr
5Tuesday15 MehrShortest Path - Bellman Ford and DijkstraProblem Set 2 Due
6Sunday20 MehrShortest Path - FloydQuiz 1Problem Set 3 Upload
7Tuesday22 MehrStrongly Connected Components
8Sunday27 MehrCut VerticesQuiz 2Problem Set 4 UploadProblem Set 3 Due
9Tuesday29 MehrMatching and Hall Condition
10Sunday4 AbanNetwork Flow - FordfulkersonQuiz 3Problem Set 5 UploadProblem Set 4 Due
11Tuesday6 AbanGame Theory Applications in Intelligence Systems
12Sunday11 AbanGame Theory Applications
13Tuesday13 AbanGame Theory Applications in Sensor NetworksProblem Set 5 Due
Sunday18 Aban
14Tuesday20 AbanGame Theory Applications in Security
15Sunday25 AbanNondeterministic AlgorithmsQuiz 4
16Tuesday27 AbanNP-Completeness and Reduction
17Sunday2 AzarReductionProblem Set 6 Upload
18Tuesday4 AzarApproximation Algorithms - Vertex CoverQuiz 5
19Sunday9 AzarApproximation Algorithms - TSP 1Problem Set 6 Due
20Tuesday11 AzarApproximation Algorithms TSP 2Problem Set 7 Upload
21Sunday16 AzarFinal Project presentationsQuiz 6
22Tuesday18 AzarFinal Project presentationsProblem Set 7 Due
23Sunday23 AzarFinal Project presentations
24Tuesday25 AzarFinal Project presentationsQuiz 7
Sunday30 Azar
Tuesday2 Dey
25Sunday7 DeyProblem Solving
26Tuesday9 DeyProblem Solving

Problem Set 1