IIT KGP Logo

Partha Bhowmick
 Department of Computer Science and Engineering
Indian Institute of Technology
Kharagpur

Home
Teaching
Research
Publications
Profile
Miscellany
 Faculty Advisorship: MTech 2010-2012

Current Course (intinno)
Algorithms I (CS21003 & 29003: Autumn 2010)
Theory: CSE Class Room 119: Wed 9:30(1); Thu 8:30(1); Fri 10:30(2).
1st Theory Class: 22/7/10 - 8:30am, Room 119.
Lab: Computer Center Lab: Tue 13:30(3).
Roll list

Teaching Assistants
  1. Kapil Bari
  2. Alok Kumar Yadav
  3. Sushant Gupta
  4. Saurabh Goyal
  5. Geet Garg
  6. Atul Gupta
    Group Email

Books
  1. Text Book: Introduction to Algorithms. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Prentice Hall of India.
  2. Data Structures and Program Design in C. R.L. Kruse, B.P. Leung, C.L. Tondo. PHI.
  3. Algorithm Design. M.T. Goodrich and R. Tamassia. Wiley Student Edition.
  4. Computer Algorithms. E. Horowitz, S. Sahni, and S. Rajasckaran. (Indian edition)
  5. The Art of Computer Programming (TAOCP). Donald E. Knuth. Addison-Wesley.
  6. Introduction to Algorithms: A Creative Approach. Udi Manber. Addison Wesley.
  7. Algorithm Design. J Kleinberg and E. Tardos. Pearson Education.
  8. Algorithms: Design Techniques and Analysis. M. H. Alsuwaiyel. World Scientific.
  9. Computational Geometry - Algorithms and Applications. M. De Berg, M. Kreveld, M. Overmars, O. Schwarzkopf.
  10. The Design and Analysis of Computer Algorithms. A. V. Aho, J. E. Hopcroft and J. D. Ullman. Addison Wesley.
  11. Computer Algorithms: Introduction to Design and Analysis. S. Baase. Addison Wesley.
  12. Randomized Algorithms. Rajeev Motwani and Prabhakar Raghavan. Cambridge University Press.

Other Resources
  1. Professor David Mount's lecture notes
  2. Professor Sandeep Sen's lecture notes

Assignments
1. Assignment 1 20/07/10—02/08/10 TA: Kapil Bari
2. Assignment 2 03/08/10—11/08/10 TA: Geet Garg
3. Assignment 3 10/08/10—30/08/10 TA: Atul Gupta
4. Lab Test 31/08/10 TA: Sushant Gupta
4. Assignment 4 07/09/10—30/09/10 TA: Saurabh Goyal


Lectures
01. L01 22/07/10 Finding minimum, maximum, 2nd max. Goodness/efficiency of an algorithm. text book
02. L02-03 23/07/10 Finding maximum and minimum simultaneously. Order Statistics: Finding i th max by partitioning (Best case, worst case, hints on worst case). text book
03. L04 28/07/10 Order notations. Definitions and examples. Recurrence equations and their solutions. Method of Iteration and time complexity of merge sort.
Exe: Why is 2kO(n/2k) = O(n) justifiable, and does provide an asymptotic tight bound of the time complexity of merge sort?		 text book
04. L05 29/07/10 Method of Substitution and time complexity of merge sort (with floor and ceiling values of split array-sizes).
Exe: Can we prove T(n)=O(n logn) with the hypothesis T(k) ≤ ck logk ?  Yes! 		text book + class note
05. L06-07 30/07/10 Method of Recursion Tree and time complexity of merge sort. Master Method and examples. Average-case time complexity of finding i th max by randomized partitioning.
Exe: Prove that for merge sort, T(n)=Ω(n logn). 		text book + class note
06. L08 04/08/10 Finding i th max by grouping and with the pivot of partitioning as the median of medians.
Exe: How does the algorithm behave when group-size is less or larger than 5? What's the change in T(n)? 		text book + class note
07. L09 05/08/10 Continuation of last lecture. Worst-case analysis: T(n)=O(n).
Exe: In Assignment 1, what's the time complexity of getting A' from the very input matrix? 		text book + class note
08. L10-11 06/08/10 Searching: Linear search: Best-case, worst-case, and average-case analysis for successful and unsuccessful searching.
Binary search: Best-case, worst-case, and average-case analysis for successful and unsuccessful searching.
BST: Insertion and deletion of nodes, and their time-complexity analysis. Notion of dummy nodes, and internal and external path lengths. Best-case, worst-case, and average-case analysis for successful and unsuccessful searching.
Exe: Justify why Sn = (U0+U1+...+Un-1)/n  + 1. 		text book
+ Book 2 (by Kruse et al.) + class note
09. L12 11/08/10 Height-balanced and weight-balanced search trees. Why dynamic height balancing? AVL tree: Definition, examples, single rotations.
Exe: Derive the explanation of L-rotation from the analogy of R-rotation. 		text book
+ Book 2 (by Kruse et al.) + class note
10. L13-14 13/08/10 AVL tree: Double rotations—Why and how. Time complexities for searching, insertion, deletion.
Exe: Give examples where rotation is required several times (i.e., O(logn)) after insertion and after deletion. 		text book
+ Book 2 (by Kruse et al.) + class note
11. L15 19/08/10 Worst-case structure of AVL trees; solving the Fibonacci recurrence; notion of golden ratio and Fibonacci trees.
Special class on advanced C programming and debugging (5:30pm-7:30pm). 		text book
+ Book 2 (by Kruse et al.) + class note
12. L16-17 20/08/10 Sorting. Insertion sort: Principle, demo, best-, worst, and average-case time complexities.
Quicksort: Principle, demo, best-, worst, and average-case time complexities. 		text book + class note
13. L18 25/08/10 Quicksort: The tricky derivation of average-case time complexity. Full binary tree. Complete binary tree. Heap. text book + class note
14. L19 26/08/10 Heap sort and its time complexity with O(n log n) time complexity of BuildHeap. text book + class note
15. L20-21 27/08/10 Tricky proof for O(n) time complexity of BuildHeap.
Comparison sorts: Why Ω(n log n)?  Linear-time sorting algorithms. Principles of Radix sort, Counting sort, Bucket sort.
Graphs: Definitions and examples; representations of directed, undirected, and weighted graphs.

