 Home > Teaching > CS 602: Design and Analysis of Algorithms

#### 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