Evaluation: 2013 Fall Midterm
1 . Let $A$ be a set of size 7 and let $B$ be a set of size 13. How many one-to-one functions $f: A \rightarrow B$ are there?
(a)
$\frac{13!}{6!}$
(b)
$\frac{6!}{13!}$
(c)
$\frac{13!}{5!}$
(d)
$\frac{13!}{7!}$
2 . You are given 5 books and 7 bookshelves. How many ways are there to place these books on the shelves? (The order on the shelves matters.)
(a)
$\frac{12!}{7!}$
(b)
${7}\choose{5}$
(c)
$\frac{11!}{7!}$
(d)
$\frac{11!}{6!}$
3 . A password consists of 6 or 7 characters, each character being an uppercase or a lowercase letter. A password must contain at least one uppercase letter. How many passwords are there?
(a)
$26 \cdot 52^{5} + 26 \cdot 52^{6}$
(b)
$52^{6} + 52^{7}$
(c)
None of the above.
(d)
$52^{6} + 52^{7} - 26^{6} - 26^{7}$
4 .
In a group of 20 people,
- 6 are blond,
- 7 have green eyes,
- 11 are not blond and do not have green eyes.
(a)
$4$
(b)
$3$
(c)
$5$
(d)
$9$
5 . How many bitstrings of length 55 start with 101 or end with 1111?
(a)
$2^{52} + 2^{51} - 2^{48}$
(b)
$2^{52} + 2^{51}$
(c)
$2^{55} - 2^{52} - 2^{51}$
(d)
$2^{55} - 2^{48}$
6 . Each person in a group of $ n $ people has a last name consisting of two uppercase letters. For what values of $ n $ can we guarantee that there are at least two people with the same last name?
(a)
$n \geq 677$
(b)
$n \geq 52$
(c)
$n \geq 676$
(d)
$n \geq 26$
7 . How many bitstrings of length 13 contain exactly 3 zeros?
(a)
${13}\choose{10}$
(b)
$2^{13} - 3$
(c)
$13!/3!$
(d)
$2^{13} - {{13}\choose{3}}$
8 . What is the coefficient of $ x^{12}y^{12} $ in the expansion of $ {(3x-7y)}^{24} $?
(a)
$-3^{12}7^{12}{{24}\choose{12}}$
(b)
$(3x)^{12}(-7y)^{12}{{24}\choose{12}}$
(c)
$(3x)^{12}(7y)^{12}{{24}\choose{12}}$
(d)
$21^{12}{{24}\choose{12}}$
9 . Which of the following is true?
(a)
$\sum_{k=0}^{n} 4^{k}5^{n-k}{{n}\choose{k}} = 20^{n}$
(b)
$\sum_{k=0}^{n} 5^{k}{{n}\choose{k}} = 6^{n}$
(c)
$\sum_{k=0}^{n} 5^{k}{{n}\choose{k}} = 5^{n}$
(d)
$\sum_{k=0}^{n} 4^{n-k}5^{k}{{n}\choose{k}} = 8^{n}$
10 . How many strings can be obtained by rearranging the letters of the word POOPERSCOOPER
(a)
$13!$
(b)
$4!3!2!2!1!1!$
(c)
${{13}\choose{4}}{{9}\choose{3}}{{6}\choose{2}}{{4}\choose{2}}{{2}\choose{1}}$
(d)
${{13}\choose{4}}{{9}\choose{3}}{{6}\choose{2}}{{4}\choose{2}}$
11 .
The function $ f: \mathbb{N} \rightarrow \mathbb{N} $ is defined by
$ f(0) = 14 $
$ f(n+1) = f(n) + 4n - 5 $ for $ n \geq 0 $
What is $ f(n) $?
(a)
$f(n) = 2n^{2} + 7n + 14$
(b)
$f(n) = 2n^{2} - 7n + 14$
(c)
$f(n) = 2n^{2} - 6n + 14$
(d)
$f(n) = 2n^{2} + 6n + 14$
12 .
$\newcommand{\Fib}{{\rm F \scriptsize IB}}$
Consider the 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)
$3$
(b)
$1$
(c)
$2$
(d)
$4$
13 .
$\newcommand{\Fib}{{\rm F \scriptsize IB}}$
Consider the 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)
$a_n = f_n - 1$
(b)
$a_n = f_n$
(c)
$a_n = f_{n-1}$
(d)
$a_n = f_{n+1}$
14 . What does the summation $ \sum_{k=7}^{n} \binom{k-1}{6} $ count?
(a)
The numbre of subsets of ${1, 2, 3, ..., n}$ having size 6
(b)
The numbre of subsets of ${1, 2, 3, ..., n}$ having size 5
(c)
The numbre of subsets of ${1, 2, 3, ..., n}$ having size 7
(d)
None of the above.
15 . If you flip a fair coin 4 times, what is the probability that the coin comes up heads exactly twice?
(a)
$1/{{4}\choose{2}}$
(b)
${{4}\choose{2}}/2^{4}$
(c)
$2^{4}/{{4}\choose{2}}$
(d)
$2/2^{4}$
16 . If you choose an element $ x $ uniformly at random from the set $ {1, 2, ..., 100} $, what is the probability that $ x $ is divisible by 4 or 5?
(a)
$45/100$
(b)
$2/5$
(c)
$1/5$
(d)
$9/100$