## 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
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