Evaluation: 2019 Winter Midterm
1 .
Consider bitstrings of length 13. The positions in these strings are numbered as $1,2,3,\dots,13$.
How many such bitstrings have the property that all bits at the odd positions are equal?
(a)
256
(b)
32
(c)
128
(d)
64
2 .
Consider permutations of the set $\{a,b,c,d,e,f,g\}$ that do not contain $bge$ (in this order).
How many such permutations are there?
How many such permutations are there?
(a)
$7! - 3!$
(b)
$7! - 5!$
(c)
$7! - 4!$
(d)
$7! - 6!$
3 .
Consider strings of length 15, where each character is a lowercase letter or an uppercase letter.
How many such strings contain at least one lowercase letter and at least one uppercase letter?
(a)
$52^{15} - 2 \cdot 26^{15}$
(b)
None of the above.
(c)
$52^{15} - 26^{15}$
(d)
$52^{15} - 3 \cdot 26^{15}$
4 .
Let $n \geq 8$ be an even integer and let $k$ be an integer with $2 \leq k \leq n/2$. Consider
$k$-element subsets of the set $S = \{1,2,\dots,n\}$. How many such subsets contain at least two even
numbers?
(a)
${n \choose k} - {n/2 \choose k - 1} - \frac{n}{2} \cdot {n/2 \choose k - 1}$
(b)
${n \choose k} - {n/2 \choose k - 1} - \frac{n}{2} \cdot {n/2 \choose k}$
(c)
${n \choose k} - {n/2 \choose k} - \frac{n}{2} \cdot {n/2 \choose k - 1}$
(d)
${n \choose k} - {n/2 \choose k} - \frac{n}{2} \cdot {n/2 \choose k}$
5 .
In a group of 100 students,
- 37 students like beer,
- 18 students like cider,
- 55 students do not like beer and do not like cider.
(a)
8
(b)
11
(c)
10
(d)
9
6 .
Let $n \geq 1$ be an integer. A group of $n$ students write an exam. Each student receives a grade,
which is an element of the set $\{A, B, C, D, F\}$.
What is the minimum value for $n$, such that there must be at least four students who receive the same grade?
What is the minimum value for $n$, such that there must be at least four students who receive the same grade?
(a)
16
(b)
14
(c)
17
(d)
15
7 .
Consider 17-element subsets of the set $\{1,2,3,\dots,45\}$.
How many such subsets have the property that the largest element in the subset is equal to 30?
How many such subsets have the property that the largest element in the subset is equal to 30?
(a)
${{29}\choose{16}}$
(b)
${30 \choose 16}$
(c)
${30 \choose 17}$
(d)
${29 \choose 17}$
8 .
Let $n \geq 4$ be an integer. What does
$$
3 \cdot { n\choose 3} + 6n \cdot {n \choose 2} + n^3
$$
count?
(a)
The number of ways to choose 3 elements (with repetitions allowed) in a set consisting of $n$ beer bottles, $n$ cider bottles, and $n$ wine bottles.
(b)
The number of ways to choose a 3-element subset of a set consisting of $n$ beer bottles, $n$ cider bottles, and $n$ wine bottles.
(c)
The number of ways to choose an ordered triple
<p style="text-align: center; margin: 0.5rem 0;">
(beer bottle, cider bottle, wine bottle)
</p>
in a set consisting of $n$ beer bottles, $n$ cider bottles, and $n$ wine bottles.
(d)
None of the above.
9 .
Let $n \geq 4$ be an even integer and let $k$ be an integer with $1 \leq k \leq n/2$. Consider
strings consisting of $n$ characters, such that
- each character is an element of $\{a, b, c\}$,
- the number of $a$'s is equal to $k$, and
- each $a$ is at an even position.
(a)
${n/2 \choose k} \cdot 2^{n/2}$
(b)
${n \choose k} \cdot 2^{n/2}$
(c)
${n \choose k} cdot 2^{n-k}$
(d)
${n/2 \choose k} \cdot 2^{n-k}$
10 .
A bitstring is called 00-free, if it does not contain two 0's next to each other.
In class, we have seen that for any $m \geq 1$,
the number of 00-free bitstrings of length $m$ is equal to the $(m+2)$-th Fibonacci number
$f_{m+2}$.
What is the number of 00-free bitstrings of length 77 that have 0 at position 59? (The positions are numbered $1,2,\dots,77$.)
What is the number of 00-free bitstrings of length 77 that have 0 at position 59? (The positions are numbered $1,2,\dots,77$.)
(a)
$f_{19} \cdot f_{59}$
(b)
$f_{20} \cdot f_{60}$
(c)
$f_{18} \cdot f_{58}$
(d)
$f_{17} \cdot f_{57}$
11 .
The function $f : \mathbb{N} \rightarrow \mathbb{N}$ is recursively defined as follows:
$$
\begin{align}
f(0) &= 6, \\
f(n) &= 4 \cdot f(n-1) + 2^{n} \ \ \mathrm{if}\ n \geq 1.
\end{align}
$$
Which of the following is true for all integers $n \geq 0$?
(a)
$f(n) = 7 \cdot 4^{n} - 2^{n}$
(b)
$f(n) = 8 \cdot 4^{n} - 2^{n+1}$
(c)
None of the above.
(d)
$f(n) = 6 \cdot 4^{n} - 2^{n}$
12 .
Consider strings of characters, where each character is an element of the set $\{a, b, c\}$. Such a
string is called awesome, if it does not contain $aa$, and does not contain $aba$, and does not contain $abb$.
For any integer $n \geq 1$, let $A_n$ be the number of awesome strings of length $n$.
Which of the following is true for any integer $n \geq 4$?
For any integer $n \geq 1$, let $A_n$ be the number of awesome strings of length $n$.
Which of the following is true for any integer $n \geq 4$?
(a)
$A_n = 2 \cdot A_{n-1} + A_{n-2} + 2 \cdot A_{n-3}$
(b)
$A_n = 2 \cdot A_{n-1} + A_{n-2} + A_{n-3}$
(c)
$A_n = A_{n-1} + 2 \cdot A_{n-2} + A_{n-3}$
(d)
$A_n = A_{n-1} + 2 \cdot A_{n-2} + 2 \cdot A_{n-3}$
13 .
We consider binary $2 \times n$ matrices, i.e., matrices with 2 rows and $n$ columns, in which each
entry is 0 or 1. A column in such a matrix is called a $1 \atop 1$-column,
if both bits in the column are 1.
For any integer $n \geq 1$ and integer $k$ with $0 \leq k \leq n$, let $M(n,k)$ be the number of binary $2 \times n$ matrices
For any integer $n \geq 1$ and integer $k$ with $0 \leq k \leq n$, let $M(n,k)$ be the number of binary $2 \times n$ matrices
- that do not contain any $1 \atop 1$-column, and
- contain exactly $k$ many 1's.
(a)
$M(n,k) = M(n,k-1)\ +$$\ M(n-1,k-1)$
(b)
$M(n,k) = M(n,k-1)\ +$$\ 2 \cdot M(n-1,k-1)$
(c)
$M(n,k) = M(n-1,k)\ +$$\ 2 \cdot M(n-1,k-1)$
(d)
$M(n,k) = M(n-1,k)\ +$$\ M(n-1,k-1)$
14 .
$\newcommand{\HelloWorld}{{\rm H {\scriptsize ELLO} W {\scriptsize ORLD}}}$
Consider the recursive algorithm $\HelloWorld$, which takes as input an integer $n \geq 0$:
$\mathbf{Algorithm}\ \HelloWorld(n)\mathrm{:}$
$\mathbf{if}\ n = 0\ \mathrm{or}\ n = 1$
$\mathbf{then}\ \mathrm{print}\ \mathit{Hello}\ \mathit{World}$
$\mathbf{else}\ \mathbf{if}\ n \text{ is a multiple of } 3$
$\qquad \mathbf{then}\ \HelloWorld\left( n \middle/ 3 \right);$
$\qquad \qquad \ \ \mathrm{print}\ \mathit{Hello}\ \mathit{World};$
$\qquad \qquad \ \ \HelloWorld\left( 2n \middle/ 3 \right)$
$\qquad \mathbf{else}\ \HelloWorld(n + 1)$
$\qquad \mathbf{endif};$
$\mathbf{endif}$
(a)
All of the above.
(b)
There exists an integer $n \geq 0$, for which algorithm $\HelloWorld(n)$ does not terminate.
(c)
None of the above.
(d)
For any integer $n \geq 0$, algorithm $\HelloWorld(n)$ terminates.
15 .
The Carleton Computer Science Society (CCSS) is organizing their annual Saint Patrick's Day party.
The CCSS has bought three types of drinks:
There are 75 students at the party, and each of them gets one drink, which is chosen uniformly at random from these three types.
Let $A$ be the event
- Porterhouse Brewing Co. Oyster Stout,
- Guinness Extra Stout,
- Magners Original Irish Cider.
There are 75 students at the party, and each of them gets one drink, which is chosen uniformly at random from these three types.
Let $A$ be the event
- A = "exactly 50 students get Magners Original Irish Cider".
(a)
$\frac{3^{75}}{{75 \choose 50} \cdot 2^{25}}$
(b)
$\frac{75 \choose 50}{3^{75}}$
(c)
$\frac{{75 \choose 50} \cdot 3^{25}}{3^{75}}$
(d)
$\frac{{ 75 \choose 50 } \cdot 2^{25}}{3^{75}}$
16 .
Consider a standard 6-sided fair die. We roll this die 8 times. Let $A$ be the event
- A = "there are at least two 5's in the sequence of 8 rolls".
(a)
$1 - {\frac{6^{8}}{5^{8} + 8 \cdot 5^{7}}}$
(b)
$1 - {\frac{8 \cdot 5^{7}}{6^{8}}}$
(c)
$1 - {\frac{8^{5} + 8 \cdot 7^{5}}{8^{6}}}$
(d)
$1 - {\frac{5^{8} + 8 \cdot 5^{7}}{6^{8}}}$
17 .
This midterm has 17 questions. For each question, four options are given, exactly one of which is
correct. Assume that you answer each question, by choosing one of the four options uniformly at random.
Let A be the event
Let A be the event
- A = "you answer at least 16 questions correctly".
(a)
$\frac{51}{4^{17}}$
(b)
$\frac{49}{4^{17}}$
(c)
$\frac{52}{4^{17}}$
(d)
$\frac{4^{17}}{52}$