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) |
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 |
Michael T. Goodrich & Roberto Tamassia,
Data Structures and Algorithms in Java,
Wiley India Edition, Third Edition (required).
Assignments: 25%; Minor (each): 20%; Final: 35%; Class participation, online discussions: extra credit.
There will be five programming assignments due approximately every two weeks.
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.
- The Kyunki Saas Bhi Kabhi Bahu Thi Rule: This rule says that you are free to meet with fellow students(s) and discuss assignments with them. Writing on a board or shared piece of paper is acceptable during the meeting; however, you should not take any written (electronic or otherwise) record away from the meeting. This applies when the assignment is supposed to be an individual effort or whenever two teams discuss common problems they are each encountering (inter-group collaboration). After the meeting, engage in a half hour of mind-numbing activity (like watching an episode of Kyunki Saas Bhi Kabhi Bahu Thi), before starting to work on the assignment. This will assure that you are able to reconstruct what you learned from the meeting, by yourself, using your own brain.
- The Right to Information Rule: To assure that all collaboration is on the level, you must always write the name(s) of your collaborators on your assignment. This also applies when two groups collaborate.