Evaluation comp2804/2019-fall-final

1 . Consider strings of length 85, in which each character is one of the letters $a,b,c,d$.
How many such strings have exactly 5 letters $c$?

(a)

${85 \choose 5} \cdot 3^{80}$

(b)

${85 \choose 5} \cdot 4^{85}$

(c)

${85 \choose 5} \cdot 3^{85}$

(d)

${85 \choose 5} \cdot 4^{80}$

2 . Consider strings of length 85, in which each character is one of the letters $a,b,c,d$.
How many such strings have exactly 15 letters $a$ and exactly 30 letters $d$?

(a)

${85 \choose 15} \cdot {70 \choose 30} \cdot 3^{40}$

(b)

${85 \choose 15} \cdot {70 \choose 30} \cdot 2^{40}$

(c)

${85 \choose 15} \cdot {70 \choose 30} \cdot 4^{40}$

(d)

None of the above.

3 . Consider strings of length 85, in which each character is one of the letters $a,b,c,d$.
How many such strings have exactly 15 letters $a$ or exactly 30 letters $d$?

(a)

None of the above.

(b)

${85 \choose 15} \cdot 3^{70} + {85 \choose 30} \cdot 3^{55}$

(c)

${85 \choose 15} \cdot 4^{70} + {85 \choose 30} \cdot 4^{55}$

(d)

${85 \choose 15} \cdot 3^{70} + {85 \choose 30} \cdot 3^{55} - {85 \choose 15} \cdot {70 \choose 30} \cdot 2^{40}$

4 . You are given 20 beer bottles $B_1,B_2,...,B_{20}$ and 50 cider bottles $C_1,C_2,...,C_{50}$.
Consider subsets of these 70 bottles, that contain exactly 12 beer bottles (and any number of cider bottles) or exactly 12 cider bottles (and any number of beer bottles). How many such subsets are there?

(a)

${20 \choose 12} + {50 \choose 12} - {20 \choose 12} \cdot {50 \choose 12}$

(b)

${20 \choose 12} + {50 \choose 12}$

(c)

${20 \choose 12} \cdot 2^{50} + {50 \choose 12} \cdot 2^{20} - {20 \choose 12} \cdot {50 \choose 12}$

(d)

${20 \choose 12} \cdot 2^{50} + {50 \choose 12} \cdot 2^{20}$

5 . You are given 20 beer bottles $B_1,B_2,...,B_{20}$ and 50 cider bottles $C_1,C_2,...,C_{50}$.
Consider subsets of these 70 bottles, that contain at least 3 beer bottles (and any number of cider bottles). How many such subsets are there?

(a)

$2^{70} - 2^{50} - 20 \cdot 2^{50} - {20 \choose 2} \cdot 2^{50}$

(b)

$2^{70} - 2^{50} - 20 \cdot 2^{50}$

(c)

$2^{70} - 2^{50} - 20 - {20 \choose 2}$

(d)

None of the above.

6 . Let $m \geq 2$ and $n \geq 2$ be integers. What does $$ {m \choose 2} + {n \choose 2} + m \cdot n $$ count?

(a)

The number of ways to choose a 2-element subset from a set consisting of $m + n$ elements.

(b)

None of the above.

(c)

The number of ways to choose a subset from a set consisting of $m + n$ elements.

(d)

The number of ways to choose an ordered pair of 2 elements from a set consisting of $m + n$ elements.

7 . Nick eats lots of bananas. During a period of 7 days, Nick eats a total of 25 bananas. A banana schedule is a sequence of 7 numbers, whose sum is equal to 25, and whose numbers indicate the number of bananas that Nick eats on each day. Three examples of such schedules are (3,2,7,4,1,3,5), (2,3,7,4,1,3,5), and (3,0,9,4,1,0,8). How many banana schedules are there?

(a)

${31 \choose 7}$

(b)

${32 \choose 7}$

(c)

${32 \choose 6}$

(d)

${31 \choose 6}$

8 . A string that is obtained by rearranging the letters of the word BOOGER is called awesome, if the string does not contain the substring OO. Thus, GEOROB is awesome, whereas GREOOB is not awesome. What is the number of awesome strings?

(a)

$6 \cdot {5 \choose 2} \cdot 3 \cdot 2$

(b)

