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

(iv) 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.