CS 12 - Homework Assignment 2

CS 12 Homework Assignment 2

This assignment is due at 8:00 pm on Sunday, October 19, 2003.

Your solutions must be submitted electronically, as a plain ASCII/text file (.txt), a PostScript document (.ps), or a PDF document (.pdf). Any other formats will be considered the same as not turning in the assignment at all (so, no Microsoft Word documents, for example). To submit your work, use the turn-in system. Do remember that the turn-in system only submits files that have been stored on the CS department machines so, if you are approaching the deadline, remember to give yourself time to copy files to the appropriate location.

1. [3 points] Explain what's wrong with the following loop and then rewrite it correctly.

int x = 0;
while (x < 10)
{ std::cout << 2*(x+1) << std::endl; }

2. [2 points] Replace the while loop from the previous problem with a for loop that accomplishes the same result (without the error, of course).

3. [3 points] What's the output of the following loop? Explain your answer.

for (int x = 0; (x++) < 10; ++x)
{ std::cout << 2*(++x) << std::endl; }

4. [7 points] The function below has a few errors. Explain what the function is supposed to do, then fix it so that it works correctly.

int f(int a[], const unsigned int length)
{
    int x;
    for (int i = 0; i <= length; ++i)
    { x += a(i); }
    
    return x / length;
}

5. [3 points] The function below has two subtle errors. Explain what the function is trying to do, then fix it so that it works correctly.

void f(int a, int b)
{
    for (int i = a; i <= b; ++i)
    { std::cout << (1 / i) << std::endl; }
}

6. [5 points, tricky] The simple-looking boolean expression below always evaluates to false, no matter what the values of x and y are. Why is that?

( (x++) == (++y) ) and ( (++x) == (y++) )

7. [3 points] What's the block of code below trying to do? What's its actual output?

int x = 0;
while (x = 0)
{
    std::cout << "Please enter a value for x:"
              << std::endl;
    std::cin >> x;
}
std::cout << "Thank you. You entered x = "
          << x << std::endl;

8. [3 points] What's the output of the program below? Explain your answer.

void f(int x)
{
    ++x;
    std::cout << "x = " << x << std::endl;
}

int main()
{
    for (int i = 0; i < 3; ++i)
    {
        f(i);
        std::cout << "i = " << i << std::endl;
    }
    
    return 0;
}

9. [3 points] Write a function swap4() that takes four integer arguments and swaps them cyclically. For example, if a = 1, b = 2, c = 3, and d = 4 before the function is called, then after swap4(a, b, c, d) is called, we'll have a = 2, b = 3, c = 4, and d = 1. Calling it again would result in a = 3, b = 4, c = 1, and d = 2. Calling it one more time would result in a = 4, b = 1, c = 2, and d = 3.

10. [5 points] As discussed in the lectures, the array implementation of a queue is not a very good one because dequeue'ing the queue (no pun intended) requires that we move every remaining element one position towards the front. Here's the enqueue() function for an array-based queue of integers:

void enqueue(int x)
{
    // we should really check to make sure that the queue
    // is not full before we enqueue, ie, we need to make
    // sure that 'back' does not grow beyond the size of
    // the array supporting the queue but we'll ignore
    // that issue for now
    
    queueArray[++back] = x;
}

Write the dequeue() function for such a queue. Remember that it must not only return the element stored at the front of the queue, but also move everyone else one position towards the front. Note that the name of the array supporting the queue is queueArray.

11. [2 points] Write a recursive function called fun, that computes a number obtained by multiplying the previous number by 2 and then subtracting 3. The first number is 7. Thus,

n        fun(n)
------------------------
1        7
2        2*7  - 3 = 11
3        2*11 - 3 = 19
4        2*19 - 3 = 35
etc

The function should return the n-th such number, when given a value for n.

12. [5 points] Suppose you start one of those email chains, in which you send one message to someone asking that person to forward it to, say, 10 friends. Then, each of those 10 people is supposed to send the same message to 10 more people, and so on. Let num_friends be the number of people to send the message to (in the example above, num_friends was 10) and let depth be the depth of the chain, that is, how many "levels" the message goes through without interruption. For example, if I sent one message to 10 friends, and each of them sent to 10 other friends, we'd have a depth of 2. At this point, there have been 110 messages sent total (10 that I sent, plus 10 sent by each of the 10 people who received it from me).

The goal of this problem is to write a function that tells you how many messages will have been sent for a given choice of num_friends and of depth. Let's call that function numMessagesSent, so that its header is

long long int numMessagesSent(int num_friends, int depth)

The reason for the long long int is that we'll be needing very large integers. Now, see if you agree with this reasoning:

The number of messages a single person sends is num_friends. Each of those people will also send that many messages, so the total number of messages sent because of a single person is:

numMessagesSent(num_friends, depth) =
    num_friends + num_friends * numMessagesSent(num_friends, depth - 1)

which you can simplify to

numMessagesSent(num_friends, depth) =
    num_friends * (1 + numMessagesSent(num_friends, depth - 1))

Aha! This is a recursive relation, isn't it? Now we need a base case. Going back to the example above, we see that when depth is 1, that is, when I send my messages and no one continues the chain, then the total number of messages sent is simply how many messages I sent, namely, num_friends. Thus, the base case is:

numMessagesSent(num_friends, 1) = num_friends

Ok, now for what you have to do. Write the C++ implementation of the recursive function

long long int numMessagesSent(int num_friends, int depth)

Then, write a main() program asking the user for how many friends he wants to send the message to and to which depth he hopes people will keep the chain going. Then, print those two inputs as well as the total number of messages which will be sent. Try your program with num_friends equal to, say, 3 and depth equal to, say, 20. Keep in mind that there are approximately 6.3 billion people in the world today.