Syllabus
|
Course Code: MT-CSE-20-21 Course Name: Advances in Algorithms |
||
| MODULE NO / UNIT | COURSE SYLLABUS CONTENTS OF MODULE | NOTES |
|---|---|---|
| 1 | Sorting: Review of various sorting algorithms, topological sorting 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. | |
| 2 | Flow-Networks: Maxflow-Mincut theorem, Ford-Fulkerson Method to compute maximum flow, Edmond-Karp maximum-flow algorithm. Graph Matching: Algorithm to compute maximum matching. Characterization of maximum matching by augmenting paths, Edmond's Blossom algorithm to compute augmenting path. |
|
| 3 | Shortest Path in Graphs: Floyd-Warshall algorithm and introduction to dynamic programming paradigm. More examples of dynamic programming. 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. |
|
| 4 | Linear Programming: Geometry of the feasibility region and Simplex algorithm.
NP-completeness: Examples, proof of NP-hardness and NP-completeness. Modulo Representation of integers/polynomials: Chinese Remainder Theorem, Conversion between base-representation and modulo-representation. Extension to polynomials. Application: Interpolation problem. |
|
