Design & Analysis of Algorithms (CS2800)
Teaching Group
Practical Information
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):
Evaluation Pattern (Relative Grading)
Reference Textbooks
Expectations Regarding Academic Honesty And Usage of Inclusive Languages
- 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
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
Expectations Regarding Academic Honesty And Usage of Inclusive Languages