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 | - |
| Lecture 11 (18.09.2024) |
Abhranil | Quick overview of some data structures, Enumerating all the solutions, Introduction to dynamic programming: a template [(B1)] | link |
| Lecture 12 (19.09.2024) |
Abhranil | Dynamic programming: Fibonacci number, WIS for path graphs, rod cutting, LCS [(B1), (B2)] | - |
| Lecture 13 (24.09.2024) |
Abhranil | More dynamic programming: Iterated Matrix Multiplication, Longest Increasing Subsequence, Arithmetic Parenthesization, Knapsack Problem [(B1), (B2)] | - |
| Lecture 14 (26.09.2024) |
Uddalok | Graphs, representation, Depth First Search and applications [(B5), (B1)] | - |
| Lecture - (01.10.2024) |
- | First Class-test | - |
| Lecture - (02.10.2024) |
- | Institute holiday: no class | - |
| Lecture 15 (03.10.2024) extra class |
Abhranil | Discussion of the mid-term and class-test question papers, Introduction to BFS | - |
| Lecture - (08.10.2024) |
- | Holiday | - |
| Lecture - (09.10.2024) |
- | Holiday | - |
| Lecture 16 (15.10.2024) |
Anupa | Breadth First Search, Dijkstra's algorithm [B5] | - |
| Lecture 17 (17.10.2024) |
Anupa | Correctness of Dijkstra's algorithm, Bellman-Ford algorithm [(B2), (B5)] | - |
| Lecture 18 (22.10.2024) |
Abhranil | Introduction to greedy algorithms, compare with DP, Minimum spanning tree: properties, Prim's algorithm [(B1), (B5)] | - |
| Lecture - (23.10.2024) |
Abhranil | Class Cancelled | - |
| Lecture 19 (29.10.2024) |
Anupa | Revisit Prim's algorithm, Kruskal's algorithm, Proof of correctness [(B1), (B5)] | - |
| Lecture - (30.10.2024) |
Anupa | No Class | - |
| Lecture 20 (05.11.2024) |
Abhranil | Introduction to LP, Network flow problem, Reduction: algorithm design paradigm, Complexity [(B1), (B2)] | - |
| Lecture 21 (06.11.2024) |
Abhranil | Complexity classes, NP-hardness, Proof of NP-hardness [(B1), (B2)] | - |
| Lecture 22 (07.11.2024) extra class |
Abhranil | More proofs of NP-hardness, Algorithm for NP-hard problems [(B1)] | - |