Selected Lecture Notes (Searching & Sorting)
text book + class note
31/09/10 Lab Test 1
 text book + class note
16. L22 01/09/10 Breadth First Search (BFS).
Exe: Suggest an algorithm and explain its time complexity to find the diameter of an undirected graph, G. (Diameter is defined as the maximum of the shortest path lengths over all vertex pairs of G.)
text book + class note
17. L23 02/09/10 Depth First Search (DFS): Principle, demo, algorithm, time complexity.
 text book + class note
18. L24-25 03/09/10 Depth First Search (DFS): Edge classification for directed and undirected graphs; Theorem on time intervals, colors, and descendants; White path theorem; Detecting cycles.
 text book + class note
19. L26 08/09/10 Topological sort.
 text book + class note
20. L27 09/09/10 Strongly connected components.
 text book + class note
21. L28-29 10/09/10 Revision.
22. L30 22/09/10 Minimum Spanning Tree. Notion of crossing edges and light edge(s). Greedy approach. Kruskal's Algorithm.
 text book + class note
23. L31 23/09/10 Minimum Spanning Tree. Prim's Algorithm and its greedy nature.
 text book + class note
24. L32-33 24/09/10 Shortest Path problems. Single-source shortest paths by Dijkstra's Algorithm.
 text book + class note
25. L34 29/09/10 Diameter of an undirected graph, G.
Diametric path(s) and related issues (Assignment 4).
Characterizing a diametric path by its farthest and nearest vertices from G.
 text book + class note
26. L35 30/09/10 Discussions.
 text book + class note
27. L36-37 01/10/10 String matching. Prefix function and KMP algorithm.
 text book + class note
28. L38 06/10/10 KMP algorithm: Demo and time complexity.
 text book + class note
29. L39 07/10/10 Dynamic Programming (DP). Elements of DP (Optimal substructure & Overlapping subproblems) and examples. Difference of DP with Greedy approach.
 text book + class note
30. L40-41 08/10/10 Definition of Longest Common Subsequence (LCS). How LCS problem satisfies DP elements. LCS algorithm; time & space complexities. Difference between longest common substring and longest common subsequence. Notion of edit distance, hamming distance, etc.
 text book + class note
31. L42 20/10/10 Problem of Matrix-chain Multiplication, its exponential counting possibilities, elements of DP, and the recurrence for m(i,j).
 text book + class note
32. L43 21/10/10 Matrix-chain Multiplication: Demo and time complexity.
 text book + class note
33. L44 27/10/10 0-1 Knapsack Problem and its DP recurrence.
 Goodrich & Tamassia + class note
34. L45 28/10/10 0-1 Knapsack Problem: DP Algorithm, demo, time complexity.
Exe: Fractional Knapsack Problem; Denomination Problem.		 Goodrich & Tamassia + class note
34. L46-47 29/10/10 Convex hull: Definition, examples, observations; Jarvis march.
 text book + class note
35. L48-50 30/10/10 (Compensatory class) Graham scan and time complexity; Divide-and-conquer approach, its time complexity; other algorithms. Closest pair in a 2D point set: Divide-and-conquer approach.

Selected Lecture Notes (up to geometry) 		text book + Computational Geometry: M. De Berg et al. + class note
36. L51 03/11/10 Closest pair in a 2D point set: Divide-and-conquer approach.

Selected Lecture Notes (up to geometry) 		text book + Computational Geometry: M. De Berg et al. + class note
37. L52 04/11/10 Strassen's Matrix Multiplication. text book + class note
38,39. L52-53 10,11/11/10 Hashing.

Selected Lecture Notes (hashing methods included) 		text book + class note


Recent Courses
  • Computer Graphics: CS43302 (Spring 2010)
  • Design and Analysis of Algorithms (Autumn 2009)
  • Computer Graphics: CS43302 (Spring 2009)
  • Design and Analysis of Algorithms (Autumn 2008)
Other Courses
  • Programming and Data Structures
  • Computational Geometry
  • Digital Image Processing
  • Pattern Recognition
  • Information and Coding Theory