CS 14 - Homework Assignment 2

CS 14 Homework Assignment 2

This assignment is due at 8:00 pm on Wednesday, October 22, 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] 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, and should throw an exception for invalid inputs.

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

Don't worry about invalid inputs, since you can make sure that all inputs are valid when you call the function. 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.

3. [5 points] Write a recursive function int powersOf2(int n) to compute powers of 2, using the fact that

2^n = 2^(n/2) * 2^(n/2),             if n is even
2^n = 2 * 2^((n-1)/2) * 2^((n-1)/2), if n is odd
2^n = 1,                             if n equals 0

Make sure to account for invalid inputs, such as negative n values.

4. [3 points] In your own words, explain what an Abstract Data Type is.

5. [3 points] Write a template function called max that returns the maximum element of an array.

6. [3 points] Write a template function called sum that returns the sum of all elements of an array.

7. [3 points] Write a template function swap4() that takes four arguments and swaps them cyclically. For example, if the type was int and 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.

8. [3 points] What does it mean to say that an operation takes constant time? Note: I don't want an answer of the form "It means it's O(1)." I want an explanation for what O(1) and constant time both mean.

9. [2 points] What is the runtime complexity of the function below?

void f(int a[], int n)
{
    for (int i = 0; i < n; ++i)
    {
        for (int j = n - 3; j < n; ++j)
        {
            a[i] = i + j;
        }
    }
}

10. [2 points] What is the runtime complexity of the function below?

void f(int a[], int n)
{
    for (int i = 0; i < n; ++i)
    {
        for (int j = n / 2; j < n; ++j)
        {
            a[i] = i + j;
        }
    }
}

11. [2 points] What is the runtime complexity of the function below?

void f(int a[], int n)
{
    for (int i = 0; i < n; ++i)
    {
        // some operation that takes O(n*log(n)) to execute
        
        for (int j = 0; j < 5; ++j)
        {
            // some operation that takes O(log(n)) to execute
        }
    }
}

12. [2 points] Order the following runtime complexities in increasing order of how fast they are, that is, slowest first, fastest last. Note: n! is the factorial of n.

O(n), O(n!), O(log(n)), O(sqrt(n)), O(n^2), O(n*log(n))