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.Algorithm Design
by J. Kleinberg and E. Tardos. Pearson/Addison Wesley, 2006.Graph Algorithms,
by S. Even. Computer Science Press, 1979.Data Structures and Network Algorithms,
by R. E. Tarjan. SIAM, 1983.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 (if time permits). Linear Programming.