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