CS 602: Design and Analysis of Algorithms

Course Contents

1. Sorting: Review of various sorting algorithms, topological sorting. (2 lecture)
2. Graph Definitions and Elementary Algorithms: Shortest path by BFS, shortest  path in edge-weighted case (Dijkasra's), depth-first search and computation of strongly connected components, emphasis on correctness proof of the algorithm and time/space analysis, example of amortized analysis. (4 lectures)
3. Matroids: Introduction to greedy paradigm, algorithm to compute a maximum weight maximal independent set. Application to MST. (3 lecture)
4. Graph Matching: Algorithm to compute maximum matching. characterization of maximum matching by augmenting paths, Edmond's Blossom algorithm to compute augmenting path. (3 lectures)
5. Flow-Networks: Maxflow-mincut theorem, Ford-Fulkerson Method to compute maximum flow, Edmond-Karp maximum-flow algorithm. (3 lectures)
6. Matrix Computations: Strassen's algorithm and introduction to divide and conquer paradigm, inverse of a triangular matrix, relation between the time complexities of basic matrix operations, LUP-decomposition. (3 lectures)
7. Shortest Path in Graphs: Floyd-Warshall algorithm and introduction to dynamic programming paradigm. More examples of dynamic programming. (3 lecture)
8. String Matching: Knuth-Morris-Pratt algorithm, Rabin-Karp algorithm, testing the membership of a regular language. (3 lectures)
9. Basic Number algorithms: Reciprocal and square algorithms to show that the time complexities of multiplication, squaring, reciprocal, and division are same. Extension to polynomials. (3 lectures)
10. Modulo Representation of integers/polynomials: Chinese Remainder Theorem, Conversion between base-representation and modulo-representation. Extension to polynomials. Application: Interpolation problem. (3 lectures)
11. Discrete Fourier Transform (DFT): In complex field, DFT in modulo ring. Fast  Fourier Transform algorithm. Schonhage-Strassen Integer Multiplication algorithm. (4 lectures)
12. Linear Programming: Geometry of the feasibility  region and Simplex algorithm. (2 lectures)
13. NP-completeness: Examples, proof of NP-hardness and NP-completeness. (2 lectures)
14. One or more of the following topics based on time and interest:

1. Approximation algorithms
2. Randomized Algorithms
3. Interior Point Method
4. Advanced Number Theoretic Algorithm

References

1. Introduction to Algorithms"  by Cormen, Leiserson, Rivest, Stein.

2. The Design and Analysis of Computer Algorithms"  by Aho, Hopcroft, Ullman.

3. Algorithm Design" by Kleinberg and Tardos.