COL 702: Advanced data structures and Algorithms Semester I 2018-2019 Instructor : Sandeep Sen

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

discussion session: Thu 4:30p - 5:30p ,SIT 001

Teaching Assistants:

• RAKESH RAUSHAN

  office hours Mon 3-5 pm office SIT 308

• AYUSH GUPTA

  office hours Fri 4-6 pm SIT, ICTD Lab (1st floor)

  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.
  
  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.

  Draft preprint

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

  Background Material in Probability

  ---

  Tutorial Problems

  Refresher problems on induction

  Quiz 1

  Problem Set 2

  Quiz 2

  Problem Set 3

  Problem Set 4

  Problem Set 5 (not for submission)

  Lectures

  Lecture 1 (Models and Intro)   Lecture 2 (Finding maximal points)   Lecture 3 (3D maxima: line sweep,data str)   Lecture 4 (Intro to randomized algorithms)   Lecture 5 (Randomized algorithms: monte carlo)  

  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  

  Lecture 12 Skip Lists   Lecture 13 optimization strategies and knapsack   Lecture 14 A greedy framework for Opt   Lecture 15 Matroid thm and appl   Lecture 16 A scheduling problem  

  Lecture 17 Union Find for Kruskal   Lecture 18 Sets using trees and path compr   Lecture 19 Dynamic Prog (Knapsack)   Lecture 20 Dynamic Prog (montonic seq,funapprox)   Lecture 21 Dynamic Prog (Floyd Warshal APSP)   Lecture 22 Shortest Path (Bellman-Ford, Dijkstra)   Lecture 23 DFS,Topological sort   Lecture 24 Strong connectivity, spanners   Lecture 25 Constructing a 3-spanner   Lecture 26 (Polynomial reducibility and NP)   Lecture 27 (NP-Completeness)   Lecture 28 (Parallel algorithms - intro)

  Lectures (previous version)

  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)  

  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