CSE373 Data Structures Wi07, Homework 3

Due at the beginning of class, Friday, 1/26/07
No late assignments will be accepted.

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, question 2.7. For parts (b) and (c), you do not need to turn in the Java code, just give answers to the questions. 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.
2. Weiss question 2.8(b).
3. Weiss question 2.11.
4. Weiss question 2.12.
5. Show that the function 12n + 3n² + 373 is O(n²). (You will need to use the definition of O(f(n)) to do this.)
6. Between lectures and homework, we've now examined three implementations of an unbounded sequential list: an array-based list, a single-linked list, and a double-linked list. Give a table showing, for each of these three implementations, the asymptotic runing time of each of the following operation as a function of the list size n (i.e., O(n²), O(n log n), etc.).
   • add a new item at the front of the list (position 0)
   • add a new item at the end of the list (position n)
   • return the current size of (number of items in) the list
   • clear the list (set it to empty)
   • search for an item in the list
   • remove the item at the front of the list
   • remove the item at the end of the list
   • advance a list iterator to the next item in the list
   • advance a list iterator to the previous item in the list
   • remove the most recent item returned by an iterator's next() operation
   • insert a new item just after the most recent item returned by an iterator's next() operation
   • insert a new item just before the most recent item returned by an iterator's next() operation
   If the normal expected time of an operation is asymptotically different from the worst-case time, given both times and a brief explanation of the why they differ.
   You should assume a reasonably efficient implementation the list opearations. In particular, for linked lists, assume that there are instance variables containing the current size of the list, and pointers to the first and last nodes in the list. You should assume that the list is not circular and contains no extra dummy nodes other than the nodes that refer to data values that have been added to the list.
7. (Unbalanced binary search trees)
1. Draw a picture of the integer-valued BST that results when these values are inserted in this order: 15, 7, 10, 3, 4, 8, 17, 42, 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 7?
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(17), add(13), delete(7).
8. 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.