Evaluation comp2804/2015-winter-final

1 . Consider a set $S$ consisting of 20 integers; 5 of these are even and the other 15 integers in $S$ are odd. What is the number of 7-element subsets of $S$ having exactly 3 even integers?

(a)

${20 \choose 7}$

(b)

${5 \choose 3}{15 \choose 4}$

(c)

${5\choose 3} + {15 \choose 4}$

(d)

${5 \choose 4}{15 \choose 3}$

2 . Consider a set $S$ consisting of 20 integers; 5 of them are even and the other 15 integers in $S$ are odd. What is the number of 7-element subsets of $S$ having at least 5 even integers or at least 5 odd integers?

(a)

${5 \choose 5}{15 \choose 2} + {5 \choose 2}{15 \choose 5} - {5 \choose 5}{15 \choose 5}$

(b)

${5 \choose 5}{15 \choose 2} + {5 \choose 2}{15 \choose 5} + {5 \choose 1}{15 \choose 6} + {5 \choose 0}{15 \choose 7}$

(c)

None of the above.

(d)

${20 \choose 7} - {5 \choose 4}{15 \choose 4}$

3 . How many bitstrings of length 77 start with 1111 or end with 0000?

(a)

$2^{73} + 2^{73}$

(b)

$2^{77} - 2^{73} - 2^{73}$

(c)

$2^{74} - 2^{69}$

(d)

$2^{77} - 2^{69}$

4 . What is the coefficient of $x^{4}y^{11}$ in the expansion of $(2x - 7y)^{15}$?

(a)

$- {15 \choose 11} \cdot 2^4 \cdot 7^{11}$

(b)

${15 \choose 11} \cdot 2^4 \cdot 7^{11}$

(c)

${15 \choose 11} \cdot 2^{11} \cdot 7^4$

(d)

$- {15 \choose 11} \cdot 2^{11} \cdot 7^4$

5 . In a group of 20 people,

6 are blond,
7 have green eyes,
11 are not blond and do not have green eyes.

How many people in this group are blond and have green eyes?

(a)

4

(b)

5

(c)

3

(d)

6

6 . Let $n \geq 7$ be an integer. Why does the following equality hold: $$ {n \choose 5}{n - 5 \choose 2} = {n \choose 2}{n - 2 \choose 5} $$

(a)

Because both sides count the number of ways to choose 2 committees in a group of $n$ people, one committee has 5 members, the other committee has 2 members, and <strong>no</strong> person can be on both committees.

(b)

Because both sides count the number of pairs $(A,B)$ of subsets of the $n$ people, such that $|A| = 2$, $|B| = 5$, and $A \subseteq B$.

(c)

Because both sides count the number of pairs $(A,B)$ of subsets of the $n$ people, such that $|A| = 5$, $|B| = 2$, and $A \subseteq B$.

(d)

Because both sides count the number of ways to choose 2 committees in a group of $n$ people, one committee has 5 members, the other committee has 2 members, and a person can be on both committees.

7 . Consider strings of characters, each character being $a$, $b$, or $c$, that contain an odd number of $a$s. Let $S_n$ be the number of such strings having length $n$. Which of the following is true?

(a)

$S_n = 2 \cdot S_{n-1} + (3^{n-1} - S_{n-1})$

(b)

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

(c)

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

(d)

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

8 . Consider the following recursive function:

f(0) = $7$,
f(n) = $f(n - 1) + 6n - 3\; \ \text{for all}$ $\mathrm{integers}\ n \geq 1$.

Which of the following is true??

(a)

For all $n \geq 0$: $f(n) = 3n^2 + 7$

(b)

None of the above.

(c)

For all $n \geq 0$: $f(n) = 2n^2 + 7$

(d)

For all $n \geq 0$: $f(n) = 4n^2 + 7$

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

$\mathbf{Algorithm}\ \Fib(n)\mathrm{:}$
$\mathbf{if}\ n = 0\ \mathrm{or}\ n = 1$
$\mathbf{then}\ f = n$
$\mathbf{else}\ f = \Fib(n - 1) + \Fib(n - 2)$
$\mathbf{endif};$
$\mathbf{return}\ f$

If we run algorithm $\Fib(77)$, how many calls are there to $\Fib(73)$?

(a)

4

(b)

3

(c)

6

(d)

5

10 . Let $S$ be the set of ordered pairs of integers that is recursively defined in the following way:

$(1,6) \in S$.
If $(a,b) \in S$ then $(a+3, b+4) \in S$.
If $(a,b) \in S$ then $(a+5, b+2) \in S$.

Which of the following is true?

(a)

For every element $(a,b)$ in $S$, $a + b$ is not divisible by 7.

(b)

None of the above.

(c)

For every element $(a,b)$ in $S$, $a + b$ is divisible by 7.

(d)

$S = \{(a,b) : a > 0$ and $b > 0$ are integers and $a + b$ is divisible by 7$\}$.

11 . How many solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 99$, where $x_1 \geq 0$, $x_2 \geq 0$, $x_3 \geq 0$, $x_4 \geq 0$ are integers?

(a)

${103 \choose 4}$

(b)

${103 \choose 3}$

(c)

${102 \choose 4}$

(d)

${102 \choose 3}$

12 . Consider two events $A$ and $B$ in a sample space $S$. You are given that $\Pr(B) = 2/3$ and $\Pr(A|B) = 4/5$. What is $\Pr(A \cap B)$?

(a)

6/15

(b)

8/15

(c)

7/15

(d)

5/15

13 . Consider three events, $A$, $B$, and $C$ in a sample space $S$. Is the following true or false?

$\Pr\bigl(A \cup (\overline{B} \cap \overline{C})\bigr) = $

$\Pr(A) + \Pr(B)\ - $ $\Pr(C).$

(a)

None of the above.

(b)

False

(c)

True

14 . Let $S$ be a set of 100 integers; 30 of these are positive and the other 70 integers in $S$ are negative. We choose, uniformly at random, a 20-element subset of $S$. What is the probability that at least one of the elements in this subset is positive?

(a)

$\left. {30 \choose 1}{70 \choose 19} \middle/ {100 \choose 20} \right.$

(b)

$1 - \left. {70 \choose 20} \middle/ {100 \choose 20} \right.$

(c)

None of the above.

(d)

$\left. {30 \choose 1} \middle/ {100 \choose 20} \right.$

15 . Let $S$ be a set of 100 integers; 30 of these are positive and the other 70 integers in $S$ are negative. We choose, uniformly at random, a 20-element subset of $S$. Let $x$ be the product of the integers in the chosen subset. What is the probability that $x > 0$?

(a)

$\frac{1}{{100 \choose 20}} \sum_{k=0}^{10} {70 \choose 2k}{30 \choose 20 - 2k}$

(b)

$\frac{1}{{100 \choose 20}} \sum_{k=0}^{10} \left({70 \choose 2k} + {30 \choose 20 - 2k}\right)$

(c)

$\frac{1}{{100 \choose 20}} \sum_{k=0}^{20} {70 \choose k}{30 \choose 20 - k}$

(d)

$\frac{1}{{100 \choose 20}} \sum_{k=0}^{20} \left({70 \choose k} + {30 \choose 20 - k}\right)$

16 . Consider a bitstring of length 77, in which each bit is 0 with probability 1/3 (and, thus, 1 with probability 2/3), independently of the other bits. What is the probability that there are exactly 15 0s in this bitstring?

(a)

${77 \choose 15}((1/3)^{62} + (2/3)^{15})$

(b)

${77 \choose 15}(1/3)^{62}(2/3)^{15}$

(c)

${77 \choose 15}(1/3)^{15}(2/3)^{62}$

(d)

${77 \choose 15}((1/3)^{15} + (2/3)^{62})$

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

A = "the bitstring contains exactly two 0s",
B = "the bitstring contains an even number of 0s".

(Note that zero is even.) What is the conditional probability $\Pr(A|B)$?

(a)

$\left. 2^5 \middle/ {5 \choose 2} \right.$

(b)

$\left. {5 \choose 2} \middle/ 2^3 \right.$

(c)

$\left. {5 \choose 2} \middle/ 2^5 \right.$

(d)

$\left. {5 \choose 2} \middle/ 2^4 \right.$

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

A = "the bitstring contains an odd number of 0s"

and

B = "the first three bits in the bitstring are 111".

Which of the following is true?

(a)

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

(b)

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

(c)

None of the above.

19 . I flip a fair coin, independently, $n$ times. For each heads, you win \$3, whereas for each tails, you lose \$1. Define the random variable $X$ to be the amount of dollars that you win. What is the expected value of $X$?

(a)

$n$

(b)

$n/2$

(c)

$2n$

(d)

$3n/2$

20 . Let $G = (V,E)$ be a graph with vertex set $V$ and edge set $E$, let $n$ be the size of $V$, and let $m$ be the size of $E$. For each vertex of $V$, flip a fair and independent coin. Let $V'$ be the subset of $V$ consisting of all vertices of $V$ whose coin flip resulted in heads. Let $E'$ be the set consisting of all edges $(u,v)$ in $E$ for which both $u$ and $v$ are in $V'$. Define the random variable $X$ to be the number of edges in $E'$. What is the expected value of $X$?

(a)

$m/16$

(b)

$m/4$

(c)

$m/8$

(d)

$m/2$

21 . Consider a bitstring of length 5, in which each bit is 0 with probability 1/2 (and, thus, 1 with probability 1/2), independently of the other bits. Define the random variables $X$ and $Y$ as follows:

X = the number of 0s in this bitstring

and

Y = the value of the first bit in this bitstring.

Which of the following is true?

(a)

None of the above.

(b)

The random variables $X$ and $Y$ are not independent.

(c)

The random variables $X$ and $Y$ are independent.

22 . One of Lindsay and Simon is chosen uniformly at random. The person that is chosen wins \$100. Define the random variables $L$ and $S$ as follows:

L = the amount that Lindsay wins

and

S = the amount that Simon wins.

Which of the following is true?

(a)

$\mathbb{E}(L) = 50$ and $\mathbb{E}(\max(L,S)) = 100$.

(b)

$\mathbb{E}(L) = 100$ and $\mathbb{E}(\max(L,S)) = 100$.

(c)

$\mathbb{E}(L) = 100$ and $\mathbb{E}(\max(L,S)) = 50$.

(d)

$\mathbb{E}(L) = 50$ and $\mathbb{E}(\max(L,S)) = 50$.

23 . Consider the following recursive algorithm $\TwoTails$, which takes as input a positive integer $k$:

$\mathbf{Algorithm}\ \TwoTails(k)\mathrm{:}$

$//$	$\text{all coin flips made are mutually}$ $\text{independent}$

$\text{flip a fair coin twice};$
$\mathbf{if}\ \text{the coin came up heads exactly twice}$
$\mathbf{then}\ \mathrm{return}\ 2^k$
$\mathbf{else}\ \TwoTails(k + 1)$
$\mathbf{endif}$

You run algorithm $\TwoTails(1)$, i.e., with $k = 1$. Define the random variable $X$ to be the value of the output of this algorithm. Let $k \geq 1$ be an integer. What is $\Pr(X = 2^k)$?

(a)

$(1/4)^{k} \cdot 3/4$

(b)

$(1/4)^{k-1} \cdot 3/4$

(c)

$(3/4)^{k-1} \cdot 1/4$

(d)

$(3/4)^{k} \cdot 1/4$

24 . You repeatedly, and independently, roll two fair dice, until the sum of the values of the two dice is equal to 12. Define the random variable $X$ to be the number of times you roll the pair of dice. What is the expected value of $X$?

(a)

36

(b)

30

(c)

20

(d)

12

25 . Who is Lindsay Bangs?

(a)

President of the Carleton Computer Science Society.

(b)

Goalie of the Ottawa Senators, her nickname is The Hamburglar.

(c)

A world-renowned rapper.

(d)

Owner of the brewery that produces Leo's Early Breakfast IPA.

Evaluation: 2015 Winter Final