Computer Science 501
Data Stuctures and Algorithm Analysis

Fall 2013, The College of Saint Rose

Home     Syllabus     Schedule     Style Guide

Agenda

• Announcements
  • Programming Project 3: Dijkstra's Road Trip [HTML] [PDF] continues; due 12/9
• Final exam next week - see details on study guide and sample questions
• Lecture 12 assignment recap
• Balanced Search Trees
• AVL Trees
• Lab 8: Tree Problems [HTML] [PDF] due - quick recap
• Maps and Hashing
  • Map structures
  • Hashing
    • hash codes
    • handling collisions

No New Lecture Assignment

But these are good questions to look at before the exam.

1. Start with a complete AVL tree containing the values 10, 20, 30, 40, 50, 60, and 70. Insert the values 31, then 32, showing any rotations needed to maintain the AVL condition.
2. Now, insert 32 then 31. Show any rotations needed to maintain the AVL condition.
3. Design an AVL tree of height 4 such that if one more value is inserted, the root is the first unbalanced node on the way back up the tree. Once you have such a tree, insert that value, perform the proper rotation(s) and verify that the AVL condition is once again met.
4. Bailey Problem 15.2, p. 399.
5. Bailey Problem 15.6, p. 399.
6. Bailey Problem 15.8, p. 399.
7. Bailey Problem 15.12, p. 400.
8. Bailey Problem 15.16, p. 400.

Examples

• HashCodes