CS503: Advances in Algorithms

This course deals with advanced topics of algorithms.

• Tuesday (0900-100)
• Thursday (0900-1000)
• Friday (0900-1000)

Broad syllabus is as follows: Algorithmic paradigms: Dynamic Programming, Greedy, Branch-and-bound; Asymptotic complexity, Amortized analysis; Graph Algorithms: Shortest paths, Flow networks; NP-completeness; Approximation algorithms; Randomized algorithms; Linear programming; Special topics: Geometric algorithms (range searching, convex hulls, segment intersections, closest pairs), Numerical algorithms (integer, matrix and polynomial multiplication, FFT, extended Euclid's algorithm, modular exponentiation, primality testing, cryptographic computations), Internet algorithms (text pattern matching, tries, information retrieval, data compression, Web caching).

• T. H. Cormen, C. L. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd edition, Prentice-hall Of India Pvt.. Ltd.

• Week 1: Analysis of algorithms, Finding max, average case analysis, Finding skyline
• Week 2: Towers of Hanoi and its variant, Fibonacci numbers, Karatsuba algorithm for multiplication, FFT
• Week 3: FFT, State space exploration, Dynamic Programing - weighted interval scheduling
• Week 4: Dynamic programming - segmented least square,
• Week 5:

• Internal evaluation