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)

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

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

Textbook

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

Grading

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.

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.