This course is an advanced form of an introductory algorithms course, and is meant to have a thorough grounding in core Algorithms required for pursuing PG degree in Computer Science. The course covers topics such as asymptotic notation, recurrence relation, graph algorithms, heaps, dynamic programming, greedy algorithms, divide and conquer, NP-completeness where the undergraduate contents of each topic is first reviewed in a fast-paced manner, and is followed by some advanced content.

- Undergraduate Algorithms course

Open only to M.Tech. and Ph.D. students (recommended for students with inadequate background in Algorithms).

1. The student is able to design and analyse algorithms using techniques like divide and conquer, greedy and dynamic programming.

2. The student is able to use standard data structures like heaps, trees and graphs for designing algorithms.

3. The student is able to prove NP-completeness of problems using reductions.

4. The student is familiar with modern techniques to handle intractable problems like randomization, approximation, backtracking search.

Evaluation will be based on in-class short online quizzes (to be taken during lectures and tutorials), group homeworks, closed-book online proctored midsem and endsem exams. We will follow a flexible policy to let students focus more on exams or homeworks, as per their choice.

The following algorithm will be used to calculate your cumulative score.

**QUIZ =**sum of 8 highest quiz percentages x 0.025**HWNum =**number of submitted homeworks**HWCount =**max ( min(HWNum, 10), 4)**HW =**sum of HWCount highest homework percentages x 0.025- Once
**turned-in**a homework cannot be retracted. And if a homework is**not turned-in**on Google Classroom ("turn-in" is a separate explicit step) then it will be considered not submitted. Both partners of a group homework gets the same score. If 1 person of a group does not want to submit a homework, it can be done by not writing the name of that individual on the homework sheet. You are free to submit and unsubmit as many times as you want BEFORE the deadline. We only care about the status once the deadline is over. For homework problems, you can say "I don't know" for any partial question (for which some point/mark is mentioned) or for the entire question and you will be awarded 20% of the points allotted to that question. However, your__I don't know policy :____submission will be counted__(so if you submit "I don't know" for ALL homeworks it may hurt your score as compared to not submitting anything at all). So my suggestion for you is to make use of this scheme sparingly.

- Once
**scale =**HWCount x 0.025**MID =**(0.8 - scale) x midsem percentage / 3**END =**2 x (0.8 - scale) x endsem percentage / 3**CUMULATIVE (%) =**QUIZ + HW + MID + END

Quizzes during lectures will happen via Google Forms from 9:00 to 9:15am and will be announced on Classroom at 9:00am. Submission window closes at 9:18am to allow network issue and server load.

Google servers often take some to accept Google Form submissions, and there are network related latency issues as well. If you try to submit at 9:16am, you may miss the deadline due to such issues. Do so at your own risk. Quizzes during tutorials will happen in the same manner but start at 2:30pm.

All office hours will take place on the Meet Link given on Classroom.

**Debajyoti Bera -** dbera@ - Monday 4-5pm (email me if you want meet at some other time)

**Suryendu Dalal** - suryendud@ - Monday 6-7pm

None - Tuesday

**Himanshu Singh** - himanshu17291@ - Wednesday 5-6pm

**Suryendu Dalal** - suryendud@ - Thursday 7pm (review sessions, only for interested students)

**Tapadeep Chakraborty** - tapadeep20017@ - Friday 3:30-4:30pm

**Rishi Sharma - **rishi17260@ - Saturday 4-5pm

None - Sunday

Students who want to discuss doubts, ask questions, pose problems, cross check ideas, share additional resources may want to sign up on the slack channel mentioned on Classroom (**Important**: Use your @iiitd.ac.in email address to sign up.) . All the TAs are available on the channel, so some TA will respond to your query within a few days. Students are also encouraged to respond to one another. Many courses use slack channel for student-TA academic discussions -- you too may find it useful.

*Joining the channel is not compulsory. Please understand that this is an informal mode of group discussion and I am not on this channel.*

- Lectures
Lec 0
- Recursive and divide-and-conquer algorithms: Lec 1 Lec 2 Lec 3 Lec 4 Lec 5 (FFT)
- Backtracking algorithms: Lec 6 Lec 7
- Dynamic programming Lec 8 Lec 9 Lec 10 Lec 11
- Graph algorithms Lec 12 Lec 13 Lec 14
- NP completeness Lec 17 Lec 18 Lec 19 Lec 20
- Approximation algorithm Lec 21 Lec 22 Lec 23 Lec 24 Lec 25
- Data structures Lec 15 Lec 16

- Tutorials Tutorial 1 Tutorial 2 Tutorial 3 Tutorial 4 Tutorial 5 Tutorial 6 Tutorial 7 Tutorial 8 Tutorial 9 Tutorial 10 Tutorial 11 Tutorial 12 Tutorial 13
- Homeworks HW1 HW2 HW3 HW4 HW5 HW6 HW7 HW8 HW9 HW10 HW11