Asymptotic notations and their significance, introduction to RAM model of computation, complexity analysis of algorithms, worst case and average case.
Basic introduction to algorithmic paradigms like divide and conquer, recursion, greedy, etc.
Searching: binary search trees, balanced binary search trees, AVL trees and red-black trees, B-trees, skip lists, hashing.
Priority queues, heaps, Interval trees, tries.
Order statistics.
Sorting: comparison based sorting - quick sort, heap sort, merge sort: worst and average case analysis.
Decision tree model and (worst case) lower bound on sorting.
Sorting in linear time - radix sort, bucket sort, counting sort, etc.
String matching.
Graph Algorithms: BFS, DFS, connected components, topological sort, minimum spanning trees, shortest paths - single source and all pairs.
| Date | Topic | Course Materials |
|---|---|---|
| 3 Aug, 2022 | Introduction | 01_Introduction.pptx |
| 4,5 Aug, 2022 | Analysis | 02_Analysis.pptx |
| 10,11,12,17,24,25 Aug, 2022 | Recursion Divide and Conquer | 03_Recursion_DAC.pptx |
| 26,31 Aug, 1 Sep, 2022 | Greedy Algorithms | 04_Greedy.pptx |
| 2,7,8 Sep, 2022 | Dynamic Programming | 05_DP.pptx suitcase.py suitcase_DP.py |
| 9,14,15,16 Sep, 2022 | Trees | 06_Trees.pptx bst.c randperm.txt avl.c |
| 12,13 Oct, 2022 | Priority Queues and Heaps | 07_Priority_Queues_Heaps.pptx |
| 14,19 Oct, 2022 | Hashing | 08_Hashing.pptx |
| 21,26,27,28 Oct, 2022 2,3,4 Nov, 2022 |
Graphs Graphs-II |
09_Graphs.pptx 09_Graphs_II.pptx |
owais.iqbal@kgpian.iitkgp.ac.in
ashik.khan@kgpian.iitkgp.ac.in
kusumakarvijay@kgpian.iitkgp.ac.in
gourashish162@iitkgp.ac.in
sanimesh005@kgpian.iitkgp.ac.in
mrprinceraj71097@kgpian.iitkgp.ac.in
udayabhaskar2001@iitkgp.ac.in
sumitkumar18cs@iitkgp.ac.in
topper1116@iitkgp.ac.in
pankajkagr@iitkgp.ac.in
barmanrahul@kgpian.iitkgp.ac.in
