CSE 373 Data Structures Sp08, Homework 2

Due at the BEGINNING of class, Friday, 4/18/08

Here are some questions on complexity, algorithm analysis, and the basics of binary trees. You only need to turn in written solutions, although you will need to run some code for one of the problems.

Problems

1. Weiss, 2.1.
2. Weiss, question 2.7. For parts (b) and (c), please turn in a printout of your Java code, (no electronic submission required). Hints: you will want to use assorted large values of n to get meaningful experimental results. You may find the library function System.nanoTime() to be useful in timing code fragments.
3. Weiss question 2.8(b).
4. Weiss question 2.11.
5. Show that the function 18n + 4n² + 373 is O(n²). (You will need to use the definition of O(f(n)) to do this.)
6. (Unbalanced binary search trees)
1. Draw a picture of the integer-valued BST that results when these values are inserted in this order: 5, 17, 10, 3, 4, 8, 20, 39, 12.
2. Which nodes are the leaves of this tree? Which node is the root?
3. What is the depth of the node containing 3? What is the height of the node containing 5?
4. Write down the order in which the node values are reached by (i) a preorder, (ii) an inorder, and (iii) a postorder traversal of the tree.
5. Draw the sequence of trees that result if we perform these operations successively on the original tree from part (a): add(9), delete(3), add(13), delete(5).
7. Draw a single binary tree such that each node contains a single character, a preorder traversal of the tree yields EXAMFUN, and an inorder traversal yields MAFXUEN.