• Debjyoti SahaRoy ( Office hrs Wed - 3:30 - 5:30)

The total will be computed as Minors 1 and 2 - 20% each, Major 40%, Quizes - and assignments - 20%.
Two of the best quizes (out of three) will constitute 5% and the rest from the programming and take-home assignments.

Attendence policy Students should abide by the attendence rules stipulated by the Institute. Students failing to meet attendence requirements will be reported for possible penal actions.

Prerequisites: CSL201 (Data Structures) or equivalent Recommended : CSL105 (Discrete Structures)

Contents. Review of basic data structures and their realization in object oriented environment. The following topics will be covered with emphasis on formal analysis and design, Dynamic Data structures; 2-3 trees, Red-black trees, binary heaps, binomial and Fibonacci heaps, Skip lists, universal hashing. Data structures for maintaing ranges, intervals and disjoint sets with applications. Basic algorithmic techniques like dynamic programming and divide- and-conquer, Sorting algorithms with analysis, integer sorting, selection, Graph algorithms like DFS with applications, MSTs and shortest paths.

Lecture Notes

For any feedback/corrections regarding notes please send email to me with subject CSL630

Background Material in Counting and Probability

Lectures

Lecture 7 (randomized selection)   Lecture 8 (Fibonacci nos computation)   Lecture 10 (knapsack,heuristics)   Lecture 11 (matroid/greedy)   Lecture 12 (matroid theorem)  

Lecture 13 (Job scheduling) Lecture 14 (Union Find)   Lecture 15 (Dynamic Programming)   Lecture 16 (Dynamic Programming)   Lecture 17 (Dynamic Programming)

Lecture 18 (Hashing)   Lecture 19 (Hashing)   Lecture 20 (Skip Lists)   Lecture 21 (Skip List analysis)   Lecture 22 (A database query problem)   Lecture 23 (Range Search tree)  

Lecture 24 (rectangular range query)   Lecture 25 (k-d trees)   Lecture 26 (NP class)   Lecture 27 (NP completeness)   Lecture 28 (NPC problems and redn)   Lecture 29 (NPC proofs, approx)  

Tutorial Problems