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)

None of the above.

(b)

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

(c)

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

(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^{77} - 2^{69}$

(b)

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

(c)

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

(d)

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

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

(a)

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

(b)

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

(c)

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

(d)

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

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)

3

(b)

5

(c)

6

(d)

4

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 a person can be on both committees.

(b)

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.

(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 pairs $(A,B)$ of subsets of the $n$ people, such that $|A| = 2$, $|B| = 5$, and $A \subseteq B$.

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 = 2 \cdot S_{n-1} + S_{n-2}$

(c)

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

(d)

$S_n = 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)

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

(c)

None of the above.

(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)

6

(c)

3

(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 divisible by 7.

(b)

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

(c)

None of the above.

(d)

For every element $(a,b)$ in $S$, $a + b$ is not 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)

${102 \choose 4}$

(b)

${103 \choose 4}$

(c)

${102 \choose 3}$

(d)

${103 \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)

7/15

(b)

6/15

(c)

8/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)

False

(b)

None of the above.

(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}^{20} \left({70 \choose k} + {30 \choose 20 - k}\right)$

(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}^{10} {70 \choose 2k}{30 \choose 20 - 2k}$

(d)

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

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)^{15}(2/3)^{62}$

(b)

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

(c)

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

(d)

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

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^5 \right.$

(c)

$\left. {5 \choose 2} \middle/ 2^3 \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)

$3n/2$

(d)

$2n$

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/2$

(b)

$m/16$

(c)

$m/4$

(d)

$m/8$

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)

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

(b)

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

(c)

None of the above.

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)) = 50$.

(c)

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

(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)

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

(c)

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

(d)

$(1/4)^{k-1} \cdot 3/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)

20

(b)

36

(c)

30

(d)

12

25 . Who is Lindsay Bangs?

(a)

A world-renowned rapper.

(b)

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

(c)

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

(d)

President of the Carleton Computer Science Society.

Evaluation: 2015 Winter Final