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:

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

Programming Projects

1. Towers of Hanoi. Due Date: Sunday, Sep. 20, 11:59pm.
2. DNS Cache. Due Date: Sunday, Oct. 19, 11:59pm.
3. Discrete Event Simulator. Due Date: Tuesday, Nov. 24, 11:59pm (hard deadline, no extensions).
4. 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