Evaluation: 2015 Fall Midterm
1 .
The Carleton Computer Science Society has a Board of Directors consisting of a President, two
Vice-Presidents, and a five-person Advisory Board. The President cannot be Vice-President and cannot be
on the Advisory Board. A Vice-President cannot be on the Advisory Board. Let $n$ be the number of
students in Carleton's Computer Science program, where $n \geq 8$. In how many ways can a Board of
Directors be chosen?
(a)
$(n-5){n \choose 2}{n-1 \choose 5}$
(b)
$(n-7){n \choose 2}{n-2 \choose 5}$
(c)
$(n-2){n\choose 2}{n-2 \choose 5}$
(d)
$n{n \choose 2}{n \choose 5}$
2 .
Let $S$ be a set of 25 elements and let $x$, $y$, and $z$ be three distinct elements of $S$. What is
the number of subsets of $S$ that contain both $x$ and $y$, but do not contain $z$?
(a)
$2^{23}$
(b)
$2^{25} - 2^{24} + 2^{23}$
(c)
$2^{22}$
(d)
$2^{25} - 2^{22}$
3 .
Let $A$ be a set of 6 elements and let $B$ be a set of 13 elements. How many one-to-one (i.e.,
injective) functions $f : A \rightarrow B$ are there?
(a)
$8 \cdot 9 \cdot 10 \cdot 11 \cdot 12 \cdot 13$
(b)
$6 \cdot 7 \cdot 8 \cdot 9 \cdot 10 \cdot 11 \cdot 12 \cdot 13$
(c)
$7 \cdot 8 \cdot 9 \cdot 10 \cdot 11 \cdot 12 \cdot 13$
(d)
$5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10 \cdot 11 \cdot 12 \cdot 13$
4 .
For any integer $n \geq 2$, let $S_n$ be the number of bitstrings of length $n$ in which the first
bit is not equal to the last bit. Which of the following is true?
(a)
$S_n = 2^{n-1}$
(b)
$S_n = 2^{n} - 2^{n-1} + 2^{n-2}$
(c)
$S_n = 2^{n-2}$
(d)
$S_n = 2^{n} - 2^{n-2}$
5 .
Consider strings of length 99 consisting of the characters $a$, $b$, and $c$. How many such strings
are there that start with $abc$ or end with $bbb$?
(a)
$2 \cdot 3^{96} - 3^{93}$
(b)
$3^{96} + 3^{96}$
(c)
$3^{99} - 2 \cdot 3^{96}$
(d)
None of the above.
6 .
What does
$$
\sum_{k=1}^{m} {m \choose k}
$$
count?
(a)
The number of bitstrings of length $m$ having exactly $k$ many 1s.
(b)
None of the above.
(c)
The number of non-empty subsets of a set of size $m$.
(d)
The number of subsets of a set of size $m$.
7 .
$\newcommand{\ShortLastName}{{\rm S {\scriptsize HORT} L {\scriptsize AST} N {\scriptsize AME}}}$
In the city of $\ShortLastName$, every person has a last name consisting of two characters, the first one being
an uppercase letter and the second one being a lowercase letter. What is the minimum number of people
needed so that we can guarantee that at least 4 of them have the same last name?
(a)
$4 \cdot 26^{2}$
(b)
$3 \cdot 26^{2} + 1$
(c)
$4 \cdot 26^{2} + 1$
(d)
$3 \cdot 26^{2}$
8 .
What is the coefficient of $x^{81}y^{7}$ in the expansion of $(3x-17y)^{88}$?
(a)
$- {88 \choose 7} \cdot 3^7 \cdot 17^{81}$
(b)
${88 \choose 7} \cdot 3^{81} \cdot 17^7$
(c)
${88 \choose 7} \cdot 3^7 \cdot 17^{81}$
(d)
$- {88 \choose 7} \cdot 3^{81} \cdot 17^7$
9 .
How many solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 55$,
where $x_1 \geq 0$, $x_2 \geq 0$, $x_3 \geq 0$, and $x_4 \geq 0$ are integers?
(a)
${58 \choose 3}$
(b)
${59 \choose 4}$
(c)
${59 \choose 3}$
(d)
${58 \choose 4}$
10 .
The function $f : \mathbb{N} \rightarrow \mathbb{N}$ is defined by
$$
\begin{align}
f(0) &= 7 \\
f(n) &= f(n - 1) + 10n - 6\; \ \mathrm{for}\ n \geq 1
\end{align}
$$
What is $f(n)$?
(a)
$f(n) = 5n^2 - 2n + 7$
(b)
$f(n) = 4n^2 - 2n + 7$
(c)
$f(n) = 5n^2 - n + 7$
(d)
$f(n) = 4n^2 - n + 7$
11 .
Let $S_n$ be the number of bitstrings of length $n$ that contain the substring 0000. Which of the
following is true?
(a)
$S_n = S_{n-1} + S_{n-2} + S_{n-3} + S_{n-4}$
(b)
$S_n = S_{n-1} + S_{n-2} + S_{n-3} + S_{n-4}\ +$ $ 2^{n-4}$
(c)
$S_n = S_{n-1} + S_{n-2} + S_{n-3}$
(d)
$S_n = S_{n-1} + S_{n-2} + S_{n-3} + 2^{n-3}$
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 1s and 2s, such that
Which of the following is true?
- the order in which the 1s and 2s occur in the sum matters, and
- it is not allowed to have two consecutive 2s.
Which of the following is true?
(a)
$S_n = S_{n-2} + S_{n-3}$
(b)
$S_n = S_{n-1} + S_{n-3}$
(c)
$S_n = S_{n-1} + S_{n-2}$
(d)
$S_n = S_{n-1} + S_{n-2} + S_{n-3}$
13 .
$\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)
6
(b)
9
(c)
7
(d)
8
14 .
(n.b., $\log$ denotes the base-2 logarithm)
$\newcommand{\JustinBieber}{{\rm J {\scriptsize USTIN} B {\scriptsize IEBER}}}
\newcommand{\elsesp}{\phantom{\mathbf{else}\ }}$
Consider the following recursive algorithm $\JustinBieber$, which takes as input an integer $n \geq 1$,
which is a power of 2:
(see document for missing code)
For $n$ a power of 2, let $B(n)$ be the number of times you print "I don't like Justin Bieber" when
running algorithm $\JustinBieber(n)$. Which of the following is true? (n.b., $\log$ denotes the base-2 logarithm)
(a)
$B(n) = \log n - 1\ \text{for all}\ n \geq 1.$
(b)
$B(n) = n - 2\ \text{for all}\ n \geq 2.$
(c)
$B(n) = \log n - 1\ \text{for all}\ n \geq 2.$
(d)
$B(n) = \log n\ \text{for all}\ n \geq 2.$
15 .
You flip a fair coin 7 times. Define the event
- A = "the result of the first flip is equal to the result of the 7-th flip".
(a)
$1/2$
(b)
$\frac{2^5 + 2}{2^7}$
(c)
$1/4$
(d)
$1/3$
16 .
You roll a fair 6-sided die twice. Define the events
- A = "the sum of the results of the two rolls is 7"
- B = "the result of the first roll is 3".
(a)
None of the above.
(b)
$\Pr(A) = \Pr(B)$
(c)
$\Pr(A) > \Pr(B)$
(d)
$\Pr(A) < \Pr(B)$
17 .
Let $S = \{1,2,3,4,5,6,7\}$. You choose a uniformly random 3-element subset $X$ of $S$. Thus,
each 3-element subset of $S$ has a probability of $\left. 1 \middle/ {7 \choose 3} \right.$ of being $X$.
Define the event
- A = "4 is an element of $X$".
(a)
15/7
(b)
3/7
(c)
7/15
(d)
7/3