Computer Science 431
Algorithms

Spring 2015, The College of Saint Rose

Home     Syllabus     Schedule

Agenda

• Announcements
  • Public talk tonight: Bowden Wise of GE Global Research, 7:30-8:30 PM, Albertus 205
  • Problem Set 5: Divide and Conquer [HTML] [PDF] continues
• Lecture 14 assignment recap
• Divide and conquer wrapup
  • closest pairs wrapup
  • quickhull
• Binary Search Trees
  • basics of BSTs
  • tree sort
• Balanced trees
  • AVL trees

Lecture 15 Assignment

Due at the start of class, Wednesday, March 18.

Please submit answers to these questions in Submission Box under "LA15" 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.

• Levitin Exercise 4.5.7, p. 166. (4 points)
• Levitin Exercise 4.5.8, p. 166. (4 points)

Terminology

• quickhull
• binary search tree (BST)
• tree sort
• balanced trees
• balance condition
• red-black trees
• AVL trees
• splay trees
• 2-3 trees
• AVL condition
• single rotation
• double rotation

Links

• Animation of Closest Pair: Divide-and-Conquer (in German, but the animations speak for themselves)