Advanced Design & Analysis of Algorithms (CS5800)

Teaching Group
  • Instructor: Akanksha Agrawal
  • Teaching Assistants: TBD

Course Content
The course will introduce some algorithm design techniques. The main focus will be on formally obtaining correctness of the algorithms and provable runtime guarantees. Along the way, we will learn efficient data structures that will help us obtain improved running times.  A sketch of topics that we intend to cover are as follows (the order may vary):  
  • A gentle introduction to problem definitons and basics of algorithm design. Employing the very basic, and arguably "our" way of dealing with problems---jugaad.
  • Mathematical objects for analyzing the runtime complexity of algorithms/problems. Understanding the difference between runtime complexity of a problem vs. an algorithm.
  • Divide-and-Conquer technique
  • Greedy techniques in designing algorithms
  • Amortized analysis of algorithms
  • Dynamic programming
  • Cuts and network flows
  • Revisiting "Jugaad" and  recognising their implications: a modern approach to reductions and obtaining meaning relationship between problems, complexity classes like P and NP, NP-hardness and (un)decibability.
If time permits, we will visit some frameworks to cope with NP-hardness and possibly look at  some newer conjectures that help up better understand the complexities of problems in the class P and beyond.

Some Practical Information 
  • Tentative Timings:   Monday   10:00-10:50, Tuesday 09:00-09:50, Wednesday 08:00-08:50, and Friday  12:00-12:50 
  • Classroom:   CS36 
  • Attendance requirements:   85%, as mandated by the institute (stringent)
  • We will have a few tutorials to help you learn better

Evaluation Pattern
  • Main Exam: 45% (Tentatively, 08:00 AM - 11:00 AM, 12th Nov.’22)
  • Quizzes (2): 17.5% + 17.5% = 35% (Tentatively, 26th Aug.’22, 28th Sept.’22)
  • Assignments/Short Exams: 20%  (best n-1 out of n)

Reference    Textbooks
  • Introduction to Algorithms, by Cormen, Leiserson, Rivest and Stein
  • Algorithm Design, by Klienberg and Tardos
  • Algorithms, by Papadimitriou, Dasgupta and Vazirani
For materials not available in these textbooks, additional references will be provided,  when required. 

Expectations  Regarding Academic Honesty And Usage of Inclusive Languages​