jdupee
10-18-2004, 06:07 PM
First off I would like to thank anyone in advance for helping me. I am in my last semester of College and for some unknown reason I decided to take a class I did not need but I have to finish it now to graduate in December. I am a Electrical Engineer and I very little experience with Java. I took a class that we did some simple programs with arrays being the hardest thing I did.
I am taking a class called Algorithms because my Counsuler recommended it to me since I had taken a Java class before. This class is in the Software Engineer and Computer Science department and what I did not know was if I was in that department there are two more classes after the Java class I took before they can take it. I am using this class as my engineering elective and I am way over my head. I have to pass this class so I really need help.
I know how BST and AVL trees work on paper but not in programming.
I am gonna make another post because what I have to is long or I think it is.
jdupee
10-18-2004, 06:09 PM
1.Write an algorithm for traversing a tree in level-order and printing out its node values (Hint: the basic idea is to
start a queue with the root and repeatedly dequeue a node, print its value and enqueue its children until the queue
becomes empty). Then implement it.
2. Implement a program to construct a BST (i.e. no need to rotate the tree while inserting nodes) one node at a time.
Test your program by having it construct some BSTs and then printing out the trees in level order.
3. Implement the Find algorithm for Splay Trees, Splay-Find, in two stages:
3.1 Implement an iterative version of the Find algorithm for BSTs. You can take the recursive algorithm in
your lecture notes and easily convert it because it is an algorithm with tail recursion. Add code to count the nodes
visited. Test your implementation to make sure it correctly finds and counts.
3.2 Then add code to restructure the tree by applying a series of rotations so that the found node reaches the
root, only if the node is found, and add the number of rotations needed to the count. Test your program by printing
out the restructured trees in level order and verifying that it is rotating the tree and counting rotations correctly.
4. Write a main program that implements the following pseudocode (create and print all outputs to a file named
“hw3.txt”):
n=2
theoretical-amortized-complexity=1
repeat
construct a BST of size n one node at a time where the nodes are added in the order 1, 2, 3..i..,n
and node i has value i.
print out the tree in level order on a new line with node values separated by commas.
total-count=0
for j=n,n-1,n-2,…2,1 do
Run Splay-Find(j) on the tree
print out the tree in level order on a new line with node values separated by commas
print string “count=” on a new line followed by the count for this execution of Splay-Find
total-count = total-count + the count for this execution of Splay-Find
end for
empirical-amortized-complexity=total-count/n
print “ratio=” and the value empirical-amortized-complexity/theoretical-amortized-complexity
print a blank line
n=2*n
theoretical-amortized-complexity= theoretical-amortized-complexity+1
until n=64 {that is, do the above for 5 trees of sizes 2,4,8,16 and 32}