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




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


Lecture 12

Dynamic Programming, Longest Common Subsequence

Lecture 24


Approximation Algorithms





Links to relevant web sites:

1.    6.046 Introduction to Algorithms Homepages - courses

2.    Introduction to Algorithms (SMA 5503) - MIT OpenCourseWare

3.    Introduction to Algorithms - MIT OpenCourseWare


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.