| Course Outline | General Information | Study Material | Lectures (classwise) | Announcements (updated) |
The course consists of 4 lecture hours per week.
The basic thrust of the course would be to study design paradigms for algorithms and their analysis.
We will try to stick to the basic course outline as given in this page, but may deviate a bit.
We would assume in this course that you have undergone the Introduction to Programming and Data Structures and Discrete Mathematics courses and have some knowledge of elementary discrete probability.
| Class Timings: | Tuesday 10:15-12:00, Friday 10:15-12:00 Room No. 525, S. N. Bose Bhavan (Library Building) |
| Exams -- the necessary evil: | Mid-sem: 30, End-sem: 50, Internal evaluation: 20 |
| Books |
(B1) Algorithm Design J. Kleinberg and Eva Tardos Pearson Education (Indian edition) (B2) Introduction to Algorithms T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein Prentice Hall India. (B3) The Design and Analysis of Computer Algorithms A. V. Aho, J. E. Hopcroft and J. D. Ullman Pearson (B4) Algorithms S. Dasgupta, C. Papadimitriou and U. Vazirani Tata McGraw-Hill (B5) Probability and Computing: Randomized Algorithms and Probabilistic Analysis Michael Mitzenmacher and Eli Upfal Cambridge University Press (B6) A First Course in Probability Sheldon Ross Pearson (B7) Computational Geometry: Algorithms and Applications Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars Springer Verlag |
| Web Resources |
(W1)
Lecture Notes by Prof. David Mount (W2) Lecture Notes by Prof. Sandeep Sen (W3) Lecture Notes by Prof. David Mount on Computational Geometry |
| LECTURE DATES | TOPICS | NOTES (pdf) | REFERENCES |
| Lecture 1 (06-01-15) |
Introduction, efficiency of an algorithm,
RAM model of computation, etc. |
- | (B3), (B1), (W2) |
| Lecture 2 (06-01-15) |
Asymptotic notations -- big-Oh, Omega, Theta, small-oh,
Binary search -- algorithm and lower bound |
- | (B2), (W1) |
| Lecture 3 (15-01-15) |
Lower bound for sorting;
selection sort, insertion sort |
- | (B2), (B3) |
| Lecture 4 (16-01-15) |
Heap as a data structure -- insertion, deletion, finding maximum; Heap sort |
- | (B2), (B3), (W1) |
| Lecture 5 (20-01-15) |
Creation of a heap in linear time. Introduction to quicksort -- the idea of recursion tree |
- | (B2), (B3), (W1) |
| Lecture 6 (23-01-15) |
Divide and conquer for sorting -- use of waiting for success bound ; quicksort as an in-place sort; worst case analysis |
- | (B1), (B2), (B3), (W1) |
| Lecture 7 (27-01-15) |
Randomized quicksort; lower bounds for average case |
- | (B3), (B5), (B6) |
| Lecture 8 (03-02-15) |
Randomized quicksort; Randomized selection -- use of waiting for success bound; |
- | (B5), (B6), (B1) |
| Lecture 9 (06-02-15) |
Linear times sorts -- counting sort, radix sort, bucket sort; |
- | (B2), (B3) |
| Lecture 10 (10-02-15) |
Lower bound on sorting for average case; Selection (median finding) -- worst case linear time; |
- | (B2), (B3) |
| Lecture 11 (12-02-15) |
Dynamic Programming -- Fibonacci number, Longest Common Subsequence, Matrix Chain Multiplication |
- | (B2), (B3) |
| Class Test I (17-02-15) |
-- | -- | -- |
| Lecture 12 (20-02-15) |
Discussion on Class Test I Dynamic Programming -- Knapsack |
- | (B2), (B3) |
| Exam (27-02-15) |
Mid Semestral Exam |
Solution sketch | - |
| Lecture 13 (03-03-15) |
Computational Geometry: Area of polygon; Polygon triangulation; Convex hull - Jarvis March, Graham's scan. |
- | (W3), (B7), (B2) |
| Lecture 14 (13-03-15) |
Computational Geometry: Convex hull - Graham's scan proof of correctness. Lower bound of convex hull Output sensitive algorithm for convex hull (Chan's algorithm) |
- | (W3), (B7), (B2) |
| Lecture 15 (17-03-2015) |
Computational Geometry: Output sensitive algorithm for convex hull (Chan's algorithm) Closest Pair and farthest pair in 2D |
- | (W3), (B2) |
| Lecture 16 (20-03-2015) |
Balanced Binary Search Tree -- AVL tree; Tree as a graph and its properties; Euler's formula for connected planar graphs |
- | (W3), (B2) |
| Lecture 17 (24-03-2015) |
Computational Geometry: Voronoi diagram and its properties Delaunay triangulation as a dual of Voronoi diagram |
- | (W3), (B7) |
| Lecture 18 (27-03-2015) |
Computational Geometry: Voronoi diagram and its properties Delaunay triangulation as a dual of Voronoi diagram |
- | (W3), (B7) |
| Lecture 19 (31-03-2015) |
Another application of plane sweep: line segment intersection Shortest path in (un)directed graphs: Dijkstra's algorithm |
- - |
(W3), (B7) (B2), (B3) |
| Lecture 20 (06-04-2015) |
Dijkstra's algorithm; Paths and matrix multiplication; All pair shortest path; |
- | (W1), (B2), (B3) |
| Lecture 21 (07-04-2015) |
Minimum spanning tree -- Prim's and Kruskal's algorithm; |
- | (W1), (B2), (B3) |
| Lecture 22 (08-04-2015) |
Proof of correctness of Prim's and
Kruskal's algorithm; Pre-order, In-order and Post-order traversal of binary tree; Breadth first search of (un)directed graph; |
- | (W1), (B2), (B3) |