Evaluation: 2018 Fall Final
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 3^{69}$
(b)
$70 \cdot 3^{70}$
(c)
$70 \cdot 2^{69}$
(d)
$70 \cdot 2^{70}$
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 3^{28}$
(c)
${70 \choose 12} \cdot {58 \choose 30}$
(d)
${70 \choose 12} \cdot {58 \choose 30} \cdot 2^{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} \cdot 2^{58} + {70 \choose 30} \cdot 2^{40}$
(c)
${70 \choose 12} + {70 \choose 30} - {58 \choose 30}$
(d)
${70 \choose 12} \cdot 2^{58} + {70 \choose 30} \cdot 2^{40} - {70 \choose 12} \cdot {58 \choose 30}$
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)
$\sum_{k=4}^{70} {70 \choose k} \cdot 2^{70-k}$
(c)
$\sum_{k=4}^{70} {70 \choose k} \cdot 2^{k}$
(d)
$3^{70} - 2^{70} - 70 \cdot 2^{69}$
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 subsets of $S$ that contain at least two elements.
(b)
The number of bitstrings of length $n$ that contain at least one 0.
(c)
The number of bitstrings of length $n$ that contain at least three 0's.
(d)
The number of subsets of $S$ that are non-empty.
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 35} \cdot 5^{20} \cdot 3^{35}$
(c)
${55 \choose 20} \cdot 5^{35} \cdot 3^{20}$
(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)
90
(b)
60
(c)
30
(d)
120
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} + S_{n-4}$
(b)
$S_n = S_{n-2} + S_{n-4}$
(c)
$S_n = 2 \cdot S_{n-2} + 4 \cdot 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} + S_{n-3}$
(b)
$S_n = S_{n-1} + S_{n-2} + 2^{n-3}$
(c)
$S_n = S_{n-1} + S_{n-2} + 1$
(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} - 1$
(b)
None of the above.
(c)
$T(n) = \frac{3}{2} \cdot 3^{n} - \frac{1}{2}$
(d)
$T(n) = \frac{5}{2} \cdot 3^{n} - \frac{1}{2}$
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)
1/3
(b)
1/4
(c)
1/2
(d)
2/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?
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)
$4 \cdot \left. {52 \choose 5} \middle/ {13 \choose 5} \right.$
(d)
$\left. {13 \choose 5} \middle/ {52 \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$".
(a)
2/11
(b)
1/7
(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?
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)
None of the above.
(c)
${n \choose k} \cdot \left. 4^{n - k} \middle/ 3^n \right.$
(d)
${n \choose k} \cdot \left. 4^{n - k} \middle/ 3^k \right.$
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$".
(a)
None of the above.
(b)
All of the above.
(c)
The events $A$ and $B$ are not independent.
(d)
The events $A$ and $B$ are independent.
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".
(a)
The events $A$ and $B$ are not independent.
(b)
None of the above.
(c)
All of the above.
(d)
The events $A$ and $B$ are independent.
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)
2/3
(b)
5/6
(c)
1/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)$.
(a)
9/8
(b)
8/9
(c)
9/13
(d)
13/9
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.
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 \middle/ 5 \right.$
(c)
$\left. (n - 1) \middle/ 25 \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.
(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}} + n + 1}{{{n+2}\choose{3}}}$
(d)
$\frac{2 {{n}\choose{2}} + 2n}{{{n+2}\choose{3}}}$
21 .
You are given two independent random variables $X$ and $Y$, where
Define the random variable
$$
Z = (X + Y)\ \mathrm{mod}\ 2.
$$
Which of the following is correct?
| $\Pr(X = 0)$ | $= \Pr(X = 1) = \Pr(Y = 0)$ $= \Pr(Y = 1) = 1/2.$ |
(a)
None of the above.
(b)
The random variables $X$ and $Z$ are independent.
(c)
The random variables $X$ and $Z$ are not independent.
(d)
All of the above.
22 .
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:
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?
$\newcommand{\TriIsHungry}{{\rm T {\scriptsize RI} I {\scriptsize S} H {\scriptsize UNGRY}}}$
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{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;}$
$\qquad\, \mathbf{endif}$
$\mathbf{endif}$
Define the random variable $X$ to be the number of dishes that Tri eats when running algorithm $\TriIsHungry$. | $//$ | $\text{the results of all}$ $\text{orders are independent}$ |
$\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}$ |
$\mathbf{endif}$
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?
(a)
7/5
(b)
5/7
(c)
5/12
(d)
12/5
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
Hint: Use the Linearity of Expectation.
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.
Hint: Use the Linearity of Expectation.
(a)
$z = 1/4$
(b)
$z = 3/4$
(c)
$z = 1/2$
(d)
$z = 1/3$
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$:
Hint: Use indicator random variables.
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.
Hint: Use indicator random variables.
(a)
$\left. (n + 1) \middle/ n \right.$
(b)
$\left. (n - 1) \middle/ n \right.$
(c)
2
(d)
1