COL106 - Data Structures - Spring 2021 Tuesday, Thursday, Friday 11-11:50 pm in Teams 1 Tuesday, Friday 3:30-4:50 pm in Teams 2 |
Instructor:
Mausam
Amit Kumar
(mausam at cse dot iitd dot ac dot in) (amitk at cse dot iitd dot ac dot in) Office hours: by appointment |
TAs: (office hours by appointment) |
Week | Topics & Lecture Notes | Required Readings | Additional Resources |
---|---|---|---|
1 | Introduction | GT Chapter 1 |
|
1-2 | Java Lab |
Resources |
|
1 | Asymptotic Analysis | GT Chapter 4.1-4.3 |
Prefix Averages |
2 | Arrays & Linked Lists | GT Chapter 3 |
|
2-3 | Stacks & Amortized Analysis | GT Chapter 6.1 |
Growable Stacks |
3 | Queues | GT Chapter 6.2-6.3 |
|
3 | Recursion | GT Chapter 5 |
|
4-5 | Programming Assignment 1 |
Resources |
|
4 | Trees | GT Chapter 8 |
|
4-5 | Search Trees | GT Chapter 11.1 |
|
Self Study | Proof Techniques | GT Chapter 4.4 |
|
5 | AVL Trees | GT Chapter 11.2-11.3 |
|
6-7 | Programming Assignment 2 |
Resources |
|
6 | 2-4 & B-Trees | GT Chapter 11.5, 15.3 |
|
7 | Heaps | GT Chapter 9 |
|
7 | Tries | GT Chapter 13.3 |
|
8-9 | Programming Assignment 3 |
Resources |
|
8 | Sorting | GT Chapter 12.1-12.4 |
|
9 | Hashing | GT Chapter 10.1-10.2 |
|
9-10 | Linearity of Expectation & Skip Lists | GT Chapter 10.4 Notes |
|
10-11 | Programming Assignment 4 |
Resources |
|
10 | Graphs & Search Algorithms | GT Chapter 14.1-14.3 |
|
11 | DFS in Directed Graphs | GT Chapter 14.5 |
|
11 | Djikstra's Algorithm | GT Chapter 14.6 |
|
12 | Minimum Spanning Tree | GT Chapter 14.7.2 |
|
13 | Programming Assignment 5 |
Resources |
Michael T. Goodrich, Roberto Tamassia & Michael H. Goldwasser,
Data Structures and Algorithms in Java,
Wiley India Edition, Sixth Edition (required).
Assignments: 26%; Minor: 25%; Final: 35%; Quizzes: 14%; Class participation, online discussions: extra credit.
There will be four programming assignments due approximately every two weeks, each worth 6% marks. Java lab will be worth 2% marks.
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.