CS 14 - Homework Assignment 1

CS 14 Homework Assignment 1 - 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.

Note: my solutions are much more detailed than what I expect you to write in your own solutions. I'm writing such detailed solutions so that you can learn more from them.

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.

Solution:

At first, since you don't know anything about the rest of the numbers in the sequence, assume that the largest is the first number. If you have to change that assumption later, fine.

1. Assume that the first number is the largest of the sequence.
2. Compare the current largest with the second number from the sequence. If the second number is larger than the current guess for the largest, make the second number the new guess for the largest.
3. Compare the current largest with the third number from the sequence. If the third number is larger than the current guess for the largest, make the third number the new guess for the largest.
4. Compare the current largest with the fourth number from the sequence. If the fourth number is larger than the current guess for the largest, make the fourth number the new guess for the largest.
.... Keep going as above, until you've checked the current guess against all numbers from the sequence, at which point the current guess is the largest number of the sequence.

A more succint way of saying the same thing is:

1. Assume that the first number is the largest of the sequence.
2. Compare each number from the sequence, starting from the second one and until the end of the sequence, against the current guess for the largest. Whichever one is larger, make that the new current guess for the largest.
3. When you're done comparing against all numbers from the sequence, the current guess for the largest is the largest.

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.

Solution: Following straight from the succint solution to the previous problem:

int max(int a[], unsigned int length)
{
    // assume the first number is the largest
    int largest = a[0];
    
    // compare each number against the current guess
    for (unsigned int i = 0; i < length; ++i)
    {
        // if we found a larger number, update largest
        if (a[i] > largest)
        { largest = a[i]; }
    }
    
    return largest;
}

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.

Solution: Any non-zero choice for x0 will do. I'll make a wacky choice, just to show how quickly this process converges to the square root of 2: x0 = 15.

x0 = 15
x1 = x0 / 2 + 1 / x0 = 7.56666667
x2 = x1 / 2 + 1 / x1 = 3.91549192
x3 = x2 / 2 + 1 / x2 = 2.21314171
x4 = x3 / 2 + 1 / x3 = 1.55841721
x5 = x4 / 2 + 1 / x4 = 1.42088530
x6 = x5 / 2 + 1 / x5 = 1.41422923
x7 = x6 / 2 + 1 / x6 = 1.41421356 <--- this is already the right answer for these many digits of precision
x8 = x7 / 2 + 1 / x7 = 1.41421356
x9 = x8 / 2 + 1 / x8 = 1.41421356
x10 = x9 / 2 + 1 / x9 = 1.41421356

If you're curious as to why this happens, come to see me in my office hours and I'll explain it then.

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.

Solution:

float f(float x)
{
    return (x / 2.0 + 1.0 / 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.

Solution:

#include <iostream>

float f(float x)
{
    return (x / 2.0 + 1.0 / x);
}

int main()
{
    std::cout << "Computing the square root of 2..."
              << std::endl << std::endl;
              
    // the while loop here is used to make sure that the
    // user enters valid information, namely, a non-zero x0
    float x0 = 0.0;
    while (x0 == 0.0)
    {
        std::cout << "Please enter a non-zero starting number"
                  << std::endl;
                  
        std::cin >> x0;
    }
            
    // the while loop here is used to make sure that the
    // user enters valid information, namely, a number of
    // iterations that is at least 1
    unsigned int max_iters = 0;
    while (max_iters < 1)
    {
        std::cout << "Please enter the number of iterations to perform"
                  << std::endl;
                  
        std::cin >> max_iters;
    }
    
    // let's print 10 digits, shall we?
    std::cout.precision(10);
    
    // let's be nice and print the user's initial value
    float x = x0;
    std::cout << "x0 = " << x0 << std::endl;
    
    // now compute and print each subsequent approximation
    for (unsigned int i = 0; i < max_iters; ++i)
    {
        x = f(x);
        std::cout << "x" << (i+1) << " = " << x << std::endl;
    }
    
    return 0;
}

Here's a printout of an actual run of this program:

Computing the square root of 2...

Please enter a non-zero starting number
15
Please enter the number of iterations to perform
20
x0 = 15
x1 = 7.566666603
x2 = 3.915491819
x3 = 2.21314168
x4 = 1.558417201
x5 = 1.420885324
x6 = 1.414229274
x7 = 1.414213538
x8 = 1.414213538
x9 = 1.414213538
x10 = 1.414213538
x11 = 1.414213538
x12 = 1.414213538
x13 = 1.414213538
x14 = 1.414213538
x15 = 1.414213538
x16 = 1.414213538
x17 = 1.414213538
x18 = 1.414213538
x19 = 1.414213538
x20 = 1.414213538

Now, if you observe carefully, you'll notice that the results here do not agree with those we calculated earlier (1.414213538 instead of 1.41421356). How come?

The reason for this discrepancy is that I asked you to implement a function that takes and returns a float, rather than a double. If you replace every float above with double and run the program again, you'll obtain:

Computing the square root of 2...

Please enter a non-zero starting number
15
Please enter the number of iterations to perform
20
x0 = 15
x1 = 7.566666667
x2 = 3.915491924
x3 = 2.213141713
x4 = 1.558417204
x5 = 1.420885296
x6 = 1.414229226
x7 = 1.414213562
x8 = 1.414213562
x9 = 1.414213562
x10 = 1.414213562
x11 = 1.414213562
x12 = 1.414213562
x13 = 1.414213562
x14 = 1.414213562
x15 = 1.414213562
x16 = 1.414213562
x17 = 1.414213562
x18 = 1.414213562
x19 = 1.414213562
x20 = 1.414213562

And now we get the expected answer. What happened here is that floats don't have enough precision to hold a result accurate to 10 decimal digits or more. For that, we need doubles.

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).

Solution: From the trace below we see that F(5) generates 14 F-calls, 1 to F(4), 2 to F(3), 3 to F(2), 5 to F(1), and 3 to F(0). Notice something about these numbers of calls (1, 2, 3, 5, 3)? With the exception of the first and the last ones, these numbers follow something similar to the Fibonacci sequence! That makes sense.

Since F(n) = F(n-1) + F(n-2), the number of calls that F(n) generates, call it #F(n), is 2 [F(n-1) and F(n-2)] plus all the calls generated by F(n-1) and F(n-2) themselves. Hence,

#F(n) = 2 + #F(n-1) + #F(n-2), n > 1

which is another recursive relation. The base cases are:

#F(0) = 0
#F(1) = 0

since F(0) and F(1) do not generate F-calls at all (they're the base cases of the Fibonacci sequence). You can try it yourself and you'll find out, from the recursion above, that #F(5) = 14, as the trace below demonstrates.

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

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);
}

