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
  1. Midsem: 20%
  2. Regular Assignments: 30%
  3. Endsem: 50%
Text Book:
  1. Foundations of Algorithms, Jones and Bartlett.
  2. For advanced topics I shall refer to various other lecture notes which you will not find in textbooks.
Assignments
  1. Assignment 1 (Contact TA: Satinder)
  2. Assignment 2 (Contact TA: Jasabanta)
  3. Assignment 3 (Contact TA: Pranjal/Satinder)
  4. Assignment 4 (Contact TA: Binny/Tanuj)
  5. Assignment 5 (Contact TA: Tanuj/Jasabanta)
Tentative semester workplan

Course Outline
  1. Complexity Analysis (refer textbook)
  2. Divide-and-Conquer (refer textbook)
  3. Greedy Algorithms (refer textbook)
  4. Geometric Algorithms (R1, R2, R3, R4)
  5. Number theoretic algorithms (refer textbook)
  6. Sampling and Randomised Algorithms
    1. Reservoir sampling (Slides, Paper)
    2. Graph Sampling
    3. Randomized Quicksort
    4. Randomized Min Cut
  7. NP-Completeness (refer textbook)