Course information

Introduction: Data structures and algorithms. Asymptotic analysis. Graphs: Basic concepts. Depth-first search and Breadth-first search. Topological layout. The Divide-and-Conquer Method: Binary search. Matrix multiplication. Strassen’s method. Greedy Algorithms: The activity selection problem. Huffman codes. Single-source shortest paths (Dijkstras algorithm). Minimum spanning trees (Prim algorithm). Dynamic Programming: Chain multiplication. Greatest common subsequence. All-pairs shortest paths. Lower Bounds: “Input”/“Output” lower bounds. Adversary lower bounds. Lower bounds for comparison-based sorting algorithms and for Huffman codes. Graph Algorithms: Checking graph acyclicity. Strongly connected components. Single-source shortest paths (the Bellman-Ford algorithm). Maximum flow (the Ford-Fulkerson algorithm and the Edmonds-Karp algorithm). NP and Computational Intractability: Polynomial time reductions. The class NP. NP-complete problems.