$(6 \cdot {5 \choose 2} \cdot 3 \cdot 2) - 5!$

(c)

$6! - 5!$

(d)

$(6 \cdot {5 \choose 2} \cdot 3) - 5!$

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} + 2^{n - 2}$

(b)

$S_n = S_{n - 1} + S_{n - 2} + 1$

(c)

$S_n = S_{n - 1} + S_{n - 2} + 2^{n - 3}$

(d)

$S_n = S_{n - 1} + S_{n - 2} + S_{n - 3}$

10 . Consider the recursive algorithm $\IFeelLikeSinging$, which takes as input an integer $n \geq 0$:

$\IFeelLikeSinging(n):$
$\quad \mathbf{if}\ n = 0\ \mathrm{or}\ n = 1\ \mathbf{then}$
$\quad \quad \text{sing O Canada}$
$\quad \mathbf{else}\ \mathbf{if}\ n\ \text{is odd}\ \mathbf{then}$
$\quad \quad \IFeelLikeSinging(n + 1)$
$\quad \mathbf{else}$
$\quad \quad \IFeelLikeSinging(\frac{n}{2})$
$\quad \quad \IFeelLikeSinging(\frac{n}{2} - 1)$

If you run algorithm $\IFeelLikeSinging(9)$, how many times do you sing O Canada?

(a)

7

(b)

8

(c)

9

(d)

6

11 . Assume you write a multiple-choice exam that has 25 questions. For each question, four options are given to you, and exactly one of these options is the correct answer. Assume that you answer each question uniformly at random, where the choices for different questions are independent of each other. What is the probability that you have exactly 17 correct answers?

(a)

${25 \choose 17} \cdot \left( 1 \middle/ 4 \right)^8 \cdot \left( 3 \middle/ 4 \right)^{17}$

(b)

${25 \choose 17} \cdot \left( 1 \middle/ 4 \right)^{17}$

(c)

${25 \choose 17} \cdot \left( 3 \middle/ 4 \right)^{17}$

(d)

${25 \choose 17} \cdot \left( 1 \middle/ 4 \right)^{17} \cdot \left( 3 \middle/ 4 \right)^8$

12 . Consider a uniformly random bitstring of length 5. Define the events

A = "the first three bits are 101 or 110",
B = "the last three bits are 111".

Which of the following is true?

(a)

The events $A$ and $B$ are not independent.

(b)

None of the above.

(c)

The events $A$ and $B$ are independent.

13 . A certain terrible, no-good, mean-spirited, awful professor gives his students 250 sample exam questions and then makes his final exam by choosing 25 of these questions uniformly at random. Student Nika doesn't have much time to study so she chooses 50 (out of 250) random sample exam questions and practices on those.

When Nika writes the exam, what is the expected number of questions that appear on the exam and that Nika has practiced on?

(n.b., depending on your background, it may be helpful to observe that this can be modelled using the hypergeometric distribution)

(a)

5

(b)

2

(c)

20

(d)

10

14 . Continuing from the previous question, what is the probability that Nika has not practiced on any of the actual exam questions?

(a)

0

(b)

$\left. {225 \choose 25} \middle/ {250 \choose 50} \right.$

(c)

$\left. {225 \choose 50} \middle/ {250 \choose 50} \right.$

(d)

$\left. {225 \choose 25} \middle/ {225 \choose 50} \right.$

15 . A bowl contains 5 blue balls and 4 red balls. We choose 2 balls uniformly at random. Define the events

A = "both balls are red",
B = "both balls have the same color".

What is the conditional probability $\Pr(A|B)$?

(a)

$\frac{{4 \choose 2}}{{5 \choose 2} + {4 \choose 2}}$

(b)

$\frac{{5 \choose 2} + {4 \choose 2}}{{4 \choose 2}}$

(c)

$\frac{{4 \choose 2}}{{5 \choose 2} \cdot {4 \choose 2}}$

(d)

$\frac{{4 \choose 2}}{{9 \choose 2}}$

16 . We choose an element $x$ uniformly at random from the set $\{1,2,3,...,10\}$. Define the events

A = "$x$ is even",
B = "$x$ is divisible by 3".

What is the conditional probability $\Pr(A|B)$?

(a)

2/3

(b)

1/3

(c)

3/10

