Review of basic concepts; Worst case and average case analysis: big oh;
small oh, omega and theta notations, Solving recurrence equations.
Overview of basic design paradigms such as incremental approach;
divide and conquer; greedy paradigm; dynamic programming
backtracking; branch and bound; pruning; transformations; preprocessing
and case studies illustrating each design methodologies with complete
analysis of algorithms. Advanced graph algorithms; Matching; Network
flows; Applications to OR / optimization; Geometric algorithms; Linesweep
paradigm; Incremental design; Closest pair problem; Convex hull;
Triangulations; Planar point location; Segment intersection; Applications
to data bases and computer graphics. Stringology; Pattern matching; 8M
algorithms; KMP algorithms; Computational number theory; GCD
algorithm; Primality tests; Quadratic residues; Applications to
cryptography. Lower bound theory; Information theoretic bounds;
Adversary arguments; NP completeness; Basic techniques for proving
NP completeness case studies. Approximate algorithms; Scheduling
problems; Set cover problem; Bin packing problem; Polynomial time
approximate schemes; Basics of parallel algorithms; Flynn's
classification; SIMD algorithms for simple problems; List ranking. Basics
of randomized algorithms; Their practical significance; Las Vegas and
Monte Carlo algorithms; Skip lists; Treaps; Uniform hashing.
- Teacher: prangan Pandu Rangan C