CIS 66 – Midterm 2 Last Name (print) ______
(Spring 2002)
ssn (last 4 digits) First Name (print) ______
______Signature ______
True or False (10 points)
1. The proof technique of mathematical induction can be stated as:
[P(1) Ù "n ³ 1 (P(n) ® P(n + 1))] ® " n P(n) T or F
2. If the digits 0, 1, 2, ..., 9 are well formed formulas, and (x+y) and
(x*y) are well formed formulas and if x and y are well formed
formulas, then (4+((1*2)+3)) is a well formed formula. T or F
3. The string "aab" is a member of the set S* of strings over the
alphabet S = {a, b} defined recursively by
l ÎS*, yyx Î S* if x Î S*and y Î S T or F
4. The set S of all nonnegative powers of 2 (1, 2, 4, 8, ...)
can be defined recursively as: 1 Î S, x + y Î S if x Î S and y Î S T or F
5. The Fibonacci numbers f0, f1, f2, … , are defined by the equations
f0 = 0, f1 = 1, fn = fn+1 + fn+2, for n = 2, 3, 4, …. T or F
6. The generalized pigeonhole principle states that, if N objects are
placed into k boxes, there is at least one box containing ëN/kû
objects. T or F
7. According to Pascal's identity, if n and k are positive integers
with n ³ k, then C(n+1,k) = C(n,k-1) + C(n,k) T or F
8. If n and r are nonnetative integers with r £ n, then
P(n,r) = P(n, n-r) T or F
9. The events E and F are independent if and only if
P(E È F) = p(E)p(F). T or F
10. The conditional probability of event E given event F, p(E|F),
equals p(E | F) = P(E Ç F) / p(E). T or F
Numerical Answer (fractions are OK, 20 points)
1. P(8,2) _____
2. C(8,6) _____
3. C(8,2) _____
4. f(2) and f(3) where f(0)=4, f(1)=10,
and f(n) = f(n-1) * f(n-2) for n ³ 2 f(2) _____ f(3) _____
5. procedure silly (n: nonnegative integer) silly(1) _____
if n < 1 then
silly(n) := 0 silly(2) _____
else
silly(n) := 2+silly(n-1) silly(3) _____
6. What is the probability of flipping a "fair" coin 6 times
and getting 6 heads? _____
7. If two cards are drawn from a deck of 52 cards, what is the
probability that they both have the same value (e.g. two kings). _____
8. If a single card is drawn from a deck of 52 cards, what is
the probability that it is either a king or a heart (or both)? _____
9. What is the probability that, when two dice are rolled,
the product of the numbers on the two dice is 4 (e.g. 1 and 4)? _____
10. A fair coin is tossed and the random variable X(s) is defined as
10 if the coin comes up heads and 20 if the coin comes up tails.
What is E(X). _____
What is E(X - E(X))2 _____
11. How many positive integers less than 700 are divisible by 7. _____
12. How many subsets of the set {a, b, c, d, e, f} are there? _____
13. How many ways can you select a committee of 3 people from
a class of 6 people? _____
14. How many ways can you select a president, vice president and
treasurer from a class of 6 people? _____
15. If Denise sells 2 different kinds of doughnuts, how may different
bags of 4 doughnuts could you purchase. _____
Short Answer (formulas like C(10,2) are OK, 20 points)
1. How many different ways can you select 7 cards from a deck of 52 cards (the order does not matter). ______
2. How many different ways can Santa distribute 10 unique gifts to John and Mary, assuming John gets 4 of the gifts and Mary gets the other 6?
______
3. How many different strings can be made from rearranging the letters in the word "R E A R R A N G E".
______
4. Provide a recursive definition for the set S = {1, 10, 100, 1000, ... }
______
5. Provide a recursive definition for the function f(n) = 10*n for n = 0, 1, 2, 3, …
______
6. How many solutions are there to the equation x + y + z = 10, when x, y, and z are constrained to be integers greater than 2.
______
7. How many positive integers less than or equal to 1000 are
divisible by 5 or 7 (or both).
______
8. How many ways can you elect a president, a vice-president, and a treasurer (3 positions) from our 18 teaching assistants?
______
9. Generate four different well-formed formulae if the binary digit “0” is well-formed and (x + y) is well-formed if x and y are well-formed.
______
10. A coin, when tossed, come up heads 6/10 of the time. What is the probability of tossing the coin 10 times of getting 7 heads and 3 tail (in any order).
______
Recursive Proof (10 points)
Using mathematical induction, show (prove) that:
1 + 4 + 7 + ... + (3n – 2) = n*(3n – 1) for n ³ 1
2
You must label the basis step, the inductive hypothesis, and the inductive conclusion
as well as the algebraic steps so that I can follow your logic.
Proof by Contradiction (5 points)
Show that, if n is odd, then n2 is odd using a proof by contradiction.
Strings of 8-Digit Hexadecimal Numbers (10 points)
Consider a string of 8-digit hex numbers (00000000 to FFFFFFFF). Provide formulas (e.g. 26 + 25) for each of the following:
1. How many different 8-digit hexadecimal numbers are there?
2. How many different 8-digit hex numbers begin with a “letter” (A through F).
3. How many different 8-digit hex numbers end with two “decimal” digits (00 through 99).
4. How many different 8-digit hex numbers begin with letter and end with two “decimal” digits, (or both).
5. How many different 8-digit hex numbers contain exactly two "F’s",
(like FF012345 or 0F000F00)?
Recursive Algorithm (5 points)
Write a recursive algorithm for computing Fibonacci Numbers F(n), n ³ 0 where F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)
procedure F(n: nonnegative integer)
______
______
______
______
Probability (10 points) (the answer must be a formula)
1. What is the probability of getting "3 of a kind" if you are dealt 5 cards from a deck of 52 cards? (Note that the last two cards must have values
different from the first three and different from each other.)
______
2. If you are dealt 5 cards from a deck of 52 cards, what is the probability that all 5 cards have different values (e.g. 2, 4, 8, J, K)?
______
3. What is the probability of winning the "pick 6" lottery, where 6 balls are drawn from a single urn containing balls numbered 1 through 40, and the order of drawing the balls does not count.
______
4. What is the probability of winning the "pick 3" daily lottery, where 3 balls are drawn from three different urns each containing balls numbered 1 through 10, and the order of drawing the balls does count.
______
5. A roulette wheel has 18 “red” numbers, 18 “black” numbers, and 2 “green” numbers. What is the probability that ten “spins” of the wheel produce ten “red” numbers?
______
Probability (10 points) (the answer must be a number)
1. What is the conditional probability that exactly two heads
appear when a fair coin is flipped three times, given that the
first flip came up heads. _____
2. A pair of dice is rolled and we are told that the sum of the dice is
greater than 4. What is the probability that the sum is equal to 5
given this added information? _____
3. Let E and F be events with p(E) = .4 and p(F) = .8, and
p(E Ç F) = .2, what is p(E | F) _____
4. In question 3, are E and F independent? Yes No
- Two fair coins are tossed and the random variable X(s) is defined as
the number of heads that appear (0, 1 or 2).
What is E(X). _____
What is E(X - E(X))2 _____