This is a core course to get familiarized with the basics of Algorithm Design and Analysis techniques. See here for an earlier offering of the course.

**Instructors**: Prajakta Nimbhorkar (post-midsem) and
Nithin Varma (pre-midsem)

**TAs**: Asif Khan, Nabin Kumar Sahoo, Shankar Ram Vasudevan

**Course Evaluation Policy**: The course will have 2
Homeworks, 2 Quizzes (at the end of first and third month, respectively),
2 Exams (a midsem at the end of the third month and an endsem at the end
of the fourth month). The breakdown of the final grade will be as follows.

*Homeworks*: 5%; *Quizzes*: 15%; *Midsem*:
25 - 30%; *Endsem*: 50 - 55%

**Lectures**: 15:30 to 16:45 on Wednesdays and Fridays;
Lectures will be online on Zoom. The Zoom link is posted on the Moodle
page for the course.

**Course Schedule
**

No. |
Date |
Topic(s)
Covered |
Reference |

1 | 22 Sep 2021 | Introduction,
stable matching algorithm & correctness proof |
KT
Sec. 1.1 |

2 | 24
Sep 2021 |
Notion
of efficient algorithms, word RAM model, asymptotic notation, running time analysis of stable matching algorithm |
KT
Sec 2.1 & 2.2, CLRS Sec 2.2, Slides by Sofya Raskhodnikova (slide 63 onwards) |

3 |
29
Sep 2021 |
Heap
data structure & Heapsort algorithm |
CLRS
Chapter 6 |

4 | 1 Oct 2021 | Quicksort algorithm, proof of correctness & discussion on running time | CLRS Sec 7.1 |

5 | 6 Oct 2021 | Solving recurrence relations | CLRS Sec 4.3, 4.4, 4.5 Reading exercise: CLRS Sec 7.2, 7.4.1 |

6 | 8 Oct 2021 | Omega(n log n) lower bound on the
running time of comparison-based sorting algorithms, Counting sort |
CLRS Sec 8.1, 8.2 |

7 | 13 Oct 2021 | Radix Sort | CLRS Sec 8.3 |

8 | 15 Oct 2021 | Selection in Linear Time | Sec 1.8 from Jeff Erickson's Textbook |

9 | 20 Oct 2021 | Quiz 1 | |

10 | 22 Oct 2021 | Fast Integer Multiplication (Divide
and Conquer Algorithm), Introduction to Dynamic Programming |
Sec 1.9 from Jeff Erickson's book, Sec 15.1 from CLRS |

11 | 27 Oct 2021 | Dynamic programming algorithm for the rod-cutting problem | Sec 15.1 from CLRS |

**References**

*[CLRS]*
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest,
Clifford Stein:

Introduction to Algorithms, 3rd Edition. MIT Press 2009,
ISBN 978-0-262-03384-8, pp. I-XIX, 1-1292

[DPV] Sanjoy Dasgupta,
Christos H. Papadimitriou, Umesh V. Vazirani:

Algorithms. McGraw-Hill
2008, ISBN 978-0-07-352340-8,
pp. I-X, 1-320

Algorithm design. Addison-Wesley 2006, ISBN 978-0-321-37291-8, pp. I-XXIII, 1-838