COL 702: Advanced data structures and Algorithms
Semester I 2018-2019
Instructor : Sandeep Sen
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)
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
Plagiarism issues and consequences Students are expected to uphold the institute prescribed norms of the honor code. For take-home assignments, published material (including internet) can be referenced but there cannot be any reproduction of the material - it falls under plagiarism. This applies to copying of code and solutions to assignment problems or working in groups and sharing solutions. The penalty for offenders would be loss of at least one grade to semester debarrment as prescribed by the institute disciplinary committee.
For any feedback/corrections regarding notes please send email to me with subject COL702
Lecture 6 (Partition based selection)   Lecture 7 (Binomial heaps)   Lecture 8 (Univ hashing)   Lecture 9 (univ hashing, string sort)   Lecture 10 linear time string sort)   Lecture 11 Potential function & amortizaion
Algorithms by Dasgupta, Papadimitriou and Vazirani, Pub: Tata McGraw-Hill.
The Design and Analysis of Computer Algorithms by Aho, Hopcroft and Ullman, Pub- Addison Wesley (Indian reprint available)
Algorithm Design: by Kleinberg and Tardos,
Low Priced Ed. by Pearson.
Introduction to Algorithms by Cormen, Leiserson and Rivest, Stein, Pub: MIT Press (Indian reprint by Prentice Hall)