COMP 3804 – Background Quiz

Question 1

$$log_2{128} = log_2{2^7} = 7$$

Question 2

$log_2 n$ is the exponent to which the base 2 must be raised to produce the number n. In other words, it answers the question: "2 raised to what power equals n?"

Question 3

$2^n$. Use bit-strings to solve this problem (1 = element included in the set, 0 = not).

Question 4

$O(n \log n)$.

This is the lower bound for comparison-based sorting algorithms, meaning that no comparison-based sorting algorithm can have a better average-case or worst-case time complexity than $O(n \log n)$.

Question 5

$O(\log n)$. Binary search if elements are sorted.

Question 6

$O(n)$. Create a balanced BST by recursively choosing the middle element as the root.

Question 7

$$\boxed{\sum_{k=1}^{n}{k}=\frac{n(n+1)}{2}}$$

Using geometry

The total number of squares in the region highlighted in black is what we're interested in counting. That is, $length \times height \times \frac{1}{2}$.

Using some 10-year-old's sorcery

Carl Friedrich Gauss

Question 8

Solve the following recurrence: $T (1) = 1$ and for each $n \geq 2$ that is a power of two.

$$\boxed{T (n) = 2 \cdot T (n/2) + n}$$

---

$$\begin{align*} T(n) &= 2 \cdot \underbrace{\left( 2 \cdot T\left(\frac{n/2}{2}\right) + n/2 \right)}_{T(n/2)} + n \\ &= 4 \cdot T\left(\frac{n/2}{2}\right) + n + n \\ &= 4 \cdot T\left( n/4 \right) + 2n \\ \\ T(n) &= 4 \cdot \underbrace{\left( 2 \cdot T\left( \frac{n/4}{2} \right) + n/4 \right)}_{T(n/4)} + 2n \\ &= 8 \cdot T(n/8) + 3n \\ \\ T(n) &= 8 \cdot \underbrace{ (2 \cdot T \left( \frac{n/8}{2} \right) + n/8) }_{T(n/8)} + 3n \\ &= 16 \cdot T(n/16) + 4n \\ &\qquad \qquad \qquad \vdots \\ T(n) &= 2^k \cdot T(n/2^k) + kn \\ \end{align*}$$

Where $k$ is the number of times we have expanded the recurrence.

Remember, our goal is to express $T(n)$ only in terms of $n$ (eliminating the recursive definition). Because the base case is $T(1)$, we can stop expanding when $n/2^k = 1$, or when $n = 2^k$. This means that $k = \log_2(n)$.

$$\begin{align} T(n) &= 2^k \cdot T(n/2^k) + kn \\ T(n) &= 2^{\log_2(n)} \cdot T(1) + n \cdot \log_2(n) \\ T(n) &= n \cdot 1 + n \cdot \log_2(n) \\ \end{align}$$

We can say that $T(n)$ is in $O(n \log n)$.

Question 9

Solve the following recurrence: $T (1) = 1$ and for each $n \geq 2$ that is a power of two.

$$\boxed{ T (n) = T (n/2) + 1 }$$

---

$$\begin{align*} T(n) &= T(n/2) + 1 \\ &= \underbrace{(T((n/2)/2) + 1)}_{T(n/2)} + 1 \\ &= T(n/4) + 2 \\ \\ T(n) &= \underbrace{ T((n/4)/2 + 1) }_{T(n/4)} + 2 \\ &= T(n/8) + 3 \\ &\qquad\qquad \vdots \\ T(n) &= T(n/2^k) + k \\ \end{align*}$$

Again, we stop expanding when $n/2^k = 1$, or when $n = 2^k$. This means that $k = \log_2(n)$.

$$\begin{align} T(n) &= T(n/2^k) + k \\ &= T(n/2^{\log_2(n)}) + \log_2(n) \\ &= 1 + \log_2(n) \\ \end{align}$$

Concluding that $T(n)$ is in $O(\log n)$.

Question 10

Let $G$ be a graph with $n$ vertices a$n$d $n$ edges. Ca$n$ $G$ be a tree?

A tree is a connected graph with no cycles. A tree with $n$ vertices has exactly $n-1$ edges. Therefore, a graph with $n$ vertices and $n$ edges cannot be a tree, as it has one more edge than a tree would have.

Question 11

Let $G$ be a graph with $n$ vertices. What is the maximum $n$umber of edges that $G$ ca$n$ have?

In a simple graph with $n$ vertices, each pair of distinct vertices can be connected by at most one edge. This means the maximum number of edges occurs when every vertex is connected to every other vertex.

The total number of ways to choose 2 vertices from $n$ vertices (i.e., the number of pairs of vertices) is given by the binomial coefficient (combinatorics):

$${}^{n}C_{2} = \binom{n}{2} = \frac{n(n-1)}{2}$$

Thus, the maximum number of edges in a simple graph with $n$ vertices is $\frac{n(n-1)}{2}$.

---

Alternatively, we can use the summation formula:

$$\begin{align} 3 + 2 + 1 &= \sum_{i=1}^{n - 1}{i} \\ &= \frac{(n - 1)((n-1) + 1)}{2} \\ &= \frac{n(n - 1)}{2} \end{align}$$

Question 12

You are given two sorted lists, each containing $n$ numbers. What is the best time complexity to merge these two lists into one sorted list?

Since both lists are already sorted, we can use a two-pointer technique to merge them efficiently. We maintain two pointers, one for each list, and compare the elements at these pointers. We append the smaller element to the merged list and move the corresponding pointer forward. This process continues until we have processed all elements from both lists.

The time complexity of this merging process is $O(n)$, where $n$ is the total number of elements in both lists (i.e., $2n$ elements). Therefore, the best time complexity to merge the two sorted lists into one sorted list is $O(n)$.

Question 13

What is a random variable? (Hint: A random variable is neither random nor a variable.)

A random variable is a mathematical function that maps outcomes of a random process to numerical values.

Suppose $X$ is the random variable representing the number of heads in 10 coin flips. If the outcome is H, T, H, H, T, T, H, T, H, T (where H = heads, T = tails), then $X$ maps this outcome to the value 5, since there are 5 heads.

$$X(\text{H, T, H, H, T, T, H, T, H, T}) = 5$$

In general, we can write:

$$X: \Omega \to \mathbb{R}$$

where $\Omega$ is the set of all possible outcomes (the sample space), and $\mathbb{R}$ is the set of real numbers. For example,

$$X(\omega) = \text{number of heads in } \omega$$

or using arrow notation:

$$\omega \mapsto X(\omega)$$

Question 14

You roll a fair die repeatedly until the result is 3. Let $X$ be the number of rolls. What is the expected value of $X$?

To find the expected value of $X$, we can use the concept of geometric distribution. The random variable $X$ follows a geometric distribution with success probability $p = \frac{1}{6}$ (the probability of rolling a 3 on a fair six-sided die).

The expected value (mean) of a geometric random variable is given by:

$$E(X) = \frac{1}{p}$$

Substituting the value of $p$: $E(X) = \frac{1}{\frac{1}{6}} = 6$ Therefore, the expected number of rolls until we get a 3 is 6.