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

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.