Evaluations

Evaluation: 2019 Fall Midterm

Author: Michiel Smid

1 . Carleton's Computer Science program has $f$ female students and $m$ male students, where $f \geq 1$ and $f + m \geq 4$. The Carleton Computer Science Society has a Board of Directors consisting of a President and three Vice-Presidents, all of whom are Computer Science students. The President is female and cannot be a Vice-President. In how many ways can a Board of Directors be chosen?
(a)
${f + m \choose 3}$
(b)
$(f - 1) \cdot {f + m \choose 3}$
(c)
$f \cdot {f + m - 1 \choose 3}$
(d)
$f \cdot {f + m \choose 3}$

2 . Let $k$ and $n$ be integers with $2 \leq k \leq n$ and consider the set $S = \{1,2,...,n\}$. What is the number of $k$-element subsets of $S$ that do not contain 1 and do not contain 2?
(a)
${n - 1 \choose k - 1}$
(b)
${n - 1 \choose k}$
(c)
${n - 2 \choose k}$
(d)
${n - 2 \choose k - 2}$

3 . Let $k$ and $n$ be integers with $2 \leq k \leq n$ and consider the set $S = \{1,2,...,n\}$. What is the number of $k$-element subsets of $S$ that do not contain 1 or do not contain 2?
(a)
${n \choose k} - {n - 1 \choose k - 1} - {n - 1 \choose k - 1}$
(b)
${n \choose k} - {n - 2 \choose k - 2}$
(c)
${n - 2 \choose k}$
(d)
${n - 1 \choose k} + {n - 1 \choose k}$

4 . For any integer $n \geq 3$, let $B_n$ be the number of bitstrings of length $n$ in which the first three bits are not all equal. Which of the following is true?
(a)
$B_n = 2^n - 2$
(b)
$B_n = 2^n - 6$
(c)
$B_n = 2 \cdot 2^{n - 3}$
(d)
$B_n = 6 \cdot 2^{n - 3}$

5 . Consider strings of length 4 over the alphabet $\{a,b,c,d\}$. How many such strings are there that start with $ad$ or end with $dcb$?
(a)
18
(b)
17
(c)
20
(d)
19

6 . Let $n \geq 5$ and consider strings of length $n$ over the alphabet $\{a,b,c,d\}$. How many such strings are there that start with $ad$ or end with $dcb$?
(a)
$4^{n - 2} + 4^{n - 3} - 4^{n - 5}$
(b)
$4^{n - 2} + 4^{n - 3}$
(c)
$4^n - 4^{n - 2} - 4^{n - 3}$
(d)
$4^n - 4^{n - 5}$

7 . What does $$ {w \choose 3} \cdot {m \choose 2} + {w \choose 4} \cdot m + {w \choose 5} $$ count?
(a)
The number of ways to choose 5 people out of a group consisting of $w$ women and $m$ men, where at least 3 women must be chosen.
(b)
The number of ways to choose 5 people out of a group consisting of $w$ women and $m$ men, where at most 3 men can be chosen.
(c)
The number of ways to choose 5 people out of a group consisting of $w$ women and $m$ men, where at most 3 women can be chosen.
(d)
The number of ways to choose 5 people out of a group consisting of $w$ women and $m$ men, where at least 3 men must be chosen.

8 . Let $n \geq 2$ be an integer and let $S$ be a set of $m$ integers. What is the minimum value of $m$ such that we can guarantee that $S$ contains at least two elements whose difference is divisible by $n$?
(a)
$n + 2$
(b)
$n$
(c)
$n - 1$
(d)
$n + 1$

9 . What is the coefficient of $x^{24}y^{26}$ in the expansion of $(5x - 7y)^{50}$?
(a)
${50 \choose 26} \cdot 5^{24} \cdot 7^{26}$
(b)
${50 \choose 24} \cdot 5^{26} \cdot 7^{24}$
(c)
$- {50 \choose 26} \cdot 5^{24} \cdot 7^{26}$
(d)
$- {50 \choose 24} \cdot 5^{26} \cdot 7^{24}$

10 . The function $f : \mathbb{Z}_{\geq 0} \rightarrow \mathbb{R}$ is defined by $$ f(n) = \begin{cases} 7 & \text{if}\ n = 0 \\ \frac{n}{3} \cdot f(n - 1) & \text{if}\ n \geq 1 \end{cases} $$ What is $f(n)$?
(a)
$f(n) = 7^n \cdot \frac{(n + 1)!}{3^n}$
(b)
$f(n) = 7 \cdot \frac{n!}{3^n}$
(c)
$f(n) = 7^n \cdot \frac{n!}{3^n}$
(d)
$f(n) = 7 \cdot \frac{(n + 1)!}{3^n}$

11 . For any integer $n \geq 1$, let $B_n$ be the number of bitstrings of length $n$ that do not contain the substring 11 and do not contain the substring 101. Which of the following is true for any $n \geq 4$?
(a)
$B_n = B_{n - 2} + B_{n - 4}$
(b)
$B_n = B_{n - 1} + B_{n - 3}$
(c)
$B_n = B_{n - 2} + B_{n - 3}$
(d)
$B_n = B_{n - 1} + B_{n - 2}$

12 . 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 3s and 4s, such that the order in which the 3s and 4s occur in the sum matters. For example, $S_5 = 0$, because 5 cannot be written as a sum of 3s and 4s. We have $S_{11} = 3$, because
$11$ $= 3 + 4 + 4 = 4 + 3 + 4$ $= 4 + 4 + 3.$
Which of the following is true for any $n \geq 5$?
(a)
$S_n = S_{n - 2} + S_{n - 3}$
(b)
$S_n = 2 \cdot S_{n - 1}$
(c)
$S_n = S_{n - 3} + S_{n - 4}$
(d)
$S_n = S_{n - 1} + S_{n - 2}$

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

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

When running $\Fib(12)$, how many calls are there to $\Fib(8)$?
(a)
5
(b)
4
(c)
7
(d)
6

14 . Consider the following recursive algorithm $\ElisaDrinksCider$, which takes as input an integer $n \geq 1$, which is a power of 2:

$\ElisaDrinksCider(n):$
$\quad \mathbf{if}\ n = 1\ \mathbf{then}$
$\quad \quad \text{then order Fibonachos}$
$\quad \mathbf{else}$
$\quad \quad \ElisaDrinksCider\left(n \middle/ 2 \right)$
$\quad \quad \mathrm{drink}\ n\ \text{bottles of cider}$
$\quad \quad \ElisaDrinksCider\left(n \middle/ 2 \right)$

For $n$ a power of 2, let $C(n)$ be the total number of bottles of cider that you drink when running algorithm $\ElisaDrinksCider(n)$. Which of the following is true for any $n \geq 1$ that is a power of 2?
(n.b., $\log$ denotes the base-2 logarithm)
(a)
$C(n) = n \log n + 1$
(b)
$C(n) = 2n \log n$
(c)
$C(n) = n \log n - 1$
(d)
$C(n) = n \log n$

15 . You flip a fair coin 9 times. Define the event
  • A = "the result of the first flip is not equal to the result of the second flip".
What is $\Pr(A)$?
(a)
1/3
(b)
1/2
(c)
1
(d)
1/4

16 . Consider 4 people, each of which has a uniformly random birthday. We ignore leap years; thus, one year has 365 days. Define the event
  • A = "at least 2 of these 4 people have the same birthday".
What is $\Pr(A)$?
(a)
$1 - \frac{362 \cdot 363 \cdot 364}{365^3}$
(b)
$1 - \frac{361 \cdot 362 \cdot 363 \cdot 364}{365^4}$
(c)
${4 \choose 2} \cdot \frac{1}{365}$
(d)
${4 \choose 2} \cdot \frac{1}{365} + {4 \choose 3} \cdot \frac{1}{365^2} + {4 \choose 4} \cdot \frac{1}{365^3}$

17 . In the game of Hearthstone, you are given a deck of 18 distinct cards. One of the cards is the Raven Idol. You choose a uniformly random hand of 3 cards. Define the event
  • A = "the hand of 3 cards contains the Raven Idol".
What is $\Pr(A)$?
(a)
3/17
(b)
3/18
(c)
$1 - (17/18)^3$
(d)
4/19