## CS 14 Homework Assignment 2 - Solutions

CS 14 Homepage
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.
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] 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.

Solution:
```int fun(int n)
{
if (n < 1) // invalid cases
throw std::domain_error("n must be positive.");
else
if (n == 1) // base case
return 7;
else
{
// make the recursive call
return (2 * fun(n-1) - 3);
}
}
```

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.

Solution:
```#include <iostream>

long long int numMessagesSent(int num_friends, int depth)
{
if (depth == 1) // base case
return num_friends;
else
{
// make the recursive call
return (num_friends *
(1 + numMessagesSent(num_friends, depth - 1)));
}
}

int main()
{
std::cout << "Let's spam-flood the internet!"
<< std::endl;

// use a loop to ask the user for proper input
// num_friends must be greater than zero

int num_friends = 0;
while (num_friends <= 0)
{
std::cout << "Please enter how many people to send a message to..."
<< std::endl;

std::cin >> num_friends;
}

// use a loop to ask the user for proper input
// depth must be greater than zero

int depth = 0;
while (depth <= 0)
{
std::cout << "Please enter how many levels you hope the chain will"
<< " go through unbroken..."
<< std::endl;

std::cin >> depth;
}

std::cout << "This is how many messages total will have been sent: "
<< std::endl
<< numMessagesSent(num_friends, depth)
<< std::endl;

return 0;
}

Here's an actual run:

Let's spam-flood the internet!
Please enter how many people to send a message to...
3
Please enter how many levels you hope the chain will go through unbroken...
20
This is how many messages total will have been sent:
5230176600
```
Notice that even sending the message to a small number of people and using a reasonably small depth, we still end up sending almost one message per person on the planet! So, please, never join those email chain letters, even if the reason sounds good (virus alerts, pleas to help sick children, environmental causes, etc).
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.

Solution:
```int powersOf2(int n)
{
if (n < 0) // invalid cases
throw std::domain_error("n must be positive.");
else
if (n == 0) // base case
return 1;
else // n > 0
{
// make the recursive calls, depending on
// whether n is even or odd

if (n % 2 == 0)
{
// n is even

int pow = powersOf2(n / 2);
return (pow * pow);
}
else
{
// n is odd

int pow = powersOf2((n - 1) / 2);
return (2 * pow * pow);
}
}
}
```
Note that: (1) we don't have to worry about integer division when dividing (n-1) by 2 because when n is odd, (n-1) is even, so it's divisible by 2; and (2) it's wise to save the result of the recursive call into a temporary variable so that we don't waste time computing the same thing twice. That is, I wrote
```int pow = powersOf2(n / 2);
return (pow * pow);
```
rather than
```return (powersOf2(n / 2) * powersOf2(n / 2));
```
Likewise for the odd case. Remember: CS 14 is about writing efficient code!
4. [3 points] In your own words, explain what an Abstract Data Type is.

Solution: An ADT is a data type whose implementation is separated from its interface. Users of an ADT are typically concerned only with the ADT's interface and semantics, that is, only with how it's supposed to be used (interface) and what results are expected from its use (semantics). An ADT is how data encapsulation is achieved, that is, by separating the implementation from the interface, the ADT's internals are hidden (encapsulated) from the user.
5. [3 points] Write a template function called `max` that returns the maximum element of an array.

Solution:
```template<class T>
T max(const T a[], const unsigned int length)
{
T the_max = a[0];

for (unsigned int i = 1; i < length; ++i)
{
if (a[i] > the_max)
{ the_max = a[i]; }
}

return the_max;
}
```

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

Solution:
```template<class T>
T sum(const T a[], const unsigned int length)
{
T the_sum = a[0];

for (unsigned int i = 1; i < length; ++i)
{ the_sum += a[i]; }

return the_sum;
}
```

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

Solution: This is very similar to the `swap` function we discussed in lecture. This one, too, must take its arguments by reference.
```template<class T>
void swap4(T & a, T & b, T & c, T & d)
{
T temp = a;
a = b;
b = c;
c = d;
d = temp;
}
```

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.

Solution: An operation is said to take constant time or to be of runtime complexity `O(1)` when the time it takes to execute does not depend on the size of the input to the operation. Thus, for example, the assignment `int x = y` takes the same time regardless of whether `y` equals 0 or 1 billion. It is, therefore, an operation taking constant time.
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;
}
}
}
```
Solution: Nope, it's not `O(n^2)`. Just because you have two nested loops, it does not always mean that you have an `O(n^2)` operation. Here, it's easy to see that `j` always goes through only 3 values, regardless of the value of `n`. Since that happens for each value of the outer loop variable `i`, which does go through `n` values, the total number of iterations is `3n`, that is, `O(n)`.
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;
}
}
}
```
Solution: The inner loop variable `j` goes through `(n / 2)` values, which does depend on the value of `n`. Since that happens for each value of the outer loop variable `i`, which does go through `n` values, the total number of iterations is `n * (n / 2)`, that is, `O(n^2)`.
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
}
}
}
```
Solution: For each iteration of the outer loop variable `i`, which goes through `n` values, we have one `O(n*log(n))` operation and exactly 5 executions of a `O(log(n))` operation. Thus, each `i` iteration takes time `O(n*log(n) + 5*log(n))` = `O((n+5)*log(n))`. The 5 is irrelevant compared to `n` (think of what happens when `n` is very large), so each `i` iteration takes time `O(n*log(n))`. Since there are `n` such iterations, the total time spent executing this function is `O(n^2*log(n))`.
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))
```
Solution:
```O(n!), O(n^2), O(n*log(n)), O(n), O(sqrt(n)), O(log(n))
```