Evaluation: 2015 Fall Final
1 .
Consider a set $S$ consisting of 20 integers; 5 of these are strictly positive and the other 15
integers in $S$ are strictly negative. What is the number of 3-element subsets of $S$ having the
property that the product of the 3 elements in the subset is negative?
(a)
${20 \choose 3}$
(b)
${15 \choose 3} + {15 \choose 2} \cdot 5 + 15 \cdot {5 \choose 2}$
(c)
${15 \choose 3}$
(d)
${15 \choose 3} + 15 \cdot {5 \choose 2}$
2 .
Consider a set $S$ consisting of 20 integers. The integer 0 is an element of $S$, 9 elements in $S$
are strictly positive, and the remaining 10 elements are strictly negative. What is the number of
7-element subsets of $S$ having the property that the product of the 7 elements in the subset is
equal to 0?
(a)
${19 \choose 6}$
(b)
${20 \choose 6}$
(c)
${19 \choose 7}$
(d)
${20}\choose{7}$
3 .
How many bitstrings $s_1s_2 \dots s_{20}$ of length 20 have the property that $s_1s_2s_3 = 000$ or
$s_2s_3s_4 = 000$?
(a)
$2^{17} - 2^{16}$
(b)
$2^{18} - 2^{17}$
(c)
$2^{18} - 2^{16}$
(d)
$2^{17} - 2^{15}$
4 .
What is the coefficient of $x^{15}y^{5}$ in the expansion of $(-3x + 5y)^{20}$?
(a)
$- {20 \choose 5} \cdot 5^{15} \cdot 3^5$
(b)
${20 \choose 5} \cdot 3^{15} \cdot 5^5$
(c)
${20 \choose 5} \cdot 5^{15} \cdot 3^5$
(d)
$- {20 \choose 5} \cdot 3^{15} \cdot 5^5$
5 .
In a group of 30 people,
- 10 are blond,
- 20 have green eyes,
- 9 are not blond and do not have green eyes.
(a)
11
(b)
9
(c)
10
(d)
8
6 .
Consider strings of characters, each character being $a$, $b$, or $c$, that contain at least one $a$.
Let $S_n$ be the number of such strings having length $n$. Which of the following is true?
(a)
$S_n = n \cdot 3^{n-1}$
(b)
$S_n = 3^{n} - 2^{n}$
(c)
$S_n = 3^{n} - n$
(d)
$S_n = n \cdot 2^{n-1}$
7 .
Consider strings of characters, each character being $a$, $b$, or $c$, that contain at least one $a$.
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}$
(b)
$S_n = 3 \cdot S_{n-1}$
(c)
$S_n = 2 \cdot S_{n-1} + 2 \cdot S_{n-2}$
(d)
None of the above.
8 .
Consider the following recursive function:
Which of the following is true?
| $f(0) = $ | $7,$ |
| $f(n) = $ | $2 \cdot f(n - 1) + 1\; \ \text{for all}$ $\text{integers}\ n \geq 1.$ |
(a)
$f(n) = 4n^{2} + 4n + 7$
(b)
$f(n) = 8n + 7$
(c)
None of the above.
(d)
$f(n) = 2^{n+3} - 1$
9 .
$\newcommand{\Fib}{{\rm F \scriptsize IB}}$
Consider the following 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$
(a)
7
(b)
5
(c)
6
(d)
4
10 .
What is the number of bitstrings of length $n$ that contain 00 or 11?
(a)
$2 \cdot n \cdot 2^{n-1}$
(b)
$2^n - 2$
(c)
$2^n - 4$
(d)
$2 \cdot (n-1) \cdot 2^{n-2}$
11 .
Nick gets 75 bananas for his birthday. He decides to eat them all over a period of 5 days. In order
to do this, Nick makes a banana-schedule, which specifies the number of bananas he is going to eat
on the first day, on the second day, etc., up to the fifth day. For example, (20, 20, 10, 20, 5),
(40, 13, 0, 20, 2), and (40, 13, 20, 2, 0) are three different banana-schedules. What is the
total number of banana-schedules?
(a)
${79 \choose 4}$
(b)
${80 \choose 4}$
(c)
${79 \choose 5}$
(d)
${80 \choose 5}$
12 .
A bowl contains 5 red balls and 7 blue balls. We choose a uniformly random subset of 3 balls. Define the event
- A = "exactly 2 of the chosen balls are red".
(a)
$\frac{{5 \choose 2} \cdot 7}{{12 \choose 3}}$
(b)
$\frac{5 \cdot {7 \choose 2}}{{12 \choose 3}}$
(c)
$\frac{{5 \choose 2}}{{12 \choose 3}}$
(d)
$\frac{{7 \choose 2}}{{12 \choose 3}}$
13 .
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".
(a)
The events $A$ and $B$ are independent.
(b)
None of the above.
(c)
The events $A$ and $B$ are not independent.
14 .
Let $n$ be the number of students who are writing this exam. Each of these students has a uniformly
random birthday, which is independent of the birthdays of the other students. We ignore leap years;
thus, the year has 365 days. Define the event
- A = "at least one student's birthday is on December 21".
(a)
$1 - (364/365)^{n}$
(b)
$n \cdot (1/365) \cdot (364/365)^{n-1}$
(c)
$1 - (1/365)^{n}$
(d)
$365 \cdot n \cdot (364/365)^{n-1}$
15 .
You are given that:
- The course COMP 9999 runs over a period of one year, starting on January 1 and ending on December 31. There is one lecture every day; thus, the total number of lectures is 365.
- Dania and Nick take this course. Dania's birthday is on November 19. Nick's birthday is on December 3.
- Professor G. Ruesome teaches the course. Professor Ruesome decides to have 20 quizzes during the year. For this, he chooses a uniformly random subset of 20 days; the quizzes will be on the 20 chosen days. (It is possible that there is a quiz on January 1.)
- A = "There is a quiz on Dania's birthday and there is a quiz on Nick's birthday".
(a)
$\left. {363 \choose 18} \middle/ {365 \choose 20} \right.$
(b)
$1 - \left. {363 \choose 20} \middle/ {365 \choose 20} \right.$
(c)
None of the above.
(d)
$\left. {365 \choose 18} \middle/ {365 \choose 20} \right.$
16 .
You are given that:
- The course COMP 9999 runs over a period of one year, starting on January 1 and ending on December 31. There is one lecture every day; thus, the total number of lectures is 365.
- Dania and Nick take this course. Dania's birthday is on November 19. Nick's birthday is on December 3.
- Professor G. Ruesome teaches the course. Professor Ruesome decides to have 20 quizzes during the year. For this, he chooses a uniformly random subset of 20 days; the quizzes will be on the 20 chosen days. (It is possible that there is a quiz on January 1.)
- B = "there is a quiz on Nick's birthday",
- C = "there are exactly 5 quizzes in December".
(a)
5/31
(b)
5/32
(c)
4/31
(d)
4/32
17 .
You are given that:
(n.b., you may find it useful to apply Linearity of Expectation)
- The course COMP 9999 runs over a period of one year, starting on January 1 and ending on December 31. There is one lecture every day; thus, the total number of lectures is 365.
- At the beginning of each of the 365 lectures, Nick flips a fair and independent coin twice. If the coin comes up heads twice, then Nick eats 3 bananas during the lecture; otherwise, Nick eats 5 bananas during the lecture.
(n.b., you may find it useful to apply Linearity of Expectation)
(a)
$\frac{9 \cdot 365}{2}$
(b)
$\frac{5 \cdot 365}{2}$
(c)
$4 \cdot 365$
(d)
$\frac{7 \cdot 365}{2}$
18 .
The $n$ students $S_1,S_2,\dots,S_n$ decide to organize a Secret Santa: They take a uniformly
random permutation $P_1,P_2,\dots,P_n$ of $S_1,S_2,\dots,S_n$. For each $i = 1,2,\dots,n$,
student $S_i$ buys a gift and gives it, anonymously, to student $P_i$.
Let $X$ be the number of students who give their gift to themselves. What is the expected value
$\mathbb{E}(X)$ of the random variable $X$?
Hint: Use an indicator random variable for each student.
(a)
$1 + 1/n$
(b)
$2$
(c)
$2 + 1/n$
(d)
$1$
19 .
The $n$ students $S_1,S_2,\dots,S_n$ decide to organize a Secret Santa: They take a uniformly
random permutation $P_1,P_2,\dots,P_n$ of $S_1,S_2,\dots,S_n$. For each $i = 1,2,\dots,n$,
student $S_i$ buys a gift and gives it, anonymously, to student $P_i$.
For each $i = 1,2,\dots,n$, let $v_i$ be the value (in dollars) of the gift that student $S_i$ buys. Let $Y$ be the value of the gift that student $S_1$ receives, and let $Z$ be the value of the gift that student $S_2$ receives. What is $\mathbb{E}(2 \cdot Y - Z)$?
(a)
$2 \sum_{i=2}^{n} v_i/n - (v_1/n + \sum_{i=3}^{n} v_i/n)$
(b)
$2v_1 - v_2$
(c)
$\sum_{i=1}^{n} v_i/n$
(d)
$\sum_{i=3}^{n} v_i/n$
20 .
You repeatedly, and independently, flip three fair coins, until there are exactly two heads among
the three flips. Define the random variable $X$ to be the total number of coin flips.
For example, if the coin flips result in
$$
(TTT), (THT), (HHH), (HTH),
$$
then $X = 12$.
What is the expected value $\mathbb{E}(X)$ of $X$?
What is the expected value $\mathbb{E}(X)$ of $X$?
(a)
8/3
(b)
8
(c)
12
(d)
3/8
21 .
Let $n$ be an integer with $n \geq 3$. Consider a bitstring of length $n$, in which each bit is 0
with probability 1/3 (and, thus, 1 with probability 2/3), independently of the other bits. Let
$X$ be the number of occurrences of 010 in this bitstring. For example, if the bitstring is
$$
0010100100,
$$
then $X = 3$.
What is the expected value $\mathbb{E}(X)$ of $X$?
Hint: Use indicator random variables.
What is the expected value $\mathbb{E}(X)$ of $X$?
Hint: Use indicator random variables.
(a)
$(n-2)/8$
(b)
$2(n-2)/27$
(c)
$n/8$
(d)
$2n/27$
22 .
Let $S = \{1,2,\dots,n\}$ and let $T$ be a set of $m$ unordered pairs of distinct elements of $S$. Thus,
$$
T \subseteq \{\{i,j\} : 1 \leq i < j \leq n\}.
$$
Consider a coin that comes up heads with probability 1/3 and, thus, tails with probability 2/3.
For each element of $S$, flip the coin, and let $S'$ be the set consisting of all elements of $S$ whose
coin flip resulted in heads. Let $T'$ be the set consisting of all elements $\{i,j\}$ in $T$ for which
both $i$ and $j$ are in $S'$.
Let $X$ be the size of the set $T'$. What is the expected value $\mathbb{E}(X)$ of $X$?
Hint: Use indicator random variables.
Let $X$ be the size of the set $T'$. What is the expected value $\mathbb{E}(X)$ of $X$?
Hint: Use indicator random variables.
(a)
$m/9$
(b)
$4n/9$
(c)
$4m/9$
(d)
$n/9$
23 .
Let $S$ be a uniformly random 2-element subset of $\{1,2,3,4\}$, and let $X$ be the number of
elements of $S$ that are even. What is the expected value $\mathbb{E}(X)$ of $X$?
(a)
1
(b)
3/2
(c)
2
(d)
5/2
24 .
$\newcommand{\Heads}{{\rm H \scriptsize EADS}}$
Consider a coin that comes up heads with probability 1/3 and, thus, tails with probability 2/3.
Consider the following recursive algorithm $\Heads$, which takes as input a positive integer $k$:
$\mathbf{Algorithm}\ \Heads(k)\mathrm{:}$
$\text{flip the coin};$
$\mathbf{if}\ \text{the coin came up heads}$
$\mathbf{then}\ \mathrm{return}\ k + 1$
$\mathbf{else}\ \Heads(k + 1)$
$\mathbf{endif}$
You run algorithm $\Heads(1)$, i.e., with $k = 1$. Define the random variable $X$ to be the value of
the output of this algorithm. Let $m \geq 1$ be an integer. What is $\Pr(X = m + 1)$?
| $//$ | $\text{all coin flips made}$ $\text{are mutually independent}$ |
$\mathbf{if}\ \text{the coin came up heads}$
$\mathbf{then}\ \mathrm{return}\ k + 1$
$\mathbf{else}\ \Heads(k + 1)$
$\mathbf{endif}$
(a)
$2^{m-1}/3^{m}$
(b)
$2^{m}/3^{m+1}$
(c)
$(2/3)^{m}$
(d)
$(2/3)^{m+1}$