Evaluation: 2015 Winter Midterm
1 .
The Carleton Computer Science Society has a Board of Directors consisting of a President and a
seven-person Advisory Board. The 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 \cdot {n \choose 7}$
(b)
$(n - 7) \cdot {n \choose 7}$
(c)
$(n - 7) + {n \choose 7}$
(d)
$n + {n \choose 7}$
2 .
Let $A$ be a set of 7 elements and let $B$ be a set of 15 elements.
How many functions $f : A \rightarrow B$ are there?
(a)
$7^{15}$
(b)
$15^7$
(c)
$15!/7!$
(d)
${15 \choose 7}$
3 .
Let $A$ be a set of 7 elements and let $B$ be a set of 15 elements. How many one-to-one (i.e.,
injective) functions $f : A \rightarrow B$ are there?
(a)
$10 \cdot 11 \cdot 12 \cdot 13 \cdot 14 \cdot 15$
(b)
$8 \cdot 9 \cdot 10 \cdot 11 \cdot 12 \cdot 13 \cdot 14 \cdot 15$
(c)
$9 \cdot 10 \cdot 11 \cdot 12 \cdot 13 \cdot 14 \cdot 15$
(d)
$9 \cdot 10 \cdot 11 \cdot 12 \cdot 13 \cdot 14$
4 .
Consider strings consisting of the characters $a$, $b$, and $c$. Such a string is called valid,
if no two consecutive characters are equal. Thus, $abacbac$ is valid, whereas $abaccac$ is not
valid.
Let $n \geq 1$ be an integer and let $V_n$ be the number of valid strings of length $n$. Which of the following is true?
Let $n \geq 1$ be an integer and let $V_n$ be the number of valid strings of length $n$. Which of the following is true?
(a)
None of the above.
(b)
$V_n = 3^n - (n - 1) \cdot 3 \cdot 3^{n-2}$
(c)
$V_n = 3 \cdot 2^{n-1}$
(d)
$V_n = 3^n - (n - 1) \cdot 3$
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)
None of the above.
(b)
$3^{99} - 2 \cdot 3^{96}$
(c)
$2 \cdot 3^{96} - 3^{93}$
(d)
$3^{96} + 3^{96}$
6 .
$\newcommand{\Silly}{{\rm S \scriptsize ILLY}}$
What does
$$
\sum_{k=2}^{n-1} (k-1)(n-k)
$$
count?
(a)
The number of 3-element subsets of an $(n-1)$-element set.
(b)
The number of 3-element subsets of an $n$-element set.
(c)
The number of times you fart when running algorithm $\Silly(n)$.
(d)
The number of 3-element subsets of an $(n+1)$-element set.
7 .
What is the minimum number of people needed so that we can guarantee that at least three of them
have the same birthday? (We ignore leap years; thus, a year has 365 days.)
(a)
$2 \cdot 365$
(b)
$365^2 + 1$
(c)
$2 \cdot 365 + 1$
(d)
$365^2$
8 .
What is the coefficient of $x^{17}$ in the expansion of $(17 + 2x)^{99}$?
(a)
None of the above.
(b)
$2^{17} \cdot 17^{82} \cdot {99 \choose 17}$
(c)
$2^{16} \cdot 17^{82} \cdot {99 \choose 16}$
(d)
$2^{82} \cdot 17^{17} \cdot {99 \choose 17}$
9 .
How many solutions are there to the equation $x_1 + x_2 + x_3 = 99$, where $x_1 \geq 0$, $x_2 \geq 0$,
and $x_3 \geq 0$ are integers?
(a)
${102 \choose 2}$
(b)
${101 \choose 2}$
(c)
${101 \choose 3}$
(d)
${102 \choose 3}$
10 .
The function $f: \mathbb{N} \rightarrow \mathbb{N}$ is defined by
$$
\begin{align}
f(0) &= 15 \\
f(n) &= f(n - 1) +6n - 4\; \ \mathrm{for}\ n \geq 1
\end{align}
$$
What is $f(n)$?
(a)
$f(n) = 3n^{2} - 2n + 15$
(b)
$f(n) = 3n^{2} + n + 15$
(c)
$f(n) = 3n^{2} - n + 15$
(d)
$f(n) = 3n^{2} + 2n + 15$
11 .
Consider strings consisting of the characters $a$, $b$, and $c$. Such a string is called valid,
if it does not contain the substring $aaa$. Let $S_n$ be the number of valid strings of length
$n$. Which of the following is true?
(a)
$S_n = 2 \cdot S_{n-1} + S_{n-2} + 2 \cdot S_{n-3}$
(b)
$S_n = 2 \cdot S_{n-1} + 2 \cdot S_{n-2} + 2 \cdot S_{n-3}$
(c)
$S_n = 2 \cdot S_{n-1} + 2 \cdot S_{n-2} + S_{n-3}$
(d)
$S_n = 2 \cdot S_{n-1} + 2 \cdot S_{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 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 1s.
Which of the following is true?
(a)
$S_n = S_{n-1} + S_{n-3}$
(b)
$S_n = S_{n-2} + S_{n-3}$
(c)
$S_n = S_{n-1} + S_{n-2} + S_{n-3}$
(d)
$S_n = S_{n-1} + S_{n-2}$
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)
4
(c)
5
(d)
7
14 .
(n.b., $\log$ denotes the base-2 logarithm)
$\newcommand{\NationalAnthem}{{\rm N {\scriptsize ATIONAL} A {\scriptsize NTHEM}}}
\newcommand{\elsesp}{\phantom{\mathbf{else}\ }}$
Consider the following recursive algorithm $\NationalAnthem$, which takes as input an integer $n \geq 1$,
which is a power of 2:
$\mathbf{Algorithm}\ \NationalAnthem(n)\mathrm{:}$
$\mathbf{if}\ n = 1$
$\mathbf{then}\ \mathrm{sing}\ {\it O\ Canada}\ \mathrm{once}$
$\mathbf{else}\ \NationalAnthem(n / 2);$
$\elsesp \mathrm{sing}\ {\it O\ Canada}\ \mathrm{once};$
$\elsesp \NationalAnthem(n / 2)$
$\mathbf{endif}$
(n.b., $\log$ denotes the base-2 logarithm)
(a)
$S(n) = 1 + \log n$
(b)
$S(n) = 1 + n \log n$
(c)
$S(n) = 2n + 1$
(d)
$S(n) = 2n - 1$
15 .
You flip a fair coin 5 times. Define the event
- A = "the number of heads is odd".
(a)
5/8
(b)
3/8
(c)
4/8
(d)
6/8
16 .
You flip a fair coin 11 times. Define the events
- A = "the number of heads is odd"
- B = "the number of tails is even".
(a)
$\Pr(A) > \Pr(B)$
(b)
$\Pr(A) = \Pr(B)$
(c)
None of the above.
(d)
$\Pr(A) < \Pr(B)$
17 .
In order to celebrate that the COMP 2804 midterm went well, you go to your neighborhood pub. This
pub has 16 different beers on tap:
- There are 7 beers of the pilsner type.
- There are 5 beers of the India pale ale type.
- There are 4 beers of the German wheatbeer type.
(a)
${16 \choose 4}$
(b)
${7 \choose 2} \cdot 5 \cdot 4 + 7 \cdot {5 \choose 2} \cdot 4 + 7 \cdot 5 \cdot {4 \choose 2}$
(c)
None of the above.
(d)
${16 \choose 4} - {7 \choose 3} - {5 \choose 3} - {4 \choose 3}$