The course consists of two lectures per week. The goal of the course would be to study design paradigms for algorithms and their analysis. The basic course outline is as given in this page, but it may deviate a bit. Some familiarity about basics of programming and some basic data structures will be assumed.
| Old Class Timing: | Tuesday 16:15-18:00, Thursday 16:15-18:00 Room No. 715, Main Building |
| Updated Class Timing: | Tuesday 16:15-18:00, Wednesday 9:30-11:15 (from 28.08.2024) ACMU Seminar Room, 6th Floor, PJA Building |
| Exams: | Mid-sem: 30, End-sem: 50, Internal evaluation: 20 |
| Books |
(B1) Algorithms Illuminated Part 1-4 Tim Roughgarden Cambridge University Press. (B2) Introduction to Algorithms T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein Prentice Hall India. (B3) Algorithm Design J. Kleinberg and Eva Tardos Pearson Education (Indian edition). (B4) The Design and Analysis of Computer Algorithms A. V. Aho, J. E. Hopcroft and J. D. Ullman Pearson. (B5) Algorithms S. Dasgupta, C. Papadimitriou and U. Vazirani Tata McGraw-Hill (B6) The Art of Computer Programming, Vol. 1-4A D. E. Knuth Addison-Wesley. |
| LECTURE DATES | LECTURER | TOPICS and REFERENCES | NOTES (pdf) |
| Lecture 1 (30.07.2024) |
Anupa | Introduction, RAM Model of computation, Efficiency of computation, Time complexity, computing Fibonacci sequence. -- [(B2 : Chapter 1 & 2),(B5 : Chapter 0 (prologue))] |
- |
| Lecture 2 (01.08.2024) |
Anupa | Worst case analysis, Asymptotic notation -- [(B2), (B5)] | - |
| Lecture 3 (06.08.2024) |
Anupa | Searching algorithm: Binary search -- [(B2)]
Sorting Algorithm: Insertion Sort -- [(B2)] |
- |
| Lecture 4 (08.08.2024) |
Abhranil | Design paradigm: Divide-and-Conquer algorithms and recursion -- [(B1), (B2)]
Analysis of Mergesort algorithm -- [(B1), (B2)] Analysis of Quicksort algorithm -- [(B1), (B2)] Role of choosing pivot -- [(B2)] |
- |
| Lecture 5 (13.08.2024) |
Abhranil | Revisiting Divide-and-Conquer: Mergesort and Quicksort
Median finding in linear time -- [(B2)] Lower bound for comparison based sorting -- [(B2)] Divide-and-Conquer: Integer Multiplication -- [(B1), (B2), (B6)] |
- |
| Lecture - (15.08.2024) |
- | Institute holiday: no class | - |
| Lecture 6 (20.08.2024) |
Abhranil | Divide-and-Conquer: Integer Multiplication -- [(B1), (B2), (B6)]
Karatsuba Algorithm -- [(B2), (B6)] Toom-Cook Multiplication -- [(B6)] Strassen's Matrix Multiplication Algorithm -- [(B1), (B2)] |
- |
| Lecture 7 (22.08.2024) |
Abhranil | Revisiting Integer Multipication
Fast Fourier Transform (FFT) -- [(B2), (B6)] |
link |
| Lecture 8 (27.08.2024) |
Abhranil | Polynomial Multiplication using FFT [(B2), (B6)] Solving recurrences: Proof of Master Theorem [(B1)] |
- |
| Lecture 9 (28.08.2024) |
Abhranil | How to prove the correctness of an algorithm? [(B1), (B2)] Proof of correctness of Quicksort algorithm [(B1)] |
- |
| Lecture 10 (03.09.2024) |
Abhranil | Introducing data structures, Table doubling - amortized cost analysis Heap data structure, Heapsort <(B1)> |
- |
| Lecture - (04.09.2024) |
- | Class cancelled | - |
| Lecture - (10.09.2024) |
- | Mid-term week: no class | - |
| Lecture - (11.09.2024) |
- | Mid-term week: no class | - |