Introduction: Order notations, induction, floor and ceiling functions, pigeon-hole principle, recurrence relations; Algorithm design techniques: Greedy algorithms, divide-and-conquer algorithms, dynamic programming, amortization, optimal algorithms; Algorithms on arrays: Selection and median-finding, counting, radix and bucket sorts, string matching (Rabin-Karp and Knuth-Morris-Pratt algorithms); Geometric algorithms: Convex hulls, sweep paradigm, Voronoidiagrams; Algorithms on graphs: Traversal, topological sort, minimum spanning trees, shortest path, network flow; NP-completeness: Classes P and NP, reduction, NP-completeness, examples of NP-complete problems; Approximation algorithms: PTAS and FPTAS, examples; Randomized algorithms: Monte Carlo and Las Vegas algorithms, examples.
Prerequisite: None
Texts/References Books:
- T. H.Cormen, C. E.Lieserson, R. L.Rivest and C. Stein, “Introduction to Algorithms”, 3rd Ed., PHI, 2010.
- J. Kleinberg and É. Tardos, “Algorithm Design”, Pearson, 2012.
- M. T. Goodrich and R.Tamassia, “Algorithm Design: Foundations, Analysis, and Internet Examples”, Second Edition, Wiley, 2006.
- R.Motwani and P. Raghavan, “Randomized Algorithms”, MHE, 2010.
- V.V. Vazirani, “Approximation Algorithms”, Springer, 2010.
|