CS 14 - Homework Assignment 1

CS 14 Homework Assignment 1

This assignment is due on Wednesday, October 8, 2003, at the start of the lecture, and is worth 35 points. You must hand your solutions on paper, and printed (ie, not hand-written). Please staple your solutions.

Note: In the problems below, don't worry about writing complicated main() functions. Write the simplest main() needed to get the job done. The point here is not to write complete programs, but to exercise your problem-solving skills. In this context, main() is merely a tool.

1. [3 points] Suppose I gave you a sequence of integer numbers (not necessarily positive or even distinct). In English, without using any C++ code at all, explain how you could determine the largest number of the entire sequence. Be as explicit and precise in your argument as possible, but don't write an essay. Instead, give short instructions of the form "pick the fifth number" or "square the number you selected", etc.

2. [3 points] Now write a function int max(int a[], unsigned int length), taking as arguments an array of integers and its corresponding length, that determines and returns the largest integer present in the array.

3. Here's a cool, but mysterious, way to numerically compute the square root of 2: start with any non-zero number, call it x0, then compute the number x1 = x0 / 2 + 1 / x0. Now that you have x1, compute x2 by applying the same formula to x1, namely, x2 = x1 / 2 + 1 / x1. Then compute x3 by applying the same formula again, this time to x2, x3 = x2 / 2 + 1 / x2, and so on. You will notice that the sequence of numbers { x0, x1, x2, x3, ... } converges fairly quickly to the numerical value of the square root of 2, that is, 1.41421356...

a. [2 points] Let's try that. Choose a number for x0 and then write the result of computing the first 10 numbers of the sequence, that is, print the values of { x0, x1, x2, ..., x9, x10 } for your choice of x0. You might want to use a calculator.

b. [2 points] Now write a function float f(float x), taking for argument a number x (not necessarily an integer), which applies the formula above to x, returning the result. In other words, you must implement the function f(x) = x / 2 + 1 / x.

c. [3 points] Next, write a small C++ program with a main function in such a way that it asks the user for a non-zero starting number x0 and for a maximum number of iterations, maxIters, then repeatedly applies f() to the result obtained from the previous application of f(), printing the result every time, and doing it maxIters times. In other words, your main function will be computing and printing x1 = f(x0), x2 = f(x1), x3 = f(x2), etc, maxIters times.

In your solution, show your complete program and also a printout of a few trial runs.

4. [2 points] 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

How many function calls of the form F(something) are made when computing F(5)? 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(3): (Notice the indentation pattern; it will help you understand what's happening.)

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 (1+1) = 2
F(3) calls F(1)
           F(1) returns 1
F(3) returns (2+1) = 3

So, the call to F(3) generates 1 call to F(2), 2 calls to F(1), and 1 call to F(0), for a total of 4 additional F calls (besides the call to F(3) that originated the rest).

5. [2 points] 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);
}

6. [3 points] 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 comes from 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. For example, a trace of the execution of this algorithm (call it recMin) on the array { 73, -21, -22, 48, 0, 724, 214, -93, 1721, 4 } goes as follows:

recMin on (73, -21, -22, 48, 0, 724, 214, -93, 1721, 4)
      calls recMin on (73, -21, -22, 48, 0)
           calls recMin on (73, -21, -22)
                calls recMin on (73)
                returns 73
                calls recMin on (-21, -22)
                     calls recMin on (-21)
                     returns -21
                     calls recMin on (-22)
                     returns -22
                returns min(-21, -22) = -22
           returns min(73, -22) = -22
           calls recMin on (48, 0)
                calls recMin on (48)
                returns 48
                calls recMin on (0)
                returns 0
           returns min(48, 0) = 0
      returns min(-22, 0) = -22
      calls recMin on (724, 214, -93, 1721, 4)
           calls recMin on (724, 214, -93)
                calls recMin on (724)
                returns 724
                calls recMin on (214, -93)
                     calls recMin on (214)
                     returns 214
                     calls recMin on (-93)
                     returns -93
                returns min(214, -93) = -93
           returns min(724, -93) = -93
           calls recMin on (1721, 4)
                calls recMin on (1721)
                returns 1721
                calls recMin on (4)
                returns 4
           returns min(1721, 4) = 4
      returns min(-93, 4) = -93
returns min(-22, -93) = -93

Write a recursive function int recMin(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.

7. [2 points] Explain, in your own words, what the Principle of Encapsulation is all about.

8. [3 points] Draw an UML diagram for a class Book. It's up to you to come up with its member variables and member functions. I want at least two member variables and at least two member functions.

9. [10 points] Suppose that you're going to write a graphical user interface program to control your VCR. Clearly, you will need a class to represent buttons that can be toggled on or off, such as the "Play" button or the "Pause" button. Write both the declaration and implementation for a class ToggleButton described by the UML diagram below:

The press() function should flip the button's on/off state, then print the button's label and whether the button is now on or off. Answer the following questions:

Why is it convenient to have two constructors, rather than just one, and why should they have the parameter lists given?
What should the second constructor do with the member variable isOn ?