# Data Structures

*Sem 1, 2009-10*

### Lecture Slides

- Introduction to Data Structures and Algorithms [PDF]
- Stacks [PDF]
- Queues and Linked Lists [PDF]
- Dictionaries [PDF]
- Hashing [PDF]
- Trees [PDF]
- Tree Walks / Traversals [PDF]
- Ordered Dictionaries [PDF]
- Quicksort [PDF]
- AVL Trees [PDF]
- 2-4 and Red-Black Trees [PDF]
- (a,b) Trees [PDF]
- Disk Based Data Structures [PDF]
- Case Study: Searching for Patterns [PDF]
- Tries [PDF]
- Data Compression [PDF]
- Priority Queues [PDF]
- Binary Heaps [PDF]
- Why Sorting [PDF]
- More Sorting [PDF]
- Graphs [PDF]
- Data Structures for Graphs [PDF]
- Applications of Breadth First Search [PDF]
- Depth First Search [PDF]
- Applications of DFS [PDF]
- DFS in Directed Graphs [PDF]
- Applications of DFS in Directed Graphs [PDF]
- Minimum Spanning Trees [PDF]
- The Union [PDF]
- Prims Algorithm for Minimum Spanning Trees [PDF]
- Single Source Shortest Paths [PDF]
- Correctness of Dijkstras Algorithm [PDF]
- Single Source Shortest Paths [PDF]

### Homeworks:

- Lists and Sets. Due Date: Sunday, Sep. 6, 11:59pm.
- Hashing. Due Date: Sunday, Sep. 13, 11:59pm.
- Binary search trees. Due Date: Sunday, Oct. 11, 11:59pm.

### Programming Projects

- Towers of Hanoi. Due Date: Sunday, Sep. 20, 11:59pm.
- DNS Cache. Due Date: Sunday, Oct. 19, 11:59pm.
- Discrete Event Simulator. Due Date: Tuesday, Nov. 24, 11:59pm (hard deadline, no extensions).
- Shortest Paths. Due Date: Tuesday, Dec. 8, 11:59pm (no extensions possible).

### Books:

- Data Structures and Algorithms in Java (4th edition)
by Michael T. Goodrich and Roberto Tamassia
- Introduction to Algorithms (Second Edition) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein

### Academic Integrity Code

**Academic honesty is required in all your work**. Verbal discussion of
assignments is fine but looking at someone else's work and then doing your is
not. You must do all written and programming assignments on your own, except
where group work is explicitly authorised. **Letting your work become available
or visible to others is also cheating**. First instance of cheating will
invite a zero in the assignment
and a letter grade penalty. Repeat offender will fail the course.