CS 2620 Assignment #7 Summer 2004

How to handin.
Points : 40
Weight : 3%
Due : Friday June 11, 2004 @ 11:00 PM
Note : Late assignments will be accepted only with the instructor's pre-approval.

Marks will be awarded for comments, style, readability, compiling and working correctly.

[5] Assume that we have the following declaration;

 
vector<int> vec;

and that we have filled the vector vec with the following values:

12, 5, 1, 23, 16, 4, 3, 11, 41, 19

Given the following recursive function:

int mystery(const vector<int>& x, int n) {
   
    int temp;    // local variable
    
    if ( n == 1 ) return x[0];
    
    // n is > 1;
    temp = mystery(x, n-1);
    if (x[n-1] > temp) 
        return x[n-1];
    else
        return temp;
}

Trace the mystery recursive function if the call

cout << mystery(vec, vec.size()) << endl;

is used. What is the output? What does the mystery function do?

[2] The function f(x) is defined for non-negative integers as follows :

f(x) = 5 if x = 1;

f(x) = x + f(x-3) if x is odd and x >= 3;
f(x) = x² + f(x-2) if x is even and x >= 4;

Explain why this function is not well defined and add something to it that will make it well-defined.
Write a library of recursive functions that includes the code for the corrected version of the above function and the following recursive functions :
1. [2] a recursive function to calculate log₂(n) for positive integers defined as:
  
  log₂(n) = 0 if n = 1;
  log₂(n) = 1 + log₂(n/2) if n > 1;
2. [2] a recursive function, mult(a,b), which multiplies two integers. You may not use the "*" operator in your function, only the "+" operator.
3. [2] a recursive function to calculate the sum of squares of the values 0 to n.
  e.g.
```
   sumsq(2) = 0 + 1 + 4 = 5
   sumsq(4) = 0 + 1 + 4 + 9 + 16 = 30
```
4. [2] a recursive version of the gcd function
[4] Write a client program that will test the above functions as follows:
1. asks the user for two integers, multiplies them and prints the product
2. calculate f(x) for x = 1 to 33
3. calculate sumsq(x) for x = 1 to 33
4. calculate log₂(x) for x = 1 to 33
5. calculate the gcd of 32136907 and 184484373
Trees
1. After reading the sections on binary trees from the text (pages 496-508) and your class notes, answer the following :
  1. [2] Discuss the differences between a single linked list and a binary search tree. Consider such things as the number of pointer fields per node, search efficiency and insertion efficiency.
  2. [2] Create a binary search tree, inserting the following elements:
```
 1 3 5 7 9 11 12 15 17
```
    What happens when the elements inserted into a binary search tree are already in order? Now create a binary search tree inserting the following elements:
```
 17 15 12 11 9 7 5 3 1
```
    What happens when the elements inserted into a binary search tree are in reverse order? How do these orders affect the efficiency of the search and insert algorithms?
  3. [1] How can you determine if a node in binary tree is a leaf?
  4. [3] Using the following binary tree, give the inorder, postorder and preorder traversals.
```
                        F
                       / \
                      /   \
                     R     C
                    / \     \
                   /   \     \
                  A     E     O
                 /     / \   / \ 
                /     /   \ /   \ 
               B     T    G L    D
```
  5. [3] Given the following traversals, construct the binary tree and give the postorder traversal.
    preorder traversal - hyiBrancs-ReA
    inorder traversal - iByrnahs-ceRA
2. Add functions to the bsTree class found in $L/lect/jun08/bsTree to do the following:
  - [2] return the SUM of the data in the nodes of a binary tree containing integers or floats.
  - [4] return a binary tree that is the mirror image of the current tree. eg if T is the tree given in part E above, then T.mirror() would return the tree below:
```
                        F
                       / \
                      /   \
                     C     R
                    /     / \
                   /     /   \
                  O     E     A
                 / \   / \     \
                /   \ /   \     \
               D    L G    T     B
```
  Include any helper functions that you need.
  [4] Modify the doPrints function in the test program to do the following :
  - it will first print the sum of the nodes for any tree that contains ints or floats. Use the typeid class in the typeinfo library to determine the type of data stored in the tree.
  - after it prints a tree sideways, it prints the mirror image of the tree sideways.

Assignment List | Prev | Next | Computer Science 2620
Department of Mathematics & Computer Science

University of Lethbridge Home Page

f(x) = 5		if x = 1;
f(x) = x + f(x-3)		if x is odd and x >= 3;
f(x) = x² + f(x-2)		if x is even and x >= 4;

`log₂(n)` = 0		if n = 1;
`log₂(n)` = 1 + `log₂(n/2)`		if n > 1;