Algorithm Design and Analysis (CS60007)
Autumn Semester 2017
Instructor: Animesh Mukherjee (animeshmATcse.iitkgp.ernet.in)
Teaching Assistant: Binny Mathew (binnymathew1988ATgmail.com), Pranjal Kanojiya (pranjal989091@gmail.com), Satinder Kaur (kaursatinder213@gmail.com), Tanuj Joshi (tjcomp.rocker@gmail.com) and Jasabanta Patro (jasabantapatro@gmail.com)
Class Timings: MON (15:00-17:00), TUE (15:00-16:00, 18:00-19:00)
Location: Room 120, CSE
Office of the Instructor: Room 121, CSE
Marks Division
-
Midsem: 20%
-
Regular Assignments: 30%
-
Endsem: 50%
Text Book:
- Foundations of Algorithms, Jones and Bartlett.
- For advanced topics I shall refer to various other lecture notes which you will not find in textbooks.
Assignments
- Assignment 1 (Contact TA: Satinder)
- Assignment 2 (Contact TA: Jasabanta)
- Assignment 3 (Contact TA: Pranjal/Satinder)
- Assignment 4 (Contact TA: Binny/Tanuj)
- Assignment 5 (Contact TA: Tanuj/Jasabanta)
Tentative semester workplan
Course Outline
- Complexity Analysis (refer textbook)
- Divide-and-Conquer (refer textbook)
- Greedy Algorithms (refer textbook)
- Geometric Algorithms (R1, R2, R3, R4)
- Number theoretic algorithms (refer textbook)
- Sampling and Randomised Algorithms
- Reservoir sampling (Slides, Paper)
- Graph Sampling
- Randomized Quicksort
- Randomized Min Cut
- NP-Completeness (refer textbook)