COL106 - Data Structures - Autumn 2017
Tuesday, Thursday, Friday 11-11:50 pm in LH108


Instructor: Mausam
(mausam at cse dot iitd dot ac dot in)
Office hours: by appointment, SIT 402
TAs: (office hours by appointment)

Course Contents

Asymptotic analysis (best case, worst case, average case, expected case, amortized), Linked lists, arrays, linear data structures (stacks, queues), tree data structures (priority queues, binary heaps, disjoint set union find), hashing, binary search trees, multiway search trees, sorting, graphs, shortest paths, minimum spanning trees, introduction to dynamic programming, introduction to approximation algorithms, skip lists.

Schedule

Start End Topics & Lecture Notes Required Readings Additional Resources
Jul 25 Jul 25 Introduction GT Chapter 1

Jul 25 Jul 31 Java Lab
Resources
Aug 1 Aug 3 Asymptotic Analysis & Recursion GT Chapter 3.1-3.4, 4.1
Prefix Averages
Aug 3 Aug 4 Stacks & Amortized Analysis GT Chapter 4.2
Growable Stacks
Aug 4 Aug 11 Practice Assignment 1

Aug 8 Aug 8 Queues GT Chapter 4.3, 4.5

Aug 10 Aug 12 Lists GT Chapter 4.4, 5.1-5.3

Aug 12 Aug 16 Proof Techniques GT Chapter 3.5

Aug 15 Aug 27 Programming Assignment 1
Resources
Aug 18 Aug 25 Practice Assignment 2

Aug 17 Aug 18 Trees I GT Chapter 6.1-6.3

Sep 5 Sep 8 Search Trees GT Chapter 9.1
Tail Recursion
Sep 7 Sep 20 Programming Assignment 2
Resources
Sep 8 Sep 14 AVL Trees GT Chapter 9.2

Sep 15 Sep 21 2-3 & 2-4 Trees GT Chapter 9.4

Sep 26 Sep 26 B Trees GT Chapter 9.6

Sep 26 Oct 24 Programming Assignment 3
Resources
Sep 28 Oct 3 Sorting GT Chapter 10

Oct 10 Oct 11 Heaps GT Chapter 7

Oct 12 Oct 13 Hashing GT Chapter 8.1-8.2

Oct 18 Oct 31 Programming Assignment 4
Resources
Oct 24 Oct 31 Practice Assignment 3

Oct 24 Oct 27 Graphs GT Chapter 12.1-12.4

Oct 31 Nov 2 Djikstra's Algorithm GT Chapter 12.5-12.6

Nov 3 Nov 14 Programming Assignment 5
Resources
Nov 3 Nov 3 Bellman Ford Algorithm Bellman Ford Algorithm

Nov 7 Nov 10 Minimum Spanning Tree & TSP Approximation GT Chapter 12.7, 10.6
Notes 14.1, 14.2, 14.3

Nov 10 Nov 11 Linearity of Expectation & Randomized Quicksort Analysis Notes 1
Notes 2

Nov 11 Nov 14 Skip Lists GT Chapter 8.4


Textbook

Michael T. Goodrich & Roberto Tamassia, Data Structures and Algorithms in Java,
Wiley India Edition, Third Edition (required).

Grading

Assignments: 25%; Minor (each): 20%; Final: 35%; Class participation, online discussions: extra credit.

There will be five programming assignments due approximately every two weeks.

Course Administration and Policies

Cheating Vs. Collaborating Guidelines

As adapted from Dan Weld's guidelines.

Collaboration is a very good thing. On the other hand, cheating is considered a very serious offense. Please don't do it! Concern about cheating creates an unpleasant environment for everyone. If you cheat, you get a zero in the assignment, and additionally you risk losing your position as a student in the department and the institute. The department's policy on cheating is to report any cases to the disciplinary committee. What follows afterwards is not fun.

So how do you draw the line between collaboration and cheating? Here's a reasonable set of ground rules. Failure to understand and follow these rules will constitute cheating, and will be dealt with as per institute guidelines.