Computer Science 501
Data Stuctures and Algorithm Analysis

Fall 2013, The College of Saint Rose

Home     Syllabus     Schedule     Style Guide

Agenda

• Announcements
  • Midterm exam score improvement opportunity tonight
  • Programming Project 2: Analyzing Sorting Algorithms [HTML] [PDF] due now
  • Lab 7: P.S.: It's Just a Stack [HTML] [PDF] due next week
  • no new lab assignment this week
• Lecture 9 assignment recap
• Lab 6: The Two Towers [HTML] [PDF] discussion
• Note: we won't get to all of this - some will spill into next week
• Ordered structures
  • ComparableAssociations
  • the OrderedStructure interface (it's empty!)
  • OrderedVector
  • OrderedList
• Trees
  • motivation
  • terminology
• Binary Trees
• Tree Traversals
  • preorder, in-order, postorder and level-order
  • recursive implementation
  • implementations as Iterators
• Binary tree example: Huffman trees

Lecture 10 Assignment

Due at the start of class, Wednesday, November 13.

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

• Consider the following three options:
  1. a standard Vector
  2. a MyVector from the sorting lab, which is capable of sorting its contents on demand (by calling the sort method)
  3. an OrderedVector, which might be thought of as a MyVector that automatically sorts during/after each modification to its contents

  Given a set of data which is modified periodically and printed in order periodically, describe briefly the circumstances (relative frequency of modifications and printouts) where each of the above three approaches might be beneficial. (8 points)

• Bailey Problem 12.22, p. 312. (4 points)

Examples

• BinaryExpressionTree
• BTTraversals