CSC-152 99S : Exam 3: Trees, Queues, Stacks, Dictionaries, and Other Structures

Distributed: Friday, April 30, 1999
Due: Noon, Thursday , May 13, 1999
No extensions!

There are a number of different questions on the exam, each with its own point value. The number of points assigned to a question does not necessarily reflect its difficulty or the time you will spend on it.

If you are confused by any question, do not hesitate to ask me for clarification. I will reserve time at the start of classes next week for questions. In addition, you can speak to me individually. I may not be available at the time you are working on the exam. If it's a reasonable hour (before 10 p.m. and after 8 a.m.), feel free to try to call me in the office (269-4410) or at home (236-7445). Email is also a reasonable way to contact me.

This examination is open book, open notes, open mind, open computer, open Web. Feel free to use any and all resources available to you except for other people and answer keys. That is, you should not consult other students, other faculty, or anyone else. (If someone outside of Grinnell has already created a Web page that answers your question and that page is not an answer key, you may use the page; however, you can't ask someone to create such a page and you cannot use pages explicitly designated as answer keys.) In addition, while you can look at the pages I've created for this and other courses, you should not refer any pages that are clearly answer keys to homework assignments or exams.

As always, you are expected to turn in your own work. If you find ideas in a book or on the Web, be sure to cite them appropriately.

This is a take-home examination. It is likely to take you about four hours. You may use any time or times you deem appropriate to complete the exam, provided you return it to me by the due date. No late exams will be accepted. I may make a solution key available soon after the exam.

Because different students will be taking the exam at different times, you are not permitted to discuss the exam with anyone until after I have returned it. If you must say something about the exam, you are allowed to say ``This is definitely the hardest exam I have ever taken.'' You may also summarize these policies.

Answer all of your questions electronically. That is, you must write all of your answers on the computer and print them out. Please put your answers in the same order that the problems appear in.

I will give partial credit for partially correct answers. You ensure the best possible grade for yourself by highlighting your answer and including a clear set of work that you used to derive the answer.

You need not write working code. However, your code should be sufficiently clear to convince me that you would be able to write working code given additional time to correct minor syntactic errors. You may also find that you learn more about the problem by trying to write working code.

While many of the problems in this exam appear to be about binary trees, they are also intended to test your understanding of a host of related issues. However, since there is some relationship between the problems on this exam, I encourage you to read through the whole exam before beginning work on any one problem.

Problems

1. Expression Trees

There are many things we do with binary trees. One particularly important one is to print them out. While in some cases, we want to print them out so that they look like trees, at other times we just want to print the elements of the tree. When we store arithmetic expressions in trees (in so-called expression trees, the way we print it out can correspond to different ways we are used to writing expressions.

As you saw in the binary tree lab, one appropriate way to represent binary trees is by giving clients cursors that they can move around the tree. We allow clients to create multiple cursors so that they can keep track of different parts of the tree. (See the code libraries section for all the details.)

In the rest of this problem, you will look at the relationship between these two ideas: how to turn a tree into a string, using one of these ways of writing expressions.

The notation we typically call ``standard arithmetic notation'' is often referred to more formally as infix notation, because the operator appears in-between the operands. To convert an expression tree to the corresponding infix string, we concatenate:

For example, to turn the previous example tree into a string, we begin with an open paren, (. We then follow it with (3+4), the string for the left subtree. We then follow that with the operator, *. We follow that with (5-6), the string for the right subtree. Finally, we cap it off with a close paren, giving ourselves ((3+4)*(5-6)). How did we figure out the string for the left and right subtrees? In the same way. Consider

A. Recursive Translation [15 points]

As you may have noted from the above discussion, translation from tree to infix string naturally occurs recursively (that is, you use the same kind of method to handle each subtree that you used for the tree as a whole). If you look at the code for the simple BinaryTreePrinter class, you'll note that it's also recursive.

Implement a recursive method that turns a binary tree into an infix string, using the rules described above (left paren, left subtree, operator, right subtree, right paren). It should correspond to the following function description:

  /**
   * Convert a tree to a parenthesized infix string.
   * Pre: The tree is nonempty.
   * Post: Returns a string corresponding to the values in
   *   the tree, described using parenthesized infix notation.
   *   When an operator is applied to two arguments, it appears
   *   between the two arguments and the whole shebang is
   *   parenthesized.
   */
  public String infix(BinaryTree tree) {
    ...
  } // infix(BinaryTree)

B. Iterative Translation [20 points]

Some programmers prefer not to use any form of recursion. For algorithms like the infix tree printer, it may be more convenient to use a stack to keep track of what's left to print. Rewrite your method from part A iteratively (without recursion), possibly using a stack to keep track of what's left to print.

Hint: Your stack will probably contain not only cursors (representing subtrees left to print) but also strings (representing operators or parens left to print). When you pop something from the stack, you should first check if its a cursor or a string, using the instanceof operator.

2. From Tree to Array [25 points]

As you saw in our discussion of heaps, it is relatively easy to store a nearly-complete binary tree in an array. The root goes in position 0. The nodes at level one go in positions 1 and 2. The nodes at level two go in positions 3, 4, 5, and 6. And so on and so forth. We might also copy the values in an incomplete binary tree to an array, using the same basic strategy (all the nodes at level 0 go in first, then all the nodes at level 1, then all the nodes at level 2, and so on and so forth). This latter technique makes it harder to reconstruct the tree, but there are times when we care less about the structure of the tree, and more about the contents.

The strategy of looking at one level at a time is called breadth-first traversal because you go across the breadth of the tree before delving into the depths of the tree.

Implement a method that puts the elements of a binary tree into an array, using a breadth-first traversal. It should match the following specification:

  /**
   * Extract all the elements in a binary tree, using
   * a left-to-right breadth-first order.  That is, all elements 
   * in level i should precede all elements in level j > i
   * and the left child of any node should precede the right
   * child.
   * Pre: The tree is nonempty.
   * Post: Returns the elements according to those specs.
   */
  public Object[] contents(BinaryTree) {
    ...
  } // contents(BinaryTree)

Hint: Put a cursor on each node when you can, and then put the nodes in a queue. You can find an implementation of queues in the appendix to this exam.

3. Binary Search Trees

You may recall that the binary search tree is a of binary tree in which the elements are organized in a particular way. Everything below and to the left of a node is less than the value stored in the node. Everything stored below and to the right of the node is greater than or equal to the value of the node.

Here is part of a definition of the BinarySearchTree class, including an algorithm for inserting a value in a binary search tree, based on our standard implementation of trees. You can find more of the definition at the end of the exam.

public class BinarySearchTree 
{
  /**
   * The underlying binary tree.  We don't subclass
   * BinaryTree (or one of its implementations), because
   * we don't want clients to do anything but add and
   * lookup elements.
   */
  protected BinaryTree tree;

  /**
   * The comparator used to determine ordering.
   */
  protected Comparator compare;

  /**
   * Insert an element in a binary search tree.
   * Pre: The tree is initialized.
   * Pre: The tree is in the standard order (smaller elements
   *   to the left, larger to the right).
   * Pre: The element and all values in the subtree can be 
   *   compared using the comparator.
   * Post: The element is inserted at the proper place.
   */
  public void insert(Object newElt) {
    // Special case: The tree is empty, so put at the root.
    if (tree.size() == 0)
      tree.setRoot(newElt);
    // Normal case: Find the location and put it there.
    else
      insert(newElt, tree.rootCursor());
  } // insert(Object)

  /**
   * Insert an element in the portion of a subtree below
   * a cursor.
   * Pre: The cursor is on the tree.
   * Pre: The tree is nonempty.
   * Pre: The subtree is in the specified order (smaller elements
   *   to the left, larger elements to the right).
   * Pre: The element and all the values in the subtree can be
   *   compared using the comparator.
   * Post: The element is inserted at the proper location.
   */
  protected void insert(Object newElt, BinaryTreeCursor cursor) {
    // Smaller things belong to the left.
    if (compare.lessThan(newElt, cursor.getValue())) {
      // Is there something to the left?  If so, insert
      // in the left subtree.
      if (cursor.hasLeftChild())
        insert(newElt, cursor.getLeftChild());
      // If there isn't something to the left, put the smaller
      // element there.
      else
        cursor.setLeft(newElt);
    } // if smaller
    // Larger things belong to the right.
    else {
      // Is there something to the right?  If so, insert
      // in the right subtree.
      if (cursor.hasRightChild()) 
        insert(newElt, cursor.getRightChild());
      // If there isn't something to the right, put the new
      // larger (or equal) thing there.
      else
        cursor.setRight(newElt);
    } // larger or equal
  } // insert(Object, BinaryTreeCursor)

  // ...
} // class BinarySearchTree

A. The smallest element [10 points]

Write a method, smallest, that returns the smallest value in the binary search tree. (This should be a method that appears within the BinarySearchTree class.) It should have the form

  /**
   * Find the smallest value in this tree.
   * Pre: The tree is initialized and nonempty.
   * Pre: The tree is in appropriate order.
   * Post: Returns the smallest value.
   */
  public Object smallest() {
    ...
  } // smallest()

You may find it useful to include the following helper method. (You must define this method if you use it.)

  /**
   * Find the smallest value in a subtree given by a cursor.
   * Pre: The tree is initialized and nonempty.
   * Pre: The cursor is on the tree.
   * Pre: The tree is in appropriate order.
   * Post: Returns the smallest value.
   */
  public Object smallest(BinaryTreeCursor cursor) {
    ...
  } // smallest(BinaryTreeCursor)

B. Running time [10 points]

What is the running time of your method, if we assume that the tree is nearly-complete? What is the running time if we assume nothing at all about the tree (other than it is correctly constructed)?

C. Deletion [20 points]

Write a method, delete that deletes one copy of an object from a binary search tree (provided, of course, that the object appears in the search tree). This method will appear within the BinarySearchTree class.

You may assume that the class also provides the smallest(BinaryTreeCursor) method described in part A, as well as a corresponding largest method. (And yes, that's a hint as tho how you might do it.)

[Instructions] [Search] [Current] [Syllabus] [Links] [Handouts] [Outlines] [Labs] [More Labs] [Assignments] [Quizzes] [Examples] [Book] [Tutorial] [API]

Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.

This page may be found at http://www.math.grin.edu/~rebelsky/Courses/CS152/99S/Handouts/exam.03.html

Source text last modified Fri Apr 30 12:24:46 1999.

This page generated on Fri Apr 30 12:31:11 1999 by SiteWeaver. Validate this page's HTML.

Contact our webmaster at rebelsky@math.grin.edu