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

(i) Approximation algorithms

(ii) Randomized Algorithms

(iii) Interior Point Method