Design and Analysis of Algorithms

Prof. Sourav Mukhopadhyay

Department of Mathematics

Indian Institute of Technology Kharagpur

Lecture 1 Introduction: Analysis of Algorithms, Insertion Sort, Merge Sort	Lecture 13 Greedy Algorithms, Graphs, Minimum Spanning Trees
Lecture 2 Asymptotic Notation, Recurrences: Substitution, Iteration, Master Method	Lecture 14 Shortest Paths I: Properties, Dijkstra's Algorithm
Lecture 3 Divide and Conquer: Strassen's Algorithm, Fibonacci Numbers	Lecture 15 Shortest Paths II: Bellman-Ford, Topological Sort, DAG Shortest Paths, Linear Programming, Difference Constraints
Lecture 4 Quicksort, Randomized Algorithms Heapsort	Lecture 16 Shortest Paths III: All-pairs Shortest Paths, Dynamic Programming, Matrix Multiplication, Floyd-Warshall, Johnson Lecture 16.3: Breadth First Search (BFS) Lecture 16.3: Depth-First Search (DFS)
Lecture 5 Decision Tree, Linear-time Sorting, Lower Bounds, Counting Sort, Radix Sort	Lecture 17 Computational Geometry: 1D Range Tree, 2D Range Tree, Line-Segment Intersection
Lecture 6 Median, Order Statistics	Lecture 18 Fixed-Universe Successor problem : Van Emde Boas
Lecture 7 Hashing, Hash Functions	Lecture 19 Amortized Algorithms, Table Doubling, Potential Method
Lecture 8 Universal Hashing, Perfect Hashing	Lecture 20 Disjoint-set data structure: Union-Find
Lecture 9 Relation of BSTs to Quicksort, Analysis of Random BST	Lecture 21 Flow networks-I
Lecture 10 Red-black Trees, Rotations, Insertions, Deletions	Lecture 22 Flow networks-II
Lecture 11 Augmenting Data Structures, Dynamic Order Statistics, Interval Trees	Lecture 23 NP-Completeness
Lecture 12 Dynamic Programming, Longest Common Subsequence	Lecture 24 Approximation Algorithms

Recommended text:

1. Cormen, Thomas, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms. 3rd ed. MIT Press, 2009. ISBN: 9780262033848.

2. Computational Geometry - Algorithms and applications" by Mark de Berg, Otfeied Cheong, Marc Van Kreveld and Mark Overmars. 3rd Edition, Springer publisher.

---