Midterm Preparation Problems.

Problem 1: Binary Trees. 

The following problems are best done on-line. If you choose not
to send the time on debugging, make sure you write the actual
code nevertheless, don't just put it aside once you understand the
"general idea".

1. Assume the following declarations for a binary tree. 

template struct BTNode {
    T value;
    BTNode * parent;
    BTNode * rchild;
    BTNode * lchild;

template class BTree {
   //constructor, destructor etc.
  BTNode * root_ptr;

1. Write a function to compare two trees (return true if both trees
have the same shape, AND all of their corresponding nodes are the same,
false otherwise). Using recursion saves a lot of coding: 
Two trees are equal if the root nodes are equal _and_ the left subtrees
under the root are equal, _and_ the right subtrees are equal. So you
function needs to make one node comparison and then call itself for
the left and the right subtrees. This can be your 

   bool BTree::operator == ( const BTree & rhs );

Assume that the type T has comparison == .  If you are still uncomfortable
with templates, assume that T is int or char.

2. Write a function that checks is the trees are of the same shape (here
no comparison of values at nodes is required). 

3. For  BTree  write a function that computes the total product
of all the int values  at the nodes.


Problem 2: Doubly Linked Lists.

Assume the following declarations for a doubly linked list:

template  class DList {
        Node* begin;
        Node* end;
        DList() : begin(null), end(null) {};
        // the usual methods

template  struct Node {
	T data;
	Node* prev;
	Node* next;

1. Write a function that takes a reference to DList and creates
a new list which is equal to the original one _in reverse order_.

2. Write  bool DList::operator == ( const DList & rhs ) that
returns true if both lists are of the same length and their
corresponding nodes are the same.


Problem 3: Big-Oh.

There are three basic rules for computing  running times
in Big-Oh notation. Let n be the natural parameter of the problem,
also refered to as its 'size'.

A. If the size of the broblem gets divided in half (or by any constant
number of times), the running time is logarithmic. Thus

int m = n;
while( m > 0 ){
  if ( m%2 == 0 ) { m = m/2; cout << "*"; }
  else m = m-1;

runs in O(log n) time, because m is divided by two at least every other

B. The running times of nested loops multiply.

C. To get the running time of a recursive function, draw the tree
of recursive calls. A binary tree with n levels has 2^n leaves,
so the time is usually exponential.

The recursive factorial  is O(n) (no branching of calls), while
recursive Towers of Hanoi and naive Fibonacci numbers are O(2^n).


Problem 4: STL.

1. Input, bubble-sort an STL  list  and print it.

2. Write a bubble sort function that doesn't care if it receives
a list ot a vector. You will have to use T as the parameter
for your linera data structure type; the individual entries will
be declared to have type  
                             typename T::value_type  , and
the function declaration will look like

template void BubbleSort( T & your_container_name ){
  typename T::iterator itr1, itr2, itr = your_container_name.begin();
  typename T::value_type temp_for_swapping; 
     // swapping two values (assignments presumably overloaded) 
     temp_for_swapping = *itr1;
     *itr1 = *itr2;
     *itr2 = temp_for_swapping;   
Problem 5: Binary Search Trees.

Write the code to insert a character into a binary search tree of 
characters (see declarations for BT above).


Problem 6: Recursion.

1. Recall that GCD( m, n) = GCD( m-n, n ) (assuming m > n).
Write a recursive function to compute GCD (what are your base

2. Write a recursive function to compute

1 + x + x^2 + ... x^n    in O(n)  time.

Same for  1 + x + 2*x^2 + ... + n!*x^n