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 |
|---|---|---|
| 2 Aug, 2023 | Introduction | 01_Introduction.pptx |
| 3 Aug, 2023 | Analysis | 02_Analysis.pptx |
| 10,11,16,17,18 Aug, 2023 | Divide and Conquer, Recursion | 03_Recursion_DAC.pptx |
| 25,30,31 Aug, 2023 | Greedy Algorithms | 04_Greedy.pptx |
| 6,8,13 Sep, 2023 | Dynamic Programming | 05_DP.pptx |
| 15,27,29 Sep, 2023 | Trees | 06_Trees.pptx |
| 4,6 Oct, 2023 | Priority Queues and Heaps | 07_Priority_Queues_Heaps.pptx |
| 6,11,12 Oct, 2023 | Hashing | 08_Hashing.pptx |
| 13,18,19 Oct 2023 3,8,9 Nov, 2022 |
Graphs-I Graphs-II |
09_Graphs_I.pptx 09_Graphs_II.pptx |
owais.iqbal@kgpian.iitkgp.ac.in
aftabh4004@kgpian.iitkgp.ac.in
barmanrahul@kgpian.iitkgp.ac.in
sanimesh005@kgpian.iitkgp.ac.in
adityahirwani@kgpian.iitkgp.ac.in
pranavsonare.sonare@gmail.com
shubhraneel@iitkgp.ac.in
suhasjain@iitkgp.ac.in
debanjansaha@iitkgp.ac.in
monalprasad@iitkgp.ac.in
velpuri.harsha@kgpian.iitkgp.ac.in