Solution: The reasons are: (1) there is no base case, meaning that this function would try to recurse infinitely many times (of course, a stack overflow would prevent an actual infinite number of recursive calls, though your program would crash), (2) you won't be able to get results bigger than 2 to the 31st power, since that's the largest integer you can have. To get larger results, you need to use double instead of int for the result. Here's the correct implementation:

double pow(double x, int n)
{
    if (n == 0) // base case
        return 1.0;
    else
        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.

Solution:

#include <iostream>

int recMin(int a[], unsigned int begin, unsigned int end) 
{
    // base case: sub-array of size 1
    if (begin == end)
        return a[begin];

    // notice that this is integer division
    int middle = (begin + end) / 2;

    // get the minimum value in each sub-array
    int left_min = recMin(a, begin, middle);
    int right_min = recMin(a, middle + 1, end);
   
    // return the min of each sub-array's min
    if (left_min < right_min)
        return left_min;
    else
        return right_min;
}

int main()
{
    std::cout << "Testing recMin()..."
              << std::endl << std::endl;
              
    // the while loop here is used to make sure that the
    // user enters valid information, namely, a positive
    // number for the size of the array
    unsigned int length = 0;
    while (length == 0)
    {
        std::cout << "Please enter the size of the array"
                  << std::endl;
                  
        std::cin >> length;
    }
            
    std::cout << std::endl;
            
    // gather array elements from the user
    int * a = new int[length];
    for (unsigned int i = 0; i < length; ++i)
    {
        std::cout << "Please enter the value for element"
                  << " a[" << i << "]" << std::endl;
                  
        std::cin >> a[i];        
    }
            
    std::cout << std::endl;
    
    // let's print the array back to the user
    // so he can see what he entered
    std::cout << "You entered the following array:"
              << std::endl;
    std::cout << "[" << a[0];  
    for (unsigned int i = 1; i < length; ++i)
    {
        std::cout << ", " << a[i];        
    }
    std::cout << "]" << std::endl << std::endl;  
    
    // now find and print the minimum array element
    std::cout << "The minimum element is:" << std::endl;
    std::cout << recMin(a, 0, length-1) << std::endl;
    
    return 0;
}

Here's the output of an actual run:

Testing recMin()...

Please enter the size of the array
8

Please enter the value for element a[0]
5001
Please enter the value for element a[1]
33
Please enter the value for element a[2]
-1023
Please enter the value for element a[3]
59
Please enter the value for element a[4]
121
Please enter the value for element a[5]
-199
Please enter the value for element a[6]
1
Please enter the value for element a[7]
13

You entered the following array:
[5001, 33, -1023, 59, 121, -199, 1, 13]

The minimum element is:
-1023

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

Solution: The Principle of Encapsulation states that, unless otherwise required, all member variables of a class and all utility member functions of a class should be made private. There are several good reasons for such a recommendation:

private member variables can be neither inadvertently nor intentionally changed by directly accessing them from other classes. The only means of changing them, if any are available at all, is through mutator functions. For example, if you have a class with two member variables to represent a date, named 'day' and 'month', then having them public lets any class access them directly and change them to anything at all. Nothing prevents someone from setting 'day' to '37' and 'month' to -4, for instance.

keeping your member variables private and having associated public mutator functions lets you enforce preconditions. In the example above, for instance, one should make 'day' and 'month' private and then have the following public mutator function:

// having the int's be unsigned guarantees that
// they are not negative integers
void setDate(unsigned int d, unsigned int m)
{
     if (m == 0 || m > 12)
     {
         // throw an error: m must be in the range [1, 12]
     }

     if (d == 0)
     {
         // throw an error: d must not be zero
     }

     switch (m)
     {
         case 2:  // February
             if (d > 29)
             {
                 // throw an error: February may have
                 // only up to 29 days

                 // if we also had a member variable
                 // to store the year, we'd then also
                 // test for leap years
             }
         break;

         case 1:  // January
         case 3:  // March
         case 5:  // May
         case 7:  // July
         case 8:  // August
         case 10: // October
         case 12: // December
             if (d > 31)
             {
                 // throw an error: these months may have
                 // only up to 31 days
             }
         break;

         default: // all other months
             if (d > 30)
             {
                 // throw an error: these months may have
                 // only up to 30 days
             }
         break;
     }

     // now we know that d and m are valid day and
     // month values so all that's left is to set our
     // private member variables accordingly

     day = d;
     month = m;
}

having your member variables private hides from clients of your classes the internals of those classes. Thus, the code they write using your classes will not depend on those internals, which means that you're free to change your classes' internals any time you need to (for example, to improve efficiency or fix bugs) without affecting any client code

making your member variables private also has the effect of simplifying the interface of your classes, which makes it easier for the clients of your classes to learn how to use them.

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.

Solution: A book has a title, an ISBN number, one or more authors, a publisher, a price, a number of pages, and probably many other properties. These would all be represented by member variables and would then have associated accessor functions. How about mutator functions? Of the properties I mentioned above, only the price is subject to change; the title, for example, should not change once a book object is created. Thus, the only member variable of those I mentioned above which I'd have a mutator function for would be the price. So here's my UML diagram for this class:

============================================================
                            Book
============================================================
- string title
- string ISBN // not an int b/c ISBN numbers may have an X
- string author_list[]
- string publisher
- int num_of_pages
- float price
============================================================
+ Book() // constructor... needs some parameters!
+ string getTitle() const
+ string getISBN() const
+ string getAuthor(unsigned int index) const
+ string * getAuthorArray() const
+ string getPublisher() const
+ int getNumberOfPages() const
+ float getPrice() const
+ void setPrice(float cost)
============================================================

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 ?

Solution:

#include <iostream>
#include <string>

using namespace std;

class ToggleButton
{
     private:
         string label;
         bool isOn;

     public:
         ToggleButton(string lbl, bool on);
         ToggleButton(string lbl);
         string getLabel() const;
         void press();
};

// this is the general constructor
ToggleButton::ToggleButton(string lbl, bool on)
{
     label = lbl;
     isOn = on;
}

// this constructor creates a ToggleButton that
// starts in the OFF position
ToggleButton::ToggleButton(string lbl)
{
     label = lbl;
     isOn = false;
}

string ToggleButton::getLabel() const
{
     return label;
}

void ToggleButton::press()
{
     // this is a quick way of inverting the
     // value of a boolean variable
     isOn = !(isOn);

     // here's the long way of doing the same thing:
     /*
     if (isOn == true)
          isOn = false;
      else
          isOn = true;
     */

     cout << "Button '" << label
          << "' is now in the ";

     if (isOn)
         cout << "ON";
     else
         cout << "OFF";

     cout << " state." << endl;
}

int main ()
{
     ToggleButton playBtn = ToggleButton("Play");
     playBtn.press();
     playBtn.press();
     playBtn.press();

     return 0;
}

Here's the output:

Button 'Play' is now in the ON state.
Button 'Play' is now in the OFF state.
Button 'Play' is now in the ON state.

The questions:

Why is it convenient to have two constructors, rather than just one, and why should they have the parameter lists given?

Answer: the general constructor needs the parameter list it has because it needs both a label and a boolean state indicator (on or off) to be able to create a ToggleButton. The other constructor is convenient because one might have many buttons in one's application and it could be that most of those buttons start their lives in the OFF state. Then, rather than have to create them with the longer-version constructor, it's much easier simply to create them with the constructor that sets the state to be OFF by default.

What should the second constructor do with the member variable isOn ?

Answer: there is no definitive answer here, but the most natural thing to do, in my opinion, is to set it to false. That corresponds to the idea that most buttons are created in their OFF state.