Prerequisite Courses: Data Structures, Linear Algebra, Calculus, Discrete Mathematics. Exercises will be given in the recitations, and their solutions will be graded. These will form about 10% of the final grade . The rest of the final grade will be determined by the final exam.
Introduction to Algorithms, by T. Cormen, C. Leiserson and R. Rivest. MIT Press, 1990 (CLR).
Most of the course follows the above book.
Graph Algorithms, by S. Even. Computer Science
Press, 1979.
Data Structures and Network Algorithms, by R. E.
Tarjan.
Graph Algorithms: Breadth first search, Depth first search, Topological sort, Strongly connected components, Biconnected components, Minimum spanning trees (Kruskal, Prim), Shortest paths (Dijkstra, Bellman-Ford), All-pairs shortest paths (Floyd-Warshall, Johnson), Dynamic Programming, Flow algorithms (Ford-Fulkerson, Edmonds-Karp, Dinic). String matching: Finite automata, KMP. Introduction to NP-completeness.
1.
October 19:
Introduction and notation, representation of graphs, BFS
2.
October 26:
BFS (end), DFS
3.
November 2:
Applications of DFS: topological sort, strongly connected components.
4.
November 9:
Minimum Spanning Trees, Kruskal's Algorithm.
5.
November 16:
Prim's Algorithm, Shortest paths.
6.
November 23:
More on shortest paths, Dijkstra's Algorithm.
7.
November 30:
The algorithm of Bellman and Ford, All pairs shortest
paths.
8.
December 7:
The algorithm of Floyd and Warshall, Johnson's
Algorithm.
9.
December 14:
Dynamic Programming.
10. December 21:
Network flows, the Max-flow Min-cut Theorem, Ford and Fulkerson's algorithm.
11. December 28:
The algorithm of
12. January 4:
String matching, the KMP algorithm.
13. January 11:
Introduction to NP-completeness
14. January 18:
More on NP-completeness. Concluding remarks.