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. templatestruct BTNode { T value; BTNode * parent; BTNode * rchild; BTNode * lchild; }; template class BTree { public: //constructor, destructor etc. protected: 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 { protected: Node * begin; Node * end; public: 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 iteration. 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 cases?). 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