Course Outline : This is an advanced course on algorithms. A prior exposure to algorithms is expected. The syllabus remains similar to any classical algorithms course with a focus on some advanced topics.
Course Instructor : Dr. Arun Kumar Das, SCIS
Teaching Assistants:
Venue: LHC1-R1
Timings : Tuesday 11 AM - 1 PM, Friday 11 AM - 1 PM
Grading policy : Minor (Mid Sem) - 40%, Major (End Sem) - 60%
Reference Materials : [B1] Algorithm Design by John Kleinberg & Eva Tardos.
[B2] Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani.
Lecture 1 (29/08/2025) : Course outline and Introduction. Contention Resolution : Probability and Randomization [B1, Ch. 13.1].
Lecture 2 (02/09/2025) : Median finding, Selection sort, Quick sort: The idea of partitioning, Expectation of random variables [B1, Ch. 13.3].
Lecture 3 (09/09/2025) : Analysis of the expected running time of randomized median finding and quick sort [B1, Ch. 13.5], Lower bound of comparison based sorting [B3, Ch. 8.1], Finding median in deterministic linear time [B3, Ch. 9.3], Counting sort [B3, Ch. 8.2].
Lecture 4 (12/09/2025) : Radix sort, Bucket sort [B3, Ch. 8], Convex hull : Graham's scan [B4, Ch. 1].
Lecture 5 (16/09/2025) : Paths in graphs, BFS and shortest paths, Dijkstra's SSSP, usage of Heaps and Priority queues [B2, Ch. 4].
Lecture 6 (23/09/2025) : Greedy vs Dynamic: Interval scheduling : unweighted [B1, Ch. 4.1] and weighted [B1, Ch. 6.1] cases.
Lecture 7 (26/09/2025) : Greedy algorithms: All interval Scheduling [B1, Ch. 4.1], Minimum Spanning Tree and Kruskal's algorithm [B1, Ch. 4.5].
Lecture 8 (30/09/2025) : Implementation of Kruskal's algorithm: Union-Find in disjoint sets, Prims algorithm[B1, Ch. 4.6; B2, Ch.5.1].