## Advanced Algorithms (CS 315), Jan 2010

**Time**

CL2, Monday 10.30am - 11.30pm

LH2, Wednesday 9.30am - 10.30am

LH2, Friday, 9.30am - 10.30am

**TAs**

Ajay Kumar and Prince

**Textbook**

[KT] Algorithm Design by

*Kleinberg and Tardos*

[V] Approximation Algorithms by

*Vijay V. Vazirani*

[MU] Probability and Computing by

*Mitzenmacher and Upfal*

[MR] Randomized algorithms by

*Motwani and Raghavan*

**Reference books**

[WS] Design of approximation algorithm by

*Williamson and Shmoys*

**Grading Scheme**

Assignments (15%) - From n+1 assignments, best n assignment marks will be used for grades.

Attendance (5%), Quiz 1 (10%), Quiz 2 (10%), MidSem (30%), EndSem (30%)

**Malpractice**

If caught copying assignment for the first time, zero for the assignment and one grade lower. If caught copying more than once or caught copying in examination, I will report it to institute senate committee which will decide on the punishment.

**Tutorials**

**Assignments**

Assignment 1: Revision of DAA course

Assignment 2: Approximation algorithm

Assignment 3: Probability

**Course Contents**

# | Date | Contents | Source |
---|---|---|---|

1 | 4/1 | Introduction, course evaluation | |

2 | 7/1 | Order Notation (Big O, omega), Recurrence equations | KT |

3 | 11/1 | Algorithmic strategies: Divide and conquer | KT |

4 | 14/1 | Algorithmic strategies: Greedy algorithm | KT |

5 | 16/1 | Approximation algorithm using greedy strategy: 1. Scheduling Problem - How to schedule n jobs in m parallel machines so that all programs are completed as early as possible. 2. k-center problem - Identify the k-best location to construt a movie theatre in a city. | KT |

6 | 17/1 | Approximation using greedy strategy: Minimal set-cover problem. A O(log(n)) approximation for the minimal set cover. | KT |

7 | 28/1 | Continuing with Minimal set-cover problem. Introduction to minimal vertex cover. | KT |

8 | 30/1 | A 2-approximation for the minimum vertex cover problem using the primal-dual method. | KT |

9 | 31/1 | Revising dynamic programming strategy through subset sum problem: We look at a O(nW), pseudo-polynomial algorithm. Introduction to the Knapsack problem and its similarities with the subset sum problem. | KT |

10 | 4/2 | Knapsack problem: An alternate pseudo-polynomial time algorithm of O(n^2v*) where v* is the maximum cost. An approximate algorithm for the Knapsack problem. We also analysed its running time. | KT |

11 | 6/2 | Analyzing the approximation bound of the algorithm from last class. Introduction to FPRAS. Showing Knapsack gives an FPRAS. | Notes |

12 | 11/2 | Tutorial session - Discussed the assignment questions | |

12 | 13/2 | Quiz - I | paper |

13 | 15/2 | Introduction to Probabilistic algorithms. A randomized algorithm for checking whether two polynomials are identical. Also showed that when there is one-sided error we can increase the confidence by running the algorithm multiple times. | MU-1 |

14 | 18/2 | A randomized algorithm for minimum cut-set. | MU-1 |

15 | 20/2 | Randomized quicksort | MU-2, Notes |

16 | 26/2 | Mid-sem | question paper |

17 | 6/3 | Union bound; Markov's Inequality, Chebyshev's Inequality - Expectation, variance | MU-3 |

18 | 8/3 | Coin toss example comparison between Markov's, Chebyshev's, union bound; Coupon collector's problem | MU-3 |

19 | 11/3 | Chernoff bound, coin flip example | MU-4 |

20 | 13/3 | Chernoff bound - parameter estimation application | MU-4 |

21 | 15/3 | Balls and Bins application - Bucket Sort | MU-4 |

22 | 20/3 | Poisson Distribution - Introduction, expectation, tail bounds | MU-4 |

23 | 22/3 | Random graphs: Hamiltoninan cycle - Introduction (guest lecture by Dr. Arpita) | MU-4 |

24 | 25/3 | (2hrs) Random graphs: Hamiltoninan cycle - modified algorithm | MU-4 |

25 | 1/4 | Random graphs: Hamiltoninan cycle - Failure probability analysis | MU-4 |

26 | 3/4 | Hashing: Bit Strings | MU-4 |

27 | 5/4 | Review - from midsem till 3/4 | MU-3,4 |

28 | 6/4 | Quiz 2 | paper |

29 | 8/4 | Randomized poly time algorithm for 2-SAT | MU-6, notes |

30 | 10/4 | Randomized algorithm for 3-SAT: Algorithm runs better than checking all satisfying assignments. | MU-7, notes |

31 | 12/4 | Introduction to Markov Chains: Seeing the previous two algorithms through this "view". | MU-6 |

32 | 15/4 | Modelling problems using Markov Chains | |

33 | 17/4 | Application of Markov Chains: Google Pagerank | slides |