(d)

1/2

17 . We choose an element $x$ uniformly at random from the set $\{1,2,3,...,10\}$. Define the events

A = "$x$ is even",
B = "$1 \leq x \leq 5$".

Which of the following is true?

(a)

None of the above.

(b)

The events $A$ and $B$ are independent.

(c)

The events $A$ and $B$ are not independent.

18 . We choose an element $x$ uniformly at random from the set $\{1,2,3,...,10\}$. Define the events

A = "$x$ is even",
B = "$1 \leq x \leq 6$".

Which of the following is true?

(a)

The events $A$ and $B$ are not independent.

(b)

The events $A$ and $B$ are independent.

(c)

None of the above.

19 . When a couple has a child, this child is a boy with probability 1/2 and a girl with probability 1/2, independent of the sex of previous children. A couple stops having children as soon as they have a child that has the same sex as their first child. Define the events

A = "the second child is a boy",
B = "the couple has at least three children and the third child is a boy".

Which of the following is true?

(a)

None of the above.

(b)

The events $A$ and $B$ are not independent.

(c)

The events $A$ and $B$ are independent.

20 . I flip two fair and independent coins. If the first coin comes up tails, you lose \$1 (i.e., you win -\$1). If the second coin comes up heads, you win \$2. (Thus, if the first coin comes up tails and the second coin comes up heads, you win \$1.) Define the random variable $X$ to be the amount of dollars that you win. What is the expected value of $X$?

(a)

1/2

(b)

2

(c)

1

(d)

1/4

21 . Let $n \geq 2$ be an integer. Consider a string $c_1,c_2,...,c_n$ of length $n$, in which each character $c_i$ is a uniformly random element of the set $\{1,2,3\}$ (independently of all other characters). Consider the random variable $X$ whose value is the number of indices $i \in \{1,...,n - 1\}$ for which the product $c_i \cdot c_{i + 1}$ is odd.

What is the expected value $\mathbb{E}(X)$ of the random variable $X$?

Hint: Use indicator random variables.

(a)

$\frac{2}{3} \cdot n$

(b)

$\frac{4}{9} \cdot n$

(c)

$\frac{4}{9} \cdot (n - 1)$

(d)

$\frac{2}{3} \cdot (n - 1)$

22 . You are given a fair 6-sided red die and a fair 6-sided blue die. Consider the following experiment:

Experiment: Roll each die once and take the sum of the two rolls. You repeat this experiment until the sum of the two rolls is equal to 7. Consider the random variable

X = the number of times you do the experiment.

(This value $X$ includes the experiment in which the sum is 7 for the first time.)
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?

(a)

5

(b)

6

(c)

3

(d)

4

23 . Is the following statement true or false?

For any random variable $X$, $\mathbb{E}\left(1 \middle/ X \right) = 1 / \mathbb{E}(X)$.

(a)

The statement is true.

(b)

The statement is false.

(c)

None of the above.

24 . Let $n$ and $k$ be integers such that $n$ is even, $n \geq 2$, and $1 \leq k \leq n$. The Carleton Computer Science Society (CCSS) is having their annual ~~Christmas~~ Holiday Season Party, which is attended by $n$ students.

(i)	$k$ of these $n$ students are politically correct and, thus, refuse to say Merry Christmas. Instead, they say Happy Holidays.
(ii)	$n - k$ of these $n$ students do not care about political correctness and, thus, they say Merry Christmas.

Consider a uniformly random permutation of these $n$ students. The positions in this permutation are numbered as $1,2,...,n$.

Define the random variable $X$ as the number of positions $i$ with $1 \leq i \leq \left. n \middle/2 \right.$ such that both students at positions $i$ and $2i$ are politically correct.

What is the expected value $\mathbb{E}(X)$ of the random variable $X$?

Hint: Use indicator random variables.

(a)

$n \cdot \frac{k(k - 1)}{n(n - 1)}$

(b)

$n \cdot \frac{(k - 1)(k - 2)}{n(n - 1)}$

(c)

$\frac{n}{2} \cdot \frac{k(k - 1)}{n(n - 1)}$

(d)

$\frac{n}{2} \cdot \frac{(k - 1)(k - 2)}{n(n - 1)}$

25 . How do you feel about writing an exam on Friday evening?

(a)