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


Lectures

  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)  

Tutorial Problems

Tutorial sheet 1   Solns

Refresher problems

Tutorial sheet 2

Minor 1 solns

Tutorial sheet 3

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