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
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