Design & Analysis of Algorithms (CS2800)

Teaching Group
  • Instructor: Akanksha Agrawal
  • Teaching Assistants: G S Santhosh Raghul  (CS22D406), Mano Prakash P (MA22C024), Ramasamy Kandasamy (CS22M068), Iyer Sreehari Dinesh (CS22M085), Anadi Sharma (CS22M011), Devmalya Roy (CS22M042), Kuna Sharath Kumar (CS23M033), Shubhodeep Chanda (CS23M062), Aditya C (CS20B003), and Bhukya Tharun (CS20B016).
​
Practical Information
  • Classroom:  CS15
  • Timings:   Monday   11:00-11:50, Tuesday 10:00-10:50, Wednesday 09:00-09:50, and Thursday  13:00-13:50 
  • We will have a few tutorials to help you learn better

Course Content
The course will introduce basic techniques used in design and analysis of algorithms. The main focus will be on formally obtaining correctness of the algorithms and provable runtime guarantees. A sketch of topics that we intend to cover are as follows (the order may vary):   
  • Review of asymptotic notations and some basic algorithm design techniques
  • Recursion, solving recurrence relations and Divide-and-Conquer
  • Greedy Algorithms
  • Dynamic programming
  • Basic graph traversal techniques
  • Reductions (or an Indian favorite way, jugaad!) and using them to obtain algorithms and hardness results. Complexity classes like P, NP, and NP-completeness
If time permits we may look at some of the topics like string algorithms, modern conjectures and their roles in refuting algorithms fancier running times and frameworks to cope with NP-hardness.

Evaluation Pattern (Relative Grading)
  • Main Exam:   40% (08:55 AM - 12:00 PM, 10th May’24)
  • Quizzes (2):   15% + 15% = 30% (07:45 AM - 08:50 AM, 26th Feb.’24 and 07:45 AM - 08:50 AM, 25th Mar.’24)
  • Class Tests (2):   10% + 10% (Tentatively, 11:00 AM - 11:50 AM, 05th Feb.’24 and 11:00 - 11:50 AM, 11th Mar.’24)
  • Lecture Scribe (group):   10%

Reference    Textbooks
  • Introduction to Algorithms, by Cormen, Leiserson, Rivest and Stein
  • Algorithm Design, by Klienberg and Tardos
  • Algorithms, by Papadimitriou, Dasgupta and Vazirani
  • Algorithms, by Jeff Erickson
For materials not available in these textbooks, additional references will be provided, when required.  We will upload the lecture material references in the course page. A lot of exercise questions of various difficulty levels are present in the above mentioned textbooks, and you are strongly encouraged to solve them.

Expectations  Regarding Academic Honesty And Usage of Inclusive Languages​