COL 206 : Data-structures

Instructor

Amit Kumar
Office : Room # 417, Bharti Building
Email : amitk@cse.iitd.ac.in
Phone : (ext) 1286.

Announcements

Teaching assistants to contact in case of assignment (or coding) related queries:
Saket Dingliwal (cs1150254@cse.iitd.ac.in), Office hour: Monday, 4-5 pm
Kacham Praneeth(cs1150600@cse.iitd.ac.in), Office hour: Thursday 4-5pm
Venue for office hours: GCL (General Computing Lab), 5th floor, Bharti building.

Class Timings

Slot F, Tuesday, Thursday, Friday : 11am-12 noon.

Assignments

Assignemnt 1 , due date is 30th January.
Assignemnt 2 , due date is 17th February.
Assignemnt 3 , due date is 12th March.
Assignemnt 4 , due date is 31st March.
Assignemnt 5 , due date is 15th April.

All homeworks must be submitted through moodle. There is no late submission policy.

Lecture Topics

Lecture 1: Introduction to the course
Lecture 2: Notion of data-structures and algorithms, running time
Lecture 3: Time complexity, O(), Ώ(), Θ() notation
Lecture 4: Quick Tour of Java
Lecture 5: More JAVA essentials, Linked lists.
Lecture 6: Doubly linked lists, Stacks
Lecture 7: Stacks, Matching Paranthesis, Quiz.
Lecture 8: More applications of Stacks, Implementation of Stacks
Lecture 9: Growable arrays, Queues, Implementation using circular arrays
Lecture 10: Trees, basic notations and implementations.
Lecture 11: Tree traversals and applications, binary trees.
Lecture 12: Dictionary ADT, Binary Search, Comparison Model Lower Bound on Search
Lecture 13: Binary Search Trees, Inserting a key in BST.
Lecture 14: Deleting a key from BST, notion of Balanced BST.
Lecture 15: AVL Trees, height balanced property, insertion in AVL Tree
Lecture 16: Deletion in AVL Trees, Examples. Multi-way Search Trees
Lecture 17: Insertion and Deletion in 2-4 Trees
Lecture 18: B-trees, insertion and deletion in B-trees
Lecture 19: Heaps and priority queues, Insert and deletemin
Lecture 20: Hashing: hash functions and examples

Books

There is no required textbook for this course. But most of the topics covered can be found in the following book.

Data-strcutures in JAVA by Michael T. Goodrich and Roberto Tamassia

Grading (tentative)

25% : Homework
20% : Each minor exam
35% : Major exam

Learning Java

There are excellent sources on the internet to learn Java. Note that you will be expected to learn Java (and use object oriented programming) on your own. Also refer to the Java module below and the exercises in it. You are required to solve all the exercises in the module as part of lab assignment (thanks to Prof. Amitabha Bagchi for making these available).