Solutions to Quiz/Homework Assignment #1
CSE326

1.

$\sum_{i=0}^{\infty} x^i = 1/(1-x)$ is true if and only if:

(a)

-1 < x < 1

(b)

$x \neq 1$

(c)

0 < x < 1

(d)

x > 1

(e)

x = 1 / 2

The correct answer is (a). I will first show that $-1 < x < 1 \Rightarrow \sum_{i=0}^{\infty} x^i = 1/(1-x)$ (the if direction), and then I will show that these are the only xs that work (the only if direction). The book gives a reasonable demonstration that the formula holds for 0 < x < 1, so I will take that as a given. When x = 0 we have:

$$\sum_{i=0}^{\infty} 0^i = 0^0 + 0^1 + 0^2 + 0^3 \cdots$$

By definition, we know that 0a = 0 for any number a, so all terms but the first are zero. The first term is just the empty product (which can also be written $\prod_{\emptyset}$)--a product of zero numbers--which is defined to be the multiplicative identity, 1 (similarly the empty sum, $\sum_{\emptyset}$, is defined to be the additive identity, 0). Thus,

$$\sum_{i=0}^{\infty} 0^i = 1 = \frac{1}{1-0}$$

Now spose -1 < x < 0. Then

$$\sum_{i=0}^{\infty} x^i = \sum_{i=0}^{\infty} (x^{2i} + x^{2i... ...)\sum_{i=0}^{\infty} x^{2i} = \frac{1+x}{1-x^2} = \frac{1}{1-x}$$

It remains to show that the formula is false for values of x not in the interval (-1,1). Spose x > 1. Then all terms in the series are positive and non-decreasing, thus the series cannot converge to the finite (and negative) value 1/(1-x). If x < -1 then the series can be rewritten as $(1+x)\sum_{i=0}^{\infty} x^{2i}$. Each term is positive and non-decreasing, and the quantity (1+x) is finite and non-zero, so again the series cannot converge to the finite value 1/(1-x). Now we have two special cases: $x = \pm 1$. If x = 1 then clearly the series diverges to $\infty$. If we defined $1/0 = \infty$, then the formula would be true in this case, but we don't. As Steve said in class, $\infty$ and ``undefined'' are not the same. If x = -1 then the partial sums of the series alternate between 1 and 0. So the average value is 1/2 = 1/(1-(-1)), but the series doesn't converge so the formula doesn't hold.

2.

Note: this question was removed from the quiz and homework.

Which of the following formulas has the smallest value?

(a)

$(\sum_{i=1}^5 i)(\sum_{i=1}^5 i)$

(b)

$\sum_{i=0}^{100} (-5)^i$

(c)

$\sum_{n=0}^5 (\sum_{i=0}^n 2^i)$

(d)

$\sum_{i=0}^{10} 2^3$

Just FYI:

(a)

Using the rule that $\sum_{i=1}^n i = \frac{n (n+1)}{2}$, this is:

$\frac{5 (5+1)}{2}^2 = 15^2 = 225$

(b)

Let's just get a feel for this one. -5¹⁰⁰ is the largest term in this series. It's equal to 5¹⁰⁰ since (-1)ⁿ = 1 for even n. That's a huge number. It gets a chunk of -(5⁹⁹) taken out of it, but that's still 4 * 5⁹⁹, and the rest of the series just adds more. So this is very big.

(c)

Using the rule that $\sum_{i=0}^n 2^i = 2^{n+1} - 1$, this becomes

$\sum_{n=0}^5 (2^{n+1} - 1) = 2 \sum_{n=0}^5 2^n + \sum_{n=0}^5 1$

Using the same rule again, we get:

2 (2⁵⁺¹) + 5 = 128 + 5 = 133

(d)

$\sum_{i=0}^{10} 2^3 = 2^3 \sum_{i=0}^{10} 1 = 2^3 * 11 = 88$

So, letter (e) is the smallest.

3.

Which of the following formulas has the greatest value?

(a)

$\log_{10} 1024$

(b)

$(\log_{13} 343)/(\log_{13} 7)$

(c)

$\log_2 (1/128)$

(d)

$\log_8 256$

(e)

$(\log_a a^2) + (2\log_a \sqrt{a})$

(a)

Logarithms are monotonically increasing, hence $\log_{10} 1024 > \log_{10} 1000 = 3$.

(b)

Using the rule $\log_A B = \frac{\log_C B}{\log_C A}$, we get:

$\frac{\log_{13} 343}{\log_{13} 7} = \log_7 343 = \log_7 7^3 = 3$.

(c)

$\log_2 (1/128) = \log_2 2^{-7} = -7$.

(d)

As for (b), $\log_8 256 = \frac{\log_2 256}{\log_2 8} = \frac{\log_2 2^8}{\log_2 2^3} = 8/3$.

(e)

$(\log_a a^2) + (2\log_a \sqrt{a}) = 2 + 2(1/2) = 3$.

So, letter (a) is the greatest.

4.

Which of the following is not equal to a³ + 4ab²?

(a1)

$a(a^2 + \frac{6ba}{3ab^0}^2)$

(a2)

$a(a^2 + \frac{6ba}{3(ab)^0}^2)$

(b)

$\frac{a^4b}{ab} + a(2b)^2$

(c)

((2^1+a+b)(2^1+a-b)a²b² + a⁴) / (a4^a)

(d)

$4\frac{((2ab)^2 + a^4)}{4a}$

(e)

none of these

Note: I am including two versions of (a) in the solutions to reflect the original (a1) and updated (a2) versions of the homework. As written on the quiz, (a) was not a correct answer. The five people who answered (a) should pay special attention to this solution because, due to an error on our part, they were not required to redo this problem on their homework.

(a1)

$a(a^2 + \frac{6ba}{3ab^0}^2) = a(a^2 + \frac{6ba}{3a}^2) = a(a^2 + (2b)^2) = a(a^2 + 4b^2) = a^3 + 4ab^2$

(a2)

$a(a^2 + \frac{6ba}{3(ab)^0}^2) = a(a^2 + \frac{6ba}{3}^2) = a(a^2 + (2ab)^2) = a(a^2 + 4a^2b^2) = a^3 + 4a^3b^2$

(b)

$\frac{a^4b}{ab} + a(2b)^2 = a^3 + a(4b^2) = a^3 + 4ab^2$

(c)

I actually intended this to be written $((2^{1+a+b})(2^{1+a-b})(a^2b^2 + \frac{1}{4}a^4)) / (a4^a)$, in which case the answer would have been (e), but instead (c) evaluates to:

$$\frac{(2^{1+a+b})(2^{1+a-b})a^2b^2 + a^4}{a4^a} = \frac{2^{2(... ...a} = \frac{(a4^a)(4ab^2) + a^4}{a4^a} = 4ab^2 + \frac{a^3}{4^a}$$

(d)

$4\frac{((2ab)^2 + a^4)}{4a} = \frac{(4a^2b^2 + a^4)}{a} = \frac{a(4ab^2 + a^3)}{a} = a^3 + 4ab^2$

Choices (a1), (b) and (d) evaluate to a³ + 4ab² while (a2) and (c) do not. Hence (a2) and (c) are the two correct answers.

5.

Note, this question has two correct answers. If you got either right on the quiz, you were correct. Otherwise, find and justify both for the homework.

Which of the following does not equal 1?

(a)

$5 \;{\rm mod}\; 2$

(b)

$(98179387171-19873956961) \;{\rm mod}\; 10$

(c)

$(4879165163*91991931877) \;{\rm mod}\; 10$

(d)

$(1987917135+19871938574) \;{\rm mod}\; 2$

(e)

$(1 \;{\rm mod}\; 1999) + 1$

Note: The expressions ought to have been parenthesized for clarity, as shown above. The proper way to think about ``mod'' (from a theory standpoint) is as a mode or environment, rather than as a function. Thus in parts (a) and (d) we are dealing with the ring of integers modulo 2 (which just has two elements), in parts (b) and (c) we are dealing with the ring of integers modulo 10 (10 elements), and in part (e) we are dealing with the ring of integers modulo 1999 (you guessed it--1999 elements). In the solutions below I will use $\equiv_M$ to denote equivalence modulo M.

(a)

$5 = 2 \cdot 2 + 1$, hence $5 \equiv_{2} 1$

(b)

$98179387171 \equiv_{10} 1$, and $19873956961 \equiv_{10} 1$, so $(98179387171-19873956961) \equiv_{10} (1-1) \equiv_{10} 0$

(c)

$4879165163 \equiv_{10} 3$, and $91991931977 \equiv_{10} 7$, so $(4879165163*91991931877) \equiv_{10} (3*7) \equiv_{10} 21 \equiv_{10} 1$

(d)

$1987917135 \equiv_{2} 1$, and $19871938574 \equiv_{2} 0$, so $(1987917135+19871938574) \equiv_{2} (1+0) \equiv_{2} 1$

(e)

$(1+1) \equiv_{1999} 2$

Thus (b) and (e) are the two choices which are not equivalent to 1.

6.

What is the best way to implement a queue?

(a)

A linked list, because the memory usage is proportional to the number of elements in the queue.

(b)

A circular array, because no memory is wasted with next (or previous) pointers.

(c)

A linked list, because it doesn't limit how many elements you can have in the queue.

(d)

A circular array; it's faster because you don't have to deference next or previous pointers.

(e)

It depends.

I don't think this one really needs much of a solution. The answer, of course, is (e). Any one of the other choices may be a perfectly valid reason to choose one implementation over the other depending on the situation. As an example, if you know ahead of time how many elements will be in your queue and you are concerned about speed, then it's probably best to use a circular array. If, however, you don't know ahead of time how many elements you will have, or if your memory is too fragmented to hold a large array, then it's probably best to use a linked list.

7.

Note, this question has no correct answer on the quiz. You should find and justify the correct answer for homework.

The following pseudocode uses the functions C, F, and G.

if (C()) {
  for i = 1 to n
    for j = 1 to n
      F()
} else {
  F()
  G()
}

In terms of the runtime of C, F, and G (T(C), T(F), and T(G), respectively) the asymptotic bound on the runtime of this code must be equivalent to which of the following?

There are a few reasonable answers to this. I will use a conservative upper bound based on the sum of the time to evaluate the conditional, the time to evaluate one branch, and the time to evaluate the other branch. The actual running code cannot do more work than this, so it is a valid upper bound.

I'll set up a pair of sums to find out how long the loop takes in the first branch, and add the times for F and G (since they occur in sequence) for the second branch.

Time for conditional = T(C)

Time for first branch $= \sum_{i=1}^n \sum_{j=1}^n T(F) = n^2 T(F)$

Time for second branch = T(F) + T(G)

All told then, this is O(T(C) + T(F) + T(G) + n² T(F)), but T(F) is o(n² T(F)), so we can drop T(F) (but may not drop n² T(F)). The final time then is O(T(C) + T(G) + n² T(F)).

Note that any of C, F, and G may read input or access global variables; so, their runtime is not necessarily constant.

8.

Given that $T_1(N) \in \theta(f(N))$ and $T_2(N) \in \theta(f(N))$ which of the following is not true?

(a)

$T_1(N) + T_2(N) \in O(f(N))$

(b)

$T_1(N) - T_2(N) \in o(f(N))$

(c)

$T_1(N) / T_2(N) \in O(1)$

(d)

$T_1(N) \in O(T_2(N))$

(e)

$T_1(N) \in \Omega(T_2(N))$

$T(n) \in \theta(f(n))$ if and only if $T(n) \in O(f(n))$ and $T(n) \in \Omega(f(n))$ based on the definition of $\theta$. So, $T_1(N) \in O(f(N))$ and $T_1(N) \in \Omega(f(N))$ and $T_2(N) \in O(f(N))$ and $T_2(N) \in \Omega(f(N))$. There must be some constant c₁ such that $T_1(N) \leq c_1 f(N)$ for sufficiently large N and another (not necessarily equal) constant c₂ such that $T_2(N) \leq c_2 f(N)$ for sufficiently large N. (And the same holds with constants d₁ and d₂ for $\geq$.) Now, on to the options:

(a)

We can just add c₁ and c₂ and prove that the new function must be $\leq (c_1 + c_2) f(N)$ for sufficiently large N.

(b)

This is false, and I'll prove it by counterexample. Let f(N) = n², let T₁(N) = 5n², and let T₂(N) = 2n². Clearly, these satisfy the requirements of the problem. However, $T_1(N) - T_2(N) = 3n^2 \in \theta(n^2)$ and by definition this is not $\in o(n^2)$.

Notice, however, that if the two functions are equal (or even just have the same coefficient for their high order term) their difference is $\in o(f(N))$.

(c)

The largest this fraction can get for sufficiently large N is $\frac{c_1 f(N)}{d_2 f(N)} = c_1 / d_2$ (upper bound of numerator over lower bound of denominator). This is a constant, so the fraction is bounded above by constant multiples of 1. Therefore, by definition, it is $\in O(1)$.

(d)

For sufficiently large N:

$T_2(N) \geq d_2 f(N)$ (since $T_2(N) \in \Omega(f(N))$). So, $\frac{c_1}{d_2} T_2(N) \geq c_1 f(N)$. But, $c_1 f(N) \geq T_1(N)$ (since $T_1(N) \in O(f(N))$). So, $\frac{c_1}{d_2} T_2(N) \geq T_1(N)$, and, by definition, $T_1(N) \in O(T_2(N))$.

(e)

By analogous reasoning to (d), this is true.

9.

Which of the choices below is a correct upper bound on the running time of this code?

sum = 0;
for (i = 0; i < n; i++)
  for (j = 0; j < i; j++)
    sum++;

(a)

O(1)

(b)

$\omega(n^2)$

(c)

o(n²)

(d)

$O(n^2 \log n)$

(e)

none of these

The ``sum++'' line takes constant time, and the loops set up the following formula:

$$\begin{eqnarray*} \sum_{i=0}^n \sum_{j=0}^i \theta(1) &=& \theta(1) \sum_{i=0}^n... ...n + 1) \\ &=& \theta(1) n^2 / 2 + 3 \theta(1) n / 2 + \theta(1) \end{eqnarray*}$$

Dropping lower order terms and coefficients, this is $\theta(n^2)$. Now, on to the answers:

(a)

O(1) is an upper bound, but $\theta(n^2) \not\subset O(1)$ (it's faster than n² on the race sheet).

(b)

$\omega(n^2)$ is not an upper bound.

(c)

o(n²) is an upper bound, but, by definition, a function is only o(f(n)) if it is not $\theta(f(n))$. So this is wrong.

(d)

$O(n^2 \log n)$ is an upper bound which is larger than n². But, that's OK. It just means this is a loose upper bound.

10.

Under which conditions would you want to store a reference to each row and column header in each element of a cross list?

(a)

Time is cheap, memory is precious.

(b)

Memory is precious, but the actual information stored at each element is small.

(c)

Time is precious, memory is cheap, but the actual information stored at each element is large.

(d)

none of the above

Pointers to the column and row headers save time traversing through the row and column lists to find those headers, but they take extra space in each node. However, if the data is large to start with, the pointers add very little extra memory requirement to each node. Therefore, an excellent time to use pointers to the headers is when time is precious (because they speed up the cross list), memory is cheap (because they require storage), but the actual information stored at each element is large (because then the memory hit -- which is cheap anyway -- is also relatively small).

11.

What is a tight upper bound on the running time of this code?

for (i = 1; i * i <= n; i++)
  if (n % i = 0)
cout << i << ' ';
cout << endl;

(a)

$O(\sqrt{n})$

(b)

O(1)

(c)

$\Omega(n)$

(d)

O(n²)

(e)

none of the above

The loop repeats as long as $i*i \leq n$ or equivalently $i^2 \leq n$ or $i \leq \sqrt{n}$. The conditional inside each loop takes constant time whether it executes or not. So, the code takes:

$\sum_{i=1}^{\sqrt{n}} \theta(1) \in \theta(\sqrt{n})$

So, only $O(\sqrt{n})$ is a tight upper bound on the code.

12.

Which choice below is a tight asymptotic bound for a function with the following runtime characteristics?

T(n) = T(n - 1) + n

T(1) = 1

(a)

$\Omega(n)$

(b)

$\theta(n)$

(c)

O(n³)

(d)

$\theta(n^2)$

(e)

none of the above

Note: A number of people answered that since we add n things, and each of them is about n, $T(n)=n\cdot n\in \Theta(n^2)$. This is handwaving, and in the future you will need to be a bit more careful to get full marks on a question. Actually (as we'll show), the sum is $1+2+3+\ldots +n$, and it's not obvious that you can think of this as $n\cdot n$ , particular for a lower bound.

Note 2: A question like this is asking for a proof, so arguing by eliminating the choices that the questions gives is not really sufficient. Also, many people who did this had very vague justifications (e.g. it's ``clearly'' much greater than $\Theta(n)$).

Here's a solution.

$$\begin{eqnarray*} T(n)&=&T(n-1)+n \\ &=&n+T(n-2)+(n-1) \qquad \mbox{by recursive substitution} \\ &=&n+(n-1)+T(n-3)+n-2 \end{eqnarray*}$$

So, after k recursive substitutions of the formula, we get

$$\begin{eqnarray*} T(n)&=&\left(\sum_{i=n+1-k}^{n} i\right)+T(n-k) \end{eqnarray*}$$

And after n-1 recursive substitutions (keeping in mind that T(1)=1),

$$\begin{eqnarray*} T(n)&=&\left(\sum_{i=1}^{n} i\right) \end{eqnarray*}$$

Now, $\sum_{i=1}^n i = \frac{n (n+1)}{2}$ (there's no need to justify this formula, since we just learned it as a fact in class).

Thus, we have

$$\begin{eqnarray*} T(n)&=&\frac{n(n+1)}{2}\\ &=&\frac{1}{2}n^2+\frac{1}{2}n\\ &\in&\Theta(n^2) \end{eqnarray*}$$

So, (d) is the correct answer. You could get away with a bit less of the english text, and introducing k is not necessary as long as you demonstrate the pattern before going to the $\sum$ formula.

13.

Given the following templated class:

template <class T>
class Templ
public:
  T min (T x, T y) { 
    if (x < y) return x; 
    else return y; 
  }
};

What can we say about class T?

(a)

It has a less than test function, 'operator <'.

(b)

It has an equality testing function, 'operator =='.

(c)

It has a less than test function, 'less'.

(d)

All of the above.

(e)

None of the above.

(a) is correct. If we're comparing X with Y using operator <, then the class T must have that operator defined (technically, as one student pointed out, it could have operator < defined as a friend function.).

We never used == or called a 'less' method, so we can't say that it necessarily has those functions defined.

14.

What is the flaw in the following inductive proof?

$\sum_{i=0}^{\infty} x^i = 1/(1-x)$ is true if and only if:

1.

-1 < x < 1

2.

$x \neq 1$

3.

0 < x < 1

4.

x > 1

5.

x = 1 / 2

The correct answer is (a). I will first show that $-1 < x < 1 \Rightarrow \sum_{i=0}^{\infty} x^i = 1/(1-x)$ (the if direction), and then I will show that these are the only xs that work (the only if direction). The book gives a reasonable demonstration that the formula holds for 0 < x < 1, so I will take that as a given. When x = 0 we have:

$$\sum_{i=0}^{\infty} 0^i = 0^0 + 0^1 + 0^2 + 0^3 \cdots$$

By definition, we know that 0a = 0 for any number a, so all terms but the first are zero. The first term is just the empty product (which can also be written $\prod_{\emptyset}$)--a product of zero numbers--which is defined to be the multiplicative identity, 1 (similarly the empty sum, $\sum_{\emptyset}$, is defined to be the additive identity, 0). Thus,

$$\sum_{i=0}^{\infty} 0^i = 1 = \frac{1}{1-0}$$

Now spose -1 < x < 0. Then

$$\sum_{i=0}^{\infty} x^i = \sum_{i=0}^{\infty} (x^{2i} + x^{2i... ...)\sum_{i=0}^{\infty} x^{2i} = \frac{1+x}{1-x^2} = \frac{1}{1-x}$$

It remains to show that the formula is false for values of x not in the interval (-1,1). Spose x > 1. Then all terms in the series are positive and non-decreasing, thus the series cannot converge to the finite (and negative) value 1/(1-x). If x < -1 then the series can be rewritten as $(1+x)\sum_{i=0}^{\infty} x^{2i}$. Each term is positive and non-decreasing, and the quantity (1+x) is finite and non-zero, so again the series cannot converge to the finite value 1/(1-x). Now we have two special cases: $x = \pm 1$. If x = 1 then clearly the series diverges to $\infty$. If we defined $1/0 = \infty$, then the formula would be true in this case, but we don't. As Steve said in class, $\infty$ and ``undefined'' are not the same. If x = -1 then the partial sums of the series alternate between 1 and 0. So the average value is 1/2 = 1/(1-(-1)), but the series doesn't converge so the formula doesn't hold.

Note: this question was removed from the quiz and homework.

Which of the following formulas has the smallest value?

1.

$(\sum_{i=1}^5 i)(\sum_{i=1}^5 i)$

2.

$\sum_{i=0}^{100} (-5)^i$

3.

$\sum_{n=0}^5 (\sum_{i=0}^n 2^i)$

4.

$\sum_{i=0}^{10} 2^3$

Just FYI:

1.

Using the rule that $\sum_{i=1}^n i = \frac{n (n+1)}{2}$, this is:

$\frac{5 (5+1)}{2}^2 = 15^2 = 225$

2.

Let's just get a feel for this one. -5¹⁰⁰ is the largest term in this series. It's equal to 5¹⁰⁰ since (-1)ⁿ = 1 for even n. That's a huge number. It gets a chunk of -(5⁹⁹) taken out of it, but that's still 4 * 5⁹⁹, and the rest of the series just adds more. So this is very big.

3.

Using the rule that $\sum_{i=0}^n 2^i = 2^{n+1} - 1$, this becomes

$\sum_{n=0}^5 (2^{n+1} - 1) = 2 \sum_{n=0}^5 2^n + \sum_{n=0}^5 1$

Using the same rule again, we get:

2 (2⁵⁺¹) + 5 = 128 + 5 = 133

4.

$\sum_{i=0}^{10} 2^3 = 2^3 \sum_{i=0}^{10} 1 = 2^3 * 11 = 88$

So, letter (e) is the smallest.

Which of the following formulas has the greatest value?

1.

$\log_{10} 1024$

2.

$(\log_{13} 343)/(\log_{13} 7)$

3.

$\log_2 (1/128)$

4.

$\log_8 256$

5.

$(\log_a a^2) + (2\log_a \sqrt{a})$

1.

Logarithms are monotonically increasing, hence $\log_{10} 1024 > \log_{10} 1000 = 3$.

2.

Using the rule $\log_A B = \frac{\log_C B}{\log_C A}$, we get:

$\frac{\log_{13} 343}{\log_{13} 7} = \log_7 343 = \log_7 7^3 = 3$.

3.

$\log_2 (1/128) = \log_2 2^{-7} = -7$.

4.

As for (b), $\log_8 256 = \frac{\log_2 256}{\log_2 8} = \frac{\log_2 2^8}{\log_2 2^3} = 8/3$.

5.

$(\log_a a^2) + (2\log_a \sqrt{a}) = 2 + 2(1/2) = 3$.

So, letter (a) is the greatest.

Which of the following is not equal to a³ + 4ab²?

(a1)

$a(a^2 + \frac{6ba}{3ab^0}^2)$

(a2)

$a(a^2 + \frac{6ba}{3(ab)^0}^2)$

(b)

$\frac{a^4b}{ab} + a(2b)^2$

(c)

((2^1+a+b)(2^1+a-b)a²b² + a⁴) / (a4^a)

(d)

$4\frac{((2ab)^2 + a^4)}{4a}$

(e)

none of these

Note: I am including two versions of (a) in the solutions to reflect the original (a1) and updated (a2) versions of the homework. As written on the quiz, (a) was not a correct answer. The five people who answered (a) should pay special attention to this solution because, due to an error on our part, they were not required to redo this problem on their homework.

(a1)

$a(a^2 + \frac{6ba}{3ab^0}^2) = a(a^2 + \frac{6ba}{3a}^2) = a(a^2 + (2b)^2) = a(a^2 + 4b^2) = a^3 + 4ab^2$

(a2)

$a(a^2 + \frac{6ba}{3(ab)^0}^2) = a(a^2 + \frac{6ba}{3}^2) = a(a^2 + (2ab)^2) = a(a^2 + 4a^2b^2) = a^3 + 4a^3b^2$

(b)

$\frac{a^4b}{ab} + a(2b)^2 = a^3 + a(4b^2) = a^3 + 4ab^2$

(c)

I actually intended this to be written $((2^{1+a+b})(2^{1+a-b})(a^2b^2 + \frac{1}{4}a^4)) / (a4^a)$, in which case the answer would have been (e), but instead (c) evaluates to:

$$\frac{(2^{1+a+b})(2^{1+a-b})a^2b^2 + a^4}{a4^a} = \frac{2^{2(... ...a} = \frac{(a4^a)(4ab^2) + a^4}{a4^a} = 4ab^2 + \frac{a^3}{4^a}$$

(d)

$4\frac{((2ab)^2 + a^4)}{4a} = \frac{(4a^2b^2 + a^4)}{a} = \frac{a(4ab^2 + a^3)}{a} = a^3 + 4ab^2$

Choices (a1), (b) and (d) evaluate to a³ + 4ab² while (a2) and (c) do not. Hence (a2) and (c) are the two correct answers.

Note, this question has two correct answers. If you got either right on the quiz, you were correct. Otherwise, find and justify both for the homework.

Which of the following does not equal 1?

1.

$5 \;{\rm mod}\; 2$

2.

$(98179387171-19873956961) \;{\rm mod}\; 10$

3.

$(4879165163*91991931877) \;{\rm mod}\; 10$

4.

$(1987917135+19871938574) \;{\rm mod}\; 2$

5.

$(1 \;{\rm mod}\; 1999) + 1$

Note: The expressions ought to have been parenthesized for clarity, as shown above. The proper way to think about ``mod'' (from a theory standpoint) is as a mode or environment, rather than as a function. Thus in parts (a) and (d) we are dealing with the ring of integers modulo 2 (which just has two elements), in parts (b) and (c) we are dealing with the ring of integers modulo 10 (10 elements), and in part (e) we are dealing with the ring of integers modulo 1999 (you guessed it--1999 elements). In the solutions below I will use $\equiv_M$ to denote equivalence modulo M.

1.

$5 = 2 \cdot 2 + 1$, hence $5 \equiv_{2} 1$

2.

$98179387171 \equiv_{10} 1$, and $19873956961 \equiv_{10} 1$, so $(98179387171-19873956961) \equiv_{10} (1-1) \equiv_{10} 0$

3.

$4879165163 \equiv_{10} 3$, and $91991931977 \equiv_{10} 7$, so $(4879165163*91991931877) \equiv_{10} (3*7) \equiv_{10} 21 \equiv_{10} 1$

4.

$1987917135 \equiv_{2} 1$, and $19871938574 \equiv_{2} 0$, so $(1987917135+19871938574) \equiv_{2} (1+0) \equiv_{2} 1$

5.

$(1+1) \equiv_{1999} 2$

Thus (b) and (e) are the two choices which are not equivalent to 1.

What is the best way to implement a queue?

1.

A linked list, because the memory usage is proportional to the number of elements in the queue.

2.

A circular array, because no memory is wasted with next (or previous) pointers.

3.

A linked list, because it doesn't limit how many elements you can have in the queue.

4.

A circular array; it's faster because you don't have to deference next or previous pointers.

5.

It depends.

I don't think this one really needs much of a solution. The answer, of course, is (e). Any one of the other choices may be a perfectly valid reason to choose one implementation over the other depending on the situation. As an example, if you know ahead of time how many elements will be in your queue and you are concerned about speed, then it's probably best to use a circular array. If, however, you don't know ahead of time how many elements you will have, or if your memory is too fragmented to hold a large array, then it's probably best to use a linked list.

Note, this question has no correct answer on the quiz. You should find and justify the correct answer for homework.

The following pseudocode uses the functions C, F, and G.

if (C()) {
  for i = 1 to n
    for j = 1 to n
      F()
} else {
  F()
  G()
}

In terms of the runtime of C, F, and G (T(C), T(F), and T(G), respectively) the asymptotic bound on the runtime of this code must be equivalent to which of the following?

There are a few reasonable answers to this. I will use a conservative upper bound based on the sum of the time to evaluate the conditional, the time to evaluate one branch, and the time to evaluate the other branch. The actual running code cannot do more work than this, so it is a valid upper bound.

I'll set up a pair of sums to find out how long the loop takes in the first branch, and add the times for F and G (since they occur in sequence) for the second branch.

Time for conditional = T(C)

Time for first branch $= \sum_{i=1}^n \sum_{j=1}^n T(F) = n^2 T(F)$

Time for second branch = T(F) + T(G)

All told then, this is O(T(C) + T(F) + T(G) + n² T(F)), but T(F) is o(n² T(F)), so we can drop T(F) (but may not drop n² T(F)). The final time then is O(T(C) + T(G) + n² T(F)).

Note that any of C, F, and G may read input or access global variables; so, their runtime is not necessarily constant.

Given that $T_1(N) \in \theta(f(N))$ and $T_2(N) \in \theta(f(N))$ which of the following is not true?

1.

$T_1(N) + T_2(N) \in O(f(N))$

2.

$T_1(N) - T_2(N) \in o(f(N))$

3.

$T_1(N) / T_2(N) \in O(1)$

4.

$T_1(N) \in O(T_2(N))$

5.

$T_1(N) \in \Omega(T_2(N))$

$T(n) \in \theta(f(n))$ if and only if $T(n) \in O(f(n))$ and $T(n) \in \Omega(f(n))$ based on the definition of $\theta$. So, $T_1(N) \in O(f(N))$ and $T_1(N) \in \Omega(f(N))$ and $T_2(N) \in O(f(N))$ and $T_2(N) \in \Omega(f(N))$. There must be some constant c₁ such that $T_1(N) \leq c_1 f(N)$ for sufficiently large N and another (not necessarily equal) constant c₂ such that $T_2(N) \leq c_2 f(N)$ for sufficiently large N. (And the same holds with constants d₁ and d₂ for $\geq$.) Now, on to the options:

1.

We can just add c₁ and c₂ and prove that the new function must be $\leq (c_1 + c_2) f(N)$ for sufficiently large N.

2.

This is false, and I'll prove it by counterexample. Let f(N) = n², let T₁(N) = 5n², and let T₂(N) = 2n². Clearly, these satisfy the requirements of the problem. However, $T_1(N) - T_2(N) = 3n^2 \in \theta(n^2)$ and by definition this is not $\in o(n^2)$.

Notice, however, that if the two functions are equal (or even just have the same coefficient for their high order term) their difference is $\in o(f(N))$.

3.

The largest this fraction can get for sufficiently large N is $\frac{c_1 f(N)}{d_2 f(N)} = c_1 / d_2$ (upper bound of numerator over lower bound of denominator). This is a constant, so the fraction is bounded above by constant multiples of 1. Therefore, by definition, it is $\in O(1)$.

4.

For sufficiently large N:

$T_2(N) \geq d_2 f(N)$ (since $T_2(N) \in \Omega(f(N))$). So, $\frac{c_1}{d_2} T_2(N) \geq c_1 f(N)$. But, $c_1 f(N) \geq T_1(N)$ (since $T_1(N) \in O(f(N))$). So, $\frac{c_1}{d_2} T_2(N) \geq T_1(N)$, and, by definition, $T_1(N) \in O(T_2(N))$.

5.

By analogous reasoning to (d), this is true.

Which of the choices below is a correct upper bound on the running time of this code?

sum = 0;
for (i = 0; i < n; i++)
  for (j = 0; j < i; j++)
    sum++;

1.

O(1)

2.

$\omega(n^2)$

3.

o(n²)

4.

$O(n^2 \log n)$

5.

none of these

The ``sum++'' line takes constant time, and the loops set up the following formula:

$$\begin{eqnarray*} \sum_{i=0}^n \sum_{j=0}^i \theta(1) &=& \theta(1) \sum_{i=0}^n... ...n + 1) \\ &=& \theta(1) n^2 / 2 + 3 \theta(1) n / 2 + \theta(1) \end{eqnarray*}$$

Dropping lower order terms and coefficients, this is $\theta(n^2)$. Now, on to the answers:

1.

O(1) is an upper bound, but $\theta(n^2) \not\subset O(1)$ (it's faster than n² on the race sheet).

2.

$\omega(n^2)$ is not an upper bound.

3.

o(n²) is an upper bound, but, by definition, a function is only o(f(n)) if it is not $\theta(f(n))$. So this is wrong.

4.

$O(n^2 \log n)$ is an upper bound which is larger than n². But, that's OK. It just means this is a loose upper bound.

Under which conditions would you want to store a reference to each row and column header in each element of a cross list?

1.

Time is cheap, memory is precious.

2.

Memory is precious, but the actual information stored at each element is small.

3.

Time is precious, memory is cheap, but the actual information stored at each element is large.

4.

none of the above

Pointers to the column and row headers save time traversing through the row and column lists to find those headers, but they take extra space in each node. However, if the data is large to start with, the pointers add very little extra memory requirement to each node. Therefore, an excellent time to use pointers to the headers is when time is precious (because they speed up the cross list), memory is cheap (because they require storage), but the actual information stored at each element is large (because then the memory hit -- which is cheap anyway -- is also relatively small).

What is a tight upper bound on the running time of this code?

for (i = 1; i * i <= n; i++)
  if (n % i = 0)
cout << i << ' ';
cout << endl;

1.

$O(\sqrt{n})$

2.

O(1)

3.

$\Omega(n)$

4.

O(n²)

5.

none of the above

The loop repeats as long as $i*i \leq n$ or equivalently $i^2 \leq n$ or $i \leq \sqrt{n}$. The conditional inside each loop takes constant time whether it executes or not. So, the code takes:

$\sum_{i=1}^{\sqrt{n}} \theta(1) \in \theta(\sqrt{n})$

So, only $O(\sqrt{n})$ is a tight upper bound on the code.

Which choice below is a tight asymptotic bound for a function with the following runtime characteristics?

T(n) = T(n - 1) + n

T(1) = 1

1.

$\Omega(n)$

2.

$\theta(n)$

3.

O(n³)

4.

$\theta(n^2)$

5.

none of the above

Note: A number of people answered that since we add n things, and each of them is about n, $T(n)=n\cdot n\in \Theta(n^2)$. This is handwaving, and in the future you will need to be a bit more careful to get full marks on a question. Actually (as we'll show), the sum is $1+2+3+\ldots +n$, and it's not obvious that you can think of this as $n\cdot n$ , particular for a lower bound.

Note 2: A question like this is asking for a proof, so arguing by eliminating the choices that the questions gives is not really sufficient. Also, many people who did this had very vague justifications (e.g. it's ``clearly'' much greater than $\Theta(n)$).

Here's a solution.

$$\begin{eqnarray*} T(n)&=&T(n-1)+n \\ &=&n+T(n-2)+(n-1) \qquad \mbox{by recursive substitution} \\ &=&n+(n-1)+T(n-3)+n-2 \end{eqnarray*}$$

So, after k recursive substitutions of the formula, we get

$$\begin{eqnarray*} T(n)&=&\left(\sum_{i=n+1-k}^{n} i\right)+T(n-k) \end{eqnarray*}$$

And after n-1 recursive substitutions (keeping in mind that T(1)=1),

$$\begin{eqnarray*} T(n)&=&\left(\sum_{i=1}^{n} i\right) \end{eqnarray*}$$

Now, $\sum_{i=1}^n i = \frac{n (n+1)}{2}$ (there's no need to justify this formula, since we just learned it as a fact in class).

Thus, we have

$$\begin{eqnarray*} T(n)&=&\frac{n(n+1)}{2}\\ &=&\frac{1}{2}n^2+\frac{1}{2}n\\ &\in&\Theta(n^2) \end{eqnarray*}$$

So, (d) is the correct answer. You could get away with a bit less of the english text, and introducing k is not necessary as long as you demonstrate the pattern before going to the $\sum$ formula.

Given the following templated class:

template <class T>
class Templ
public:
  T min (T x, T y) { 
    if (x < y) return x; 
    else return y; 
  }
};

What can we say about class T?

1.

It has a less than test function, 'operator <'.

2.

It has an equality testing function, 'operator =='.

3.

It has a less than test function, 'less'.

4.

All of the above.

5.

None of the above.

(a) is correct. If we're comparing X with Y using operator <, then the class T must have that operator defined (technically, as one student pointed out, it could have operator < defined as a friend function.).

We never used == or called a 'less' method, so we can't say that it necessarily has those functions defined.

What is the flaw in the following inductive proof?