CS 12 - Homework Assignment 3

CS 12 Homework Assignment 3

This assignment is due on Wednesday, August 6, 2003, at the start of the lecture. Please hand in printed solutions.

1. Write a program to play a numerical version of "20 questions." More specifically, your program should ask the user to choose a maximum integer number, maxNum, then ask the user to think of an integer number, between 1 and maxNum, inclusive. The program's goal is to guess which number the user thought of, by asking whether the mystery number is bigger than a guess provided by the program. The user should respond with y or n, accordingly. When your program figures out the mystery number, it should print both that number and the number of questions asked.

2. Write a test program that defines an array of 5 integers, fills it with the first 5 odd numbers, and then prints the contents of the first 10 elements. Yes, I meant the first 10 elements. Explain the result. You should hand in as part of this assignment the printout of a few runs of your program.

3.a. Consider the following recursive relation, defining the so-called Fibonacci sequence:

F(0) = 1
F(1) = 1
F(n) = F(n-1) + F(n-2), for n > 1

Show a two-column table where the first column has values of n and the second colum has the corresponding values F(n), for n going from 0 to 10.

3.b. How many function calls of the form F(something) are made when computing F(7)? How many times are F(1) and F(0) called for? In your solution, show a trace of the execution of this function call. Here's an example of tracing the execution of F(4): (Notice the indentation pattern; it will help you understand what's happening.)

F(4) calls F(3)
           F(3) calls F(2)
                      F(2) calls F(1)
                           F(1) returns 1
                      F(2) calls F(0)
                           F(0) returns 1
                F(2) returns 2
           F(3) calls F(1)
                F(1) returns 1
     call to F(3) returns 3
F(4) calls F(2)
           F(2) calls F(1)
                F(1) returns 1
           F(2) calls F(0)
                F(0) returns 1
     call to F(2) returns 2
call to F(4) returns 5

So, the call to F(4) generates 8 additional F calls: 1 call to F(3), 2 calls to F(2), 3 calls to F(1), and 2 calls to F(0).

3.c. Note that in 3.b. the number of calls in "suspended state" (that is, calls that are waiting for a returned value) is at most 3, because (look at the first few lines of the trace) F(4) calls on F(3) which calls on F(2) which calls on F(1) which then returns a value. Explain the mechanism by which it is possible to keep these function calls waiting.

4. The following recursive function is supposed to compute the result of x to the n-th power, where x is an arbitrary number and n is a positive integer. There are two reasons why it does not work. Explain those reasons, then fix the function so that it works.

int pow(int x, int n)
{
    return x * pow(x, n-1);
}

5.a. Suppose you're given an array of integers. A recursive way to find the smallest element in the array is to compare the smallest element of the first half of the array with the smallest element of the second half of the array and return the smallest of those two numbers. The recursive nature of this solution is embedded in the fact that finding the smallest element of a given half of the original array (either the lower half or the top half) is exactly the same problem as the original problem, only now it's applied to a smaller array. Describe how this algorithm would work (that is, trace the algorithm) on the following array: { 73, -21, -22, 48, 0, 724, 214, -93, 1721, 4 }.

5.b. Now write a recursive function int recSmallest(int a[], unsigned int begin, unsigned int end) which returns the smallest element of the integer array a using the idea described above. Also write a main function to test your recursive function. You may use a small fixed length for the array (say, 10).