About This Course
The objective of this course is to enable each individual student to pursue some of these activities: explore advanced topics in algorithmic and complexity theory; engage in analysis and design of complex algorithms for real-world problems in current application domains; learn and evaluate advanced / novel algorithm design strategies and techniques; and understand sturdy / open problems in algorithmic or complexity theory by analyzing known approaches and their limitations. The scope of this course includes (i) algorithm design strategies such as Randomization and Approximation as well as specific techniques therein (ii) NP-hard problems and approaches to handle them and (iii) problem/application domains such as online social networks, Internet and the Web, number theory and cryptography, and distributed computing. While algorithm analysis is included in the scope wherever applicable the emphasis of the course is on algorithm design as such and specific analysis techniques are not emphasized. While the student is exposed to various problem/application domains from an algorithmic perspective the focus is not on the domains but on specific problems and approaches to solving those problems. Of course, the student is encouraged – if interested – to pursue a specific domain for a project during the course and – occasionally, if the student is tenacious enough – beyond the course
Frequently Asked Questions
Do I need to buy a textbook?
T1. “Randomized Algorithms”, by “Motwani, Rajiv & P. Raghavan”, CUP, 1995.
T2. “Combinatorial Optim.: Algo. & Complexity”, by “Papadimitnou, C.H. & Kenneth Steiglitz”, PHI, 1982