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%
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].
Lecture 9 (14/10/2025) : Line Segment intersections [B4, Ch. 2.1], Huffman coding.
Minor 1 (15/10/2025) : Minor examination!
Lecture 10 (17/10/2025) : Binary search trees, AVL trees.
Lecture 11 (21/10/2025) : Polynomial-time reductions, definition of NP, NP-complete problems [B1, Ch. 8].
Lecture 12 (22/10/2025) : Line Segment intersections : implementation of sweep line algorithm [B4, Ch. 2.1], Longest increasing subsequence.
Lecture 13 (04/11/2025) : Network Flow, Ford-Fulkerson algorithm [B1, Ch. 7.1].
Lecture 14 (07/11/2025) : Bipartite Matching [B1, Ch. 7.5].
Lecture 15 (07/11/2025) : Maximum flow and Minimum cuts [B1, Ch. 7.2], NP hardness of TSP [B1, Ch. 8].
Lecture 16 (11/11/2025) : Perfect matching in bipartite graph: Necessary and Sufficient condition [B1, Ch. 7.5], Randomization in finding the Min-Cut [B1, Ch. 13.2].
Lecture 17 (12/11/2025) : NP hardness of 3-dimensional matching[B1, Ch. 8], Stabbing with line segments [P1], Counting inversions [B1, Ch. 5.3], Integer multiplication [B1, Ch. 5.5].
Lecture 18 (14/11/2025) : Closest pair of points: Divide and Conquer [B1, Ch. 5.4], Hashing [B1, Ch. 13.6, 13.7].
Lecture 19 (14/11/2025) : An approach to algorithmic research, recaps, and wrapping up.
Minor 2 (21/11/2025) : Minor examination!
Major (28/11/2025) : End semester/Major examination!