COL 702: Advanced data structures and Algorithms

Semester I 2017-2018

Instructor : Sandeep Sen

Lectures: M,Th 8 - 9:20 , Venue IIA 101

Office hours: Mon 9:30a - 10:30a

Teaching Assistants:

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 COL702

Background Material in Counting and Probability


  Lecture 2 (Shortest path )   Lecture 3 (Shortest path cont)   Lecture 4 (Binomial Heaps)   Lecture 5 (Bin Heaps and amortized ds)   Lecture 6 (Potential function and amortized analysis)   Lecture 7 (Randomized selection)
Lecture 8 (Deterministic selection)   Lecture 9 (String sorting)   Lecture 10 (String sorting contd)   Lecture 11 (Optimization and Greedy)   Lecture 12 (Matroid theorem and MST)   Lecture 13 (A scheduling problem)
Lecture 14 (Greedy approx, Union Find)   Lecture 15 (Union Find using trees)   Lecture 16 (Knapsack using Dyn Prog)   Lecture 16b (Dynamic Prog: Longest increasing subseq)   Lecture 17 (Dyn Prog contd : Parsing)
Lecture 18 (Dyn Prog contd : Function compression)   Lecture 19 (Universal Hash function)   Lecture 20 (Skip Lists)   Lecture 21 (Orthogonal range search)   Lecture 22 (range search trees)   Lecture 23 (Convex hull)  
Lecture 24 (Planar Point location)   Lecture 26 (Polynomial reducibility and NP)   Lecture 27 and 28 (Proving NP Completeness)  

Tutorial Problems

Tutorial sheet 1   Solns

Refresher problems

Tutorial sheet 2

Minor 1 solns

Tutorial sheet 3

Minor 2 solns

Tutorial sheet 4

Tutorial sheet 5

Major exam solutions

Reference books

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)

Sandeep Sen
Last modified: Mon July 23 2012