This note
introduces students to advanced techniques for the design and analysis of
algorithms, and explores a variety of applications. Topics covered includes:
Greedy algorithms, Dynamic programming, Network flow applications, matchings,
Randomized algorithms, Karger's min-cut algorithm, NP-completeness, Linear
programming, LP duality, Primal-dual algorithms, Semi-definite Programming, MB
model contd., PAC model, Boosting in the PAC framework.