| Course Code | CS 315 |
| Course Name | Advanced Algorithms |
| Offered to | UG/PG |
| Pre-requisites | NIL |
| Lecture | 3 |
| Tutorial | 0 |
| Practical | 0 |
| Credit | 6 |
| Reference | 1. Motwani and Raghavan. Randomized Algorithms. Cambridge, UK: Cambridge University Press, 1995 2. Vijay Vazirani, Approximation Algorithms, Springer, 2001. 3. Michael Mitzenmacher and Eli Upfal, Probability and Computing, Cambridge University Press, 2005. 4. T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, 2nd edition, 2001. |
| Description | The main objective of Algorithms course is to design efficient algorithms. Unfortunately, many problems turn out to be NP-hard and therefore these problems are highly unlikely to have efficient algorithms. Approximation algorithms are a way of getting around this situation. We will then look at randomised algorithms, which gives a better running time. We pay for this increased speed by accuracy (the fact that the algorithm might answer incorrectly sometimes). In the end, we will also look at streaming algorithms. 1. NP-completeness: Introduction to NP, NP-hard, NP-completeness, Example problems in NP, Reductions, showing problems are NP-hard. 2. Approximation algorithms: Introduction to approximation algorithms, approximation algorithms for set cover, knapsack, bin packing, maximum satisfiability (MAX-SAT) 3. Randomized algorithms: Use of random variables, chernoff bounds in randomised algorithms; randomised algorithms for verifying matrix multiplication, quick sort, computing mean, set balancing, packet routing; Introduction of FPRAS, approximate counting and approximate sampling, DNF counting, CNF counting with NP-oracle, Markov Chains and applications in randomized 2-SAT, page rank. 4. Streaming algorithms: Introduction, sketching, distinct and frequency moments. 5. Others: Parameterized complexity, string matching, parallel algorithms |