# 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

## 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).