Evaluations

Evaluation: 2018 Fall Final

Author: Michiel Smid

1 . Consider strings of length 70, in which each character is one of the letters $a,b,c$. How many such strings have exactly 1 letter $c$?
(a)
$70 \cdot 2^{70}$
(b)
$70 \cdot 2^{69}$
(c)
$70 \cdot 3^{70}$
(d)
$70 \cdot 3^{69}$

2 . Consider strings of length 70, in which each character is one of the letters $a, b, c$. How many such strings have exactly 12 letters $c$ and exactly 30 letters $b$?
(a)
${70 \choose 12} + {58 \choose 30}$
(b)
${70 \choose 12} \cdot {58 \choose 30} \cdot 2^{28}$
(c)
${70 \choose 12} \cdot {58 \choose 30}$
(d)
${70 \choose 12} \cdot {58 \choose 30} \cdot 3^{28}$

3 . Consider strings of length 70, in which each character is one of the letters $a, b, c$. How many such strings have exactly 12 letters $c$ or exactly 30 letters $b$?
(a)
None of the above.
(b)
${70 \choose 12} + {70 \choose 30} - {58 \choose 30}$
(c)
${70 \choose 12} \cdot 2^{58} + {70 \choose 30} \cdot 2^{40} - {70 \choose 12} \cdot {58 \choose 30}$
(d)
${70 \choose 12} \cdot 2^{58} + {70 \choose 30} \cdot 2^{40}$

4 . Consider strings of length 70, in which each character is one of the letters $a, b, c$. How many such strings have at least 3 letters $c$?
(a)
$3^{70} - 2^{70} - 70 \cdot 2^{69} - {70 \choose 2} \cdot 2^{68}$
(b)
$3^{70} - 2^{70} - 70 \cdot 2^{69}$
(c)
$\sum_{k=4}^{70} {70 \choose k} \cdot 2^{k}$
(d)
$\sum_{k=4}^{70} {70 \choose k} \cdot 2^{70-k}$

5 . Let $n \geq 2$ be an integer and consider the set $S = \{1,2,\dots,n\}$. What does $$ \sum_{k=2}^{n} {n \choose k} $$ count?
(a)
The number of bitstrings of length $n$ that contain at least three 0's.
(b)
The number of subsets of $S$ that are non-empty.
(c)
The number of bitstrings of length $n$ that contain at least one 0.
(d)
The number of subsets of $S$ that contain at least two elements.

6 . What is the coefficient of $x^{20}y^{35}$ in the expansion of $(5x - 3y)^{55}$?
(a)
$- {55 \choose 35} \cdot 5^{20} \cdot 3^{35}$
(b)
${55 \choose 20} \cdot 5^{35} \cdot 3^{20}$
(c)
${55 \choose 35} \cdot 5^{20} \cdot 3^{35}$
(d)
$- {55 \choose 20} \cdot 5^{35} \cdot 3^{20}$

7 . A string that is obtained by rearranging the letters of the word

SUCCESS

is called awesome, if the string contains the substring UE or EU. Thus, both SCUESCS and SCSEUCS are awesome, whereas SUCCESS is not awesome. What is the number of awesome strings?
(a)
30
(b)
120
(c)
90
(d)
60

8 . Let $n \geq 1$ be an integer and let $S_n$ be the number of ways in which $n$ can be written as a sum of 2's and 4's; the order in which the 2's and 4's occur in the sum matters. For example, $S_6 = 3$, because $$ 6 = 2 + 2 + 2 = 2 + 4 = 4 + 2. $$ Which of the following is true for any integer $n \geq 6$?
(a)
$S_n = 2 \cdot S_{n-2} + 4 \cdot S_{n-4}$
(b)
$S_n = 2 \cdot S_{n-2} + S_{n-4}$
(c)
$S_n = S_{n-2} + S_{n-4}$
(d)
$S_n = S_{n-2} + 4 \cdot S_{n-4}$

9 . Consider bitstrings that do not contain 110. Let $S_n$ be the number of such strings having length $n$. Which of the following is true for any $n \geq 4$?
(a)
$S_n = S_{n-1} + S_{n-2} + 1$
(b)
$S_n = S_{n-1} + S_{n-2} + 2^{n-3}$
(c)
$S_n = S_{n-1} + S_{n-2} + S_{n-3}$
(d)
$S_n = S_{n-1} + S_{n-2} + 2^{n-2}$

10 . The function $T : \mathbb{N} \rightarrow \mathbb{N}$ is recursively defined as follows: $$ \begin{align} T(0) &= 2, \\ T(n) &= 3 \cdot T(n - 1) + 1,\ \ \mathrm{if}\ n \geq 1. \end{align} $$ Which of the following is true for all integers $n \geq 0$?
(a)
$T(n) = \frac{5}{2} \cdot 3^{n} - \frac{1}{2}$
(b)
$T(n) = \frac{3}{2} \cdot 3^{n} - \frac{1}{2}$
(c)
None of the above.
(d)
$T(n) = \frac{5}{2} \cdot 3^{n} - 1$

11 . You flip a fair coin 5 times; the flips are independent of each other. What is the probability that in these 5 coin flips, the coin comes up heads an odd number of times?
(a)
2/3
(b)
1/2
(c)
1/4
(d)
1/3

12 . In a standard deck of 52 cards, each card has a suit and a rank. There are four suits (spades ♠, hearts ♡, clubs ♣, and diamonds ♢), and 13 ranks (Ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, and King).
Assume you get a uniformly random hand consisting of 5 cards. What is the probability that the 5 cards in this hand are all of the same suit?
(a)
$\left. {52 \choose 5} \middle/ {13 \choose 5} \right.$
(b)
$4 \cdot \left. {13 \choose 5} \middle/ {52 \choose 5} \right.$
(c)
$\left. {13 \choose 5} \middle/ {52 \choose 5} \right.$
(d)
$4 \cdot \left. {52 \choose 5} \middle/ {13 \choose 5} \right.$

13 . You are given a fair die that has six faces. One face has the letter $a$ on it, two faces have the letter $b$ on them, and three faces have the letter $c$ on them. Assume you roll this die twice, independently of each other. Define the events
  • A = "both rolls result in the same letter",
  • B = "at least one of the rolls results in the letter $a$".
What is $\Pr(A|B)$?
(a)
1/7
(b)
2/11
(c)
1/11
(d)
2/7

14 . Let $n$ and $k$ be integers with $1 \leq k \leq n$.
You are given two bitstrings $a_1,a_2,\dots,a_n$ and $b_1,b_2,\dots,b_n$ of length $n$. In both bitstrings, each bit is 0 with probability 1/2, and 1 with probability 1/2 (independent of all other bits).
Consider the bitstring $$ a_1 \cdot b_1,a_2 \cdot b_2,\dots,a_n \cdot b_n $$ where $a_i \cdot b_i$ is the result of multiplying the two bits $a_i$ and $b_i$. What is the probability that this bitstring contains exactly $k$ many 1's?
(a)
${n \choose k} \cdot \left. 3^{n - k} \middle/ 4^n \right.$
(b)
${n \choose k} \cdot \left. 4^{n - k} \middle/ 3^k \right.$
(c)
${n \choose k} \cdot \left. 4^{n - k} \middle/ 3^n \right.$
(d)
None of the above.

15 . Consider a uniformly random permutation $a_1,a_2,a_3,a_4$ of the set $\{1,2,3,4\}$. Define the events
  • A = "$a_1 > a_2$",
  • B = "$a_4 > a_3$".
Which of the following is correct?
(a)
None of the above.
(b)
The events $A$ and $B$ are not independent.
(c)
The events $A$ and $B$ are independent.
(d)
All of the above.

16 . You flip a fair coin three times; these three flips are independent. Define the events
  • A = "the number of heads in these three flips is even",
  • B = "the number of tails in these three flips is at most one".
(Remember that 0 is even.) Which of the following is correct?
(a)
None of the above.
(b)
The events $A$ and $B$ are not independent.
(c)
The events $A$ and $B$ are independent.
(d)
All of the above.

17 . Let $A$ and $B$ be two independent events in some sample space $S$. You are given that $\Pr(A) = 1/4$ and $\Pr(B) = 2/3$. What is $\Pr(A \cup B)$?
(a)
1/3
(b)
5/6
(c)
2/3
(d)
3/4

18 . A red box contains the numbers 0, 1, and 2, and a blue box also contains the numbers 0, 1, and 2. You choose a uniformly random element from the red box and a uniformly random element from the blue box; these two choices are independent of each other. Define the random variables
  • X = the number you choose from the red box,
  • Y = the number you choose from the blue box,
  • Z = $\max(X, Y)$.
What is the expected value $\mathbb{E}(Z)$ of the random variable $Z$?
(a)
8/9
(b)
13/9
(c)
9/13
(d)
9/8

19 . Let $n \geq 2$ be an integer. Consider a string $c_1,c_2,\dots,c_n$ of length $n$, in which each character $c_i$ is a uniformly random element of the set $\{\alpha, \beta, \gamma, \delta, \epsilon\}$ (independently of all other characters).
Define the random variable $X$ to be the number of indices $i$ with $1 \leq i < n$ for which $c_i = c_{i+1}$.
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?
Hint: Use indicator random variables.
(a)
$\left. (n - 1) \middle/ 5 \right.$
(b)
$\left. (n - 1) \middle/ 25 \right.$
(c)
$\left. n \middle/ 5 \right.$
(d)
$\left. n \middle/ 25 \right.$

20 . Let $n \geq 2$ be an integer. You are given $n$ beer bottles $B_1,B_2,\dots,B_n$ and two cider bottles $C_1$ and $C_2$. You choose a uniformly random 3-element subset of the set of these $n+2$ bottles. Define the random variable $X$ to be
  • X = the number of cider bottles in the chosen subset.
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?
(a)
$\frac{2 {{n}\choose{2}} + n}{{{n+2}\choose{3}}}$
(b)
$\frac{2 {{n}\choose{2}} + n + 1}{{{n+2}\choose{3}}}$
(c)
$\frac{2 {{n}\choose{2}} + 2n}{{{n+2}\choose{3}}}$
(d)
$\frac{2 {{n}\choose{2}} + n - 1}{{{n+2}\choose{3}}}$

21 . You are given two independent random variables $X$ and $Y$, where
$\Pr(X = 0)$ $= \Pr(X = 1) = \Pr(Y = 0)$ $= \Pr(Y = 1) = 1/2.$
Define the random variable $$ Z = (X + Y)\ \mathrm{mod}\ 2. $$ Which of the following is correct?
(a)
The random variables $X$ and $Z$ are not independent.
(b)
All of the above.
(c)
None of the above.
(d)
The random variables $X$ and $Z$ are independent.

22 . Zoltan's Noodle House is a popular restaurant in downtown Ottawa. When you order the surprise dish, you get Mi Quang with probability 1/4, Bun Cha Ca with probability 1/3, and Banh Xeo with probability 5/12.
Tri enjoys going to this restaurant, because the food reminds him of his mommy's food back home in Da Nang.
Tri runs the following recursive algorithm:
$\mathbf{Algorithm}\ \TriIsHungry\mathrm{:}$
$//$ $\text{the results of all}$ $\text{orders are independent}$
$\text{Tri orders the surprise dish;}$
$\mathbf{if}\ \mathrm{Tri}\ \mathrm{gets}\ \mathit{Mi}\ \mathit{Quang}$
$\mathbf{then}\ \text{Tri eats the dish;}$
$\qquad\ \ \TriIsHungry$
$\mathbf{else}\ \mathbf{if}\ \mathrm{Tri}\ \mathrm{gets}\ \mathit{Bun}\ \mathit{Cha}\ \mathit{Ca}$
$\qquad\, \mathbf{then}\ \text{Tri eats the dish;}$
$\qquad \qquad\ \ \, \TriIsHungry$
$\qquad\, \mathbf{else}\ \text{Tri eats the dish;}$
$\hspace{4.05em}$ $\text{Tri pays the bill}$ $\text{and goes home}$
$\qquad\, \mathbf{endif}$
$\mathbf{endif}$
Define the random variable $X$ to be the number of dishes that Tri eats when running algorithm $\TriIsHungry$.
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?
(a)
12/5
(b)
5/7
(c)
7/5
(d)
5/12

23 . The final exam for COMP 2804 has 25 multiple-choice questions. For each question, there are 4 possible answers, exactly one of which is correct. Michiel chooses a positive real number $z$ and uses the following marking scheme: For each correct answer, a student receives 1 mark, whereas for each incorrect answer, the student receives $-z$ marks.
Jim is one of the students and answers the 25 questions, by choosing a uniformly random answer for each question; the choices are independent of each other.
Define the random variable
  • X = the number of marks that Jim recevies.
For what value of $z$ is the expected value $\mathbb{E}(X)$ equal to 0?
Hint: Use the Linearity of Expectation.
(a)
$z = 1/2$
(b)
$z = 1/3$
(c)
$z = 1/4$
(d)
$z = 3/4$

24 . Let $n \geq 2$ be an integer. There are $n$ students $S_1,S_2,\dots,S_n$ writing this exam. Each student has brought one backpack with them. Before the exam starts, all students have to leave their backpacks at the front of the examination room.
At the end of the exam, the proctor places the backpacks in a uniformly random order $b_1,b_2,\dots,b_n$, and, for each $i = 1, 2, ..., n$, gives backpack $b_i$ to student $S_i$.
Define the following random variable $X$:
  • X = the number of students who get their own backpack.
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?
Hint: Use indicator random variables.
(a)
$\left. (n + 1) \middle/ n \right.$
(b)
1
(c)
2
(d)
$\left. (n - 1) \middle/ n \right.$

25 . Who discovered the Vandermonde Identity?
(a)
Professor Identity
(b)
Justin Bieber
(c)
Alexandre-Théophile Vandermonde
(d)
Donald Trump