CSE 373 Data Structures 10sp, Homework 2
Due at the BEGINNING of class, Friday, 4/16/10
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
- Prove (using Induction) that:
![](hw02_files/image003.gif)
Hints: Start with N=1 as the base case, then show how
ends up being equal to
. More hints: You
already know what the sum of
is, and you should use
the induction hypothesis
to come up with your answer.
Referring to the induction examples on pages 6 and 7 and the examples
from the slides may be helpful.
- Order the functions given in
Weiss question 2.1 on page 50 from slowest growth rate to fastest growth
rate. IN ADDITION add these functions in: log N, log2 N. If any of the functions grow at the same
rate, be sure to indicate this.
- Weiss question 2.2 on
p.50. You do not need to prove an
item is true (just saying true is enough for full credit), but you must
give a counter example in order to demonstrate an item is false if you
want full credit. To give a counter
example, give values for T1(N), T2(N) and f(N) for
which the statement is false.
Hints: Think about the definitions of big O and little o.
- Weiss, question 2.7
on p.51 (You only need to do this question for the first FIVE
program segments – you may ignore the last loop (6)). 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. A link to some
Java code showing an example of timing can be
found here.
Note that there are THREE parts to this question, do all
3. a) calculate big-O, b)
run the code *for several values of N* (4 or more) and time it,
c) talk about what you
see. For part c, be sure
to say something about what you saw in your run-times, are they
what you expected based on your big-O
calculations?
If not, any ideas why not?
Graphing the values you got from part b might be useful for your
discussion. Remember that when giving the big-O running time we always
want the tightest bound we can get.
- Show that the function 315n
+ 45n3 + 214 is O(n3).
(You will need to use the definition of O(f(n))
to do this. In other words, find
values for c and n0 such that the definition of big-O holds
true as we did with the examples in lecture.
- (Unbalanced binary search
trees)
- Draw a picture of the
integer-valued BST that results when these values are inserted in
this order: 17, 9, 14, 2, 4, 5, 40, 70, 56.
- Which nodes are the
leaves of this tree? Which node is the root?
- What is the depth
of the node containing 4? What is the height of the node
containing 40?
- 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.
- Draw the sequence of
trees (thus draw 3 new trees) that result if we perform these operations in
this order on the original tree from part (a):
add(11)
, delete(9)
, delete(17)
(You may use either
deletion routine described in lecture, but for ease of grading please
pick one strategy and stick with it – do NOT use lazy
deletion.).