#### CS 602: Design and Analysis of Algorithms

###### Course Contents

- Sorting: Review of various sorting algorithms, topological sorting. (2 lecture)
- 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)
- Matroids: Introduction to greedy paradigm, algorithm to compute a maximum weight maximal independent set. Application to MST. (3 lecture)
- Graph Matching: Algorithm to compute maximum matching. characterization of maximum matching by augmenting paths, Edmond's Blossom algorithm to compute augmenting path. (3 lectures)
- Flow-Networks: Maxflow-mincut theorem, Ford-Fulkerson Method to compute maximum flow, Edmond-Karp maximum-flow algorithm. (3 lectures)
- 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)
- Shortest Path in Graphs: Floyd-Warshall algorithm and introduction to dynamic programming paradigm. More examples of dynamic programming. (3 lecture)
- String Matching: Knuth-Morris-Pratt algorithm, Rabin-Karp algorithm, testing the membership of a regular language. (3 lectures)
- 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)
- Modulo Representation of integers/polynomials: Chinese Remainder Theorem, Conversion between base-representation and modulo-representation. Extension to polynomials. Application: Interpolation problem. (3 lectures)
- Discrete Fourier Transform (DFT): In complex field, DFT in modulo ring. Fast Fourier Transform algorithm. Schonhage-Strassen Integer Multiplication algorithm. (4 lectures)
- Linear Programming: Geometry of the feasibility region and Simplex algorithm. (2 lectures)
- NP-completeness: Examples, proof of NP-hardness and NP-completeness. (2 lectures)
- One or more of the following topics based on time and interest:

- Approximation algorithms
- Randomized Algorithms
- Interior Point Method
- Advanced Number Theoretic Algorithm

###### References

- Introduction to Algorithms" by Cormen, Leiserson, Rivest, Stein.
- The Design and Analysis of Computer Algorithms" by Aho, Hopcroft, Ullman.
- Algorithm Design" by Kleinberg and Tardos.