Unit 1 Sorting

6 lecture hours

• 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

Unit 2 Matroids

8 lecture hours

• Introduction to greedy paradigm
• algorithm to compute a maximum weight maximal independent set
• Application to MST
• Graph Matching: Algorithm to compute maximum matching
• Characterization of maximum matching by augmenting paths
• Edmond's Blossom algorithm to compute augmenting path

Unit 3 Flow-Networks

9 lecture hours

• Maxflow-mincut theorem
• Ford-Fulkerson Method to compute maximum flow
• Edmond-Karp maximum-flow algorithm
• 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

Unit 4 Shortest Path in Graphs

• Floyd-Warshall algorithm and introduction to dynamic programming paradigm
• More examples of dynamic programming
• Modulo Representation of integers/polynomials: Chinese Remainder Theorem
• Conversion between base-representation and modulo-representation
• Extension to polynomials
• Application: Interpolation problem. 10 Subject Code: 3720216 w.e.f