CSE326 Midterm Exam #1

With answers and notes
July 9, 2004
Each part of each problem is worth 4 points except where noted


1. In a binary tree, "full nodes" are those with two children. 
    A. What is the relationship between the number of full nodes and the number of leaves in a binary tree?  Iluustrate with a couple of examples. 

#Leaves=#FullNodes +1. See attatched for examples.         


    B. Now prove your answer with a careful proof.by induction.


Note: a very common flaw in the proof was omitting a statement of what the induction variable was.  This cannot be inferred just from the relationship "#Leaves=#FullNodes +1".  Some possibiities are:
induction on the number of nodes in the tree
induction on the number of leaves
induction on the number of full nodes
induction of the height of the tree, etc.

Each of these will lead to different ways of phrasing the base case(s), different uses of the induction hypothesis, etc.

Proof by induction on number of nodes in the graph.  Let P(n) = For all trees with n nodes, #Leaves=#FullNodes +1 .

Basis step: For P(1), there is only one possible tree, with nothing but a root, and for this tree, the statement is true:  #Leaves=1 and #FullNodes=0

Induction Hypothesis: Assume P(k) is true for some k >= 1.

Induction Step: Consider any tree with k+1 nodes. Remove one of the leaf nodes. The remaining tree has k nodes, so the ID holds for that tree. Two cases are possible. a) the parent of the leaf node removed is a full node. In this case adding the leaf increases the number of full nodes by 1 and the number of leaves by 1. So the equality is satisfied. b) the parent of leaf node was not a full node. So when the leaf is added the number of leaves is unchanged (parent is no longer a leaf and a leaf is added) and no extra full nodes are added. so equality is maintained.


2. Let f and g be functions, and suppose that for every n>1, it is true that f(n) < g(n).   Clearly f(n) = O(g(n)).  Is it also possible that g(n) = O(f(n))?  Explain.

Yes. Consider f(n)=n and g(n)=2n. Clearly f(n)<g(n). Also g(n)=O(f(n)) as g(n)<=3*f(n) for n>1.


3. Suppose the time complexity function of an algorithm is approximated at 5*2N.  The algorithm is programmed and timed to run for about 5 seconds when N = 10.  Given just this information, estimate how long it would take to run when N = 20.

Remember that the basic definition of a complexity function is that it tells the number of steps required for a given problem size.  Use the complexity formulat to find the number of steps for N=10, and you can calculate how long each step takes.   Then when you have calculated the number of steps when N=20, you can figure out the total time.

(Time taken for N=20) / (Time taken  for N=10) = (5*220 )/( 5*210) = 210   =1024.

So, Time taken for (N=20) is 5*1024=5120s.

Only an "estimate" was asked for, so you could have rounded off or approximated along the way.  5000 was certainly acceptable.


4. Each of the following functions is defined at least for values of n >= 2.  Give a big-Theta bound for each of these functions.  You do not need to explain your answer. (2 pts. each)

f(n) = n * (n % 7)  O(n)

f(n)  = n % (n - 1)   This is exactly 1. O(1)

f(n) = (n * n) % (n + 1)  This is exactly 1. O(1)


5. Outline the steps to solve this problem using the classes, interfaces, and methods of the Java Collections framework.  Give code that is pretty close to real, compilable Java if possible (without taking too much of your valuable time!).

 John and Brenda each have a list of all the books they own. 
    A. Print out all the books owned by either of them (listing each book only once), and then
    B. print out only the books they both own.

The solutions shown are quite compact through clever use of the addAll and contains method.  You can of course solve the problem without them.

For both the examples assume that the list of books are in the following List
List brenda; 

List john;

A.
 
 Set either=new TreeSet(); 

 either.addAll(john);

 either.addAll(Brenda);

 Iterator iter=either.iterator();

 while (iter.hasNext()) { 

   System.out.println(iter.next()); 

 }

B.
 
 Set brendaSet=new TreeSet(brenda);

 Iterator iter=john.iterator();  

 while (iter.hasNext()) { 

    Object book=iter.next();' 

    if (brendaSet.contains(book))

       System.out.println(book); 

 }

 

 



6. Given an initially empty stack S of characters, what is on the stack after these operations have completed?  (For possible partial credit, show your work).

S.push('s');
S.push('t');
S.push('u');
char ch = S.pop();
ch = S.pop();
S.push('v');
S.push(ch);
S.push('w');
ch = S.pop();        

See attatched. 
7. Given an initially empty queue Q of characters, what is in the queue after these operations have completed?  (For possible partial credit, show your work).

Q.enqueue('s');
Q.enqueue('t');
Q.enqueue('u');
char ch = Q.dequeue();
ch = Q.dequeue();
Q.enqueue('v');
Q.enqueue(ch);
Q.enqueue('w');
ch = Q.dequeue();

 

See attached. 

8. Think about the stack-based algorithm for evaluating post-fix expressions.  (You can assume, if it helps, that all the operations are binary, left-associative).
    A. In terms of that algorithm, how do you determine whether a given expression is a valid postfix expression?  (For example, A B + is valid but Z + Y is not).
The given expression is valid postfix if 

1) The stack contains atleast two elements whenever you try to pop two elements. (i.e. StackEmptyException is never thrown). 

2) The stack contains exactly  one element when the expression is completely read.  

    B. Give an algorithm for determining if a given expression is valid postfix or not.  Do not use a stack (do something simpler if possible).
Keep a counter of "effective" number of operands.  Initialize the counter to 0.  Whenever you see an operand, add one to this counter. When you see an operator check to see if the number of operands is >=2. if not the expression is malformed; if yes, decrement the counter by one. At the end of the expression the value of counter should be 1 for the expression to be well formed. 

9. There is a stack-based algorithm for converting in-fix expressions into postfix.  Show how this works, by showing the state of the stack and the output at each step during the conversion of this expression.  You can do this by crossing out old values if you are neat and clear about it; otherwise, redraw the stack at each stage.

A * (B + C / D) + E

See attatched. 

10. Suppose you are told that A B C D is the pre-order traversal of a binary tree, and that A B C  D is also the in-order traversal of the same tree!  Either give a tree which satisfies this, or explain why it is not possible.

It is possible. Note that is there is no left child the actions of the two traversals are identical. See attached to example of tree. 



11. Draw the tree resulting from inserting the following values into an initially empty binary search tree: 
5  10  20  3    7   4    1   6   11   19

See attached. 


12. Give worst-case and average-case bounds (big-Theta if possible, otherwise just big-O) for the time of each of the following, assuming a reasonable implementation (2 pts. each):
    A. Insertion into a queue (array-based implementation) Theta(1)

    B. Deletion from a binary search tree Theta(log(n)) average case, assuming the tree is reasonably well balanced on average.  Worst-case Theta(n).

    C. Finding the max value in a binary search tree See previous answer

    D. Deletion from a list (linked-list implementation) Theta(1), assuming you know where the deletion is to be; Theta(n) if you have to search for the element

    E. Insertion in a list at given position (array-based implementation) Theta(1) if you take "insertion" to mean "replacement",  Theta(n) if insertion means preserving the elements in the list by shifting to the right (e.g, the way Java ArrayList works).

13.  In this problem, we deal exclusively with binary trees of integers.  It might help you to think of these integers as weights, and to think of the tree like an Alexander Calder mobile with objects of different weights dangling from it.

Define a node to be "weight-balanced" if the sum of all the weights (i.e., the integer values) in the left subtree is equal to the sum of all the weights in the right subtree.  Note that with this definition, every leaf node is weight-balanced.

A  (2 pts.) Give an example of a tree (with 4 or more nodes) whose root is weight-balanced but where no other non-leaf nodes are weight-balanced. See attatched.
B. (2 pts.) Give an example of a tree (with 4 or more nodes) in which every node is weight-balanced. See attatched. 
C. (2 pts.) Give an example of a binary search tree (with 4 or more nodes) in which the root is weight-balanced.See attatched. 
D. (8 pts.) Implement the following method in Java:
/** Return true iff the node is weight-balanced or is null.*.
boolean checkBalance(BinTreeNode node);
Use this class definition:
public class BinTreeNode {
    Object element;
    BinTreeNode left;
    BinTreeNode right;
}
Your are free to write helper methods if you wish.

public static boolean checkBalance(BinTreeNode node) {
if (node == null) {
return true;
}
return sum(node.left) == sum(node.right); 
}

private static int sum(BinTreeNode node) {
if (node == null) {
return 0;
}
return ((Integer) node.element).intValue()
+ sum(node.left) + sum(node.right);
}

 E. Give a bound for the running time of your algorithm (2 pts.)  O(n).