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