Computer Science 431
Algorithms

Spring 2015, The College of Saint Rose

Home     Syllabus     Schedule

Agenda

• Announcements
  • note the video at the bottom of the previous lecture page
  • Problem Set 5: Divide and Conquer [HTML] [PDF] due tomorrow night
• Problem Set 6: Trees [HTML] [PDF] out
• Lecture 15 assignment recap
• Balanced trees
  • AVL trees
• Array representation of binary trees
• Priority queue (review)
• Heaps

Lecture 16 Assignment

Due at the start of class, Monday, March 23.

Please submit answers to these questions in Submission Box under "LA16" or in hard copy by the start of our next class. We will discuss these questions at the start of class, so no late submissions are accepted. Please be sure that your name is clearly indicated in all submissions.

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. (5 points)
2. Now, insert 32 then 31. Show any rotations needed to maintain the AVL condition. (5 points)
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 points)
4. Levitin Exercise 6.3.7, p. 226 (5 points)

Terminology

• single rotation
• double rotation
• array representation of trees
• priority queue
• min-heap/max-heap