math vic
RiverFlowsInYou
Exam2SolutionTTh1.pdf
Exam 2: Solution
5.1 Prove by mathematical induction that 0 1 11 2 2 2 ... 2 1 2 1n nn n (5 points)
0 11 2 1 1 2 1
Assume 1 10 1 11 2 2 2 ... 1 2 1 1 2 1n nn n
I.e. 0 1 2 11 2 2 2 ... 1 2 2 2 1n nn n
Then 0 1 2 1 1 11 2 2 2 ... 1 2 2 2 2 1 2n n n nn n n n
0 1 1 1 1 1
0 1 1 1
0 1 1 1
0 1 1 1
0 1 1
1 2 2 2 ... 2 2 2 2 1 2
1 2 2 2 ... 2 2 ( 2 ) 1
1 2 2 2 ... 2 2 (2 2) 1
1 2 2 2 ... 2 2 2( 1) 1
1 2 2 2 ... 2 ( 1)2 1
n n n n
n n
n n
n n
n n
n n n
n n n
n n
n n
n n
5.2 Let 1 2 1 2
2, 4, 2 if 2 n n n
a a a a a n
. Use strong induction to prove that 2 n
n a . (5 points)
1
1 2a ,
2
2 2a
Assume 2 k
k a for all k n with 2k
So for 1k n , 1
1 2
n
n a
, and for 2k n ,
2
2 2
n
n a
1 2 1 1 1
1 2 1 2 2, 4, 2 =2 2 2 2 2 2 2 2
n n n n n n
n n n a a a a a
A3/3.1 Describe a non-recursive algorithm that takes a list of integers 1 2 , ,...,
n a a a and finds the first location (i.e. index)
of the largest number on the list.. Write your answer in pseudo-code or any well-known procedural language like Python,
Java, C++, ….
E.g. For the list 1 2 3 4 5 , , , ,a a a a a = 2, 3, 6, 5, 6 your program should return 3 because
3 a , the third element of the list, is
the first time the largest number occurs.
procedure First_Time_Largest ( 1 2 , ,..., :
n a a a integers)
index = 1
largest_so_far = 1
a
for i = 2 to n
if i
a largest_so_far
index = i
largest_so_far = i
a
return index
8.3 (7.3) Write a recursive algorithm to compute the nth term of the recursively defined sequence
1 2 3 1 2 3 1, 2, 3, if 3
n n n n a a a a a a a n
(5 points)
procedure nth-term ( n Z
)
if 1n return 1
else if 2n
return 3
else
return nth-term(n-1)+nth-term(n-2)
6.1/6.3 A symphony orchestra has in its repertoire 30 Haydn pieces, 15 modern pieces, and 9 Beethoven pieces. (2.5 points each)
a) How many ways can the orchestra play 3 pieces if they are allowed to play the same piece more than once? 3
54
b) How many ways can the orchestra play 3 pieces if they are not allowed to play the same piece more than
once? 54 53 52
c) How many ways can the orchestra play 3 pieces if they must play a Haydn piece first, a modern piece second
and a Beethoven piece last?
30 15 9
d) How many ways can the orchestra play 3 pieces if they must play one Haydn piece, one Beethoven piece and
one modern piece in any order?
3! 30 15 9
7.1 The lottery game 2by2 is played as follows:
First, you pick two different red numbers between 1 and 26 (inclusive) and two different white numbers between 1 and 26
(inclusive). Order does not matter. After all tickets have been purchased, two red numbers and two white numbers are
selected. The closer you are to having picked the correct numbers, the more money you will win!
E.g. You pick Red: 2, 25; White 3,10
The winning numbers are Red: 7,25; White: 2,25.
You matched one red number and no white numbers.
(10 points)
a) What is the probability that you match both red numbers and both white numbers?
1
26 25 26 25
b) What is the probability that you match either both red numbers or both white numbers, but not both?
Match both correct reds and pick two losing whites, or pick two losing
reds and both correct whites.
2 24 24 2
2 2 2 2
26 25 26 25
c) What is the probability that you match exactly one red number and no white numbers?
Pick one of the two winning red numbers, then one of the losing red
numbers, then pick two losing white numbers.
2 24 24
1 1 2
26 25 26 25
8.3 Consider the procedure T given below.
procedure T (n: positive integer)
if n < 2 return 1
else
for i = 1 to n
for j = 1 to n
x = x + 1
return 3 3 3 3n n n nT T T T
Let ( )f n be the number of additions in the procedure for an input of n and note that ( )f n satisfies a recurrence relation
of the form dncbnfanf / .
a) Determine the values of a, b, c, and d. (4 points)
4a 3b 1c 2d
b) Apply The Master Theorem (given below) to T to determine its complexity. (1 point)
Master Theorem
Given dncbnfanf / , then
)(nf is
log log
b
d d
d d
a d
n if a b
n n if a b
n if a b
Since d
a b , the complexity is 2n
6.5 a) How many ways to rearrange the letters BOOKKEEPERS ? 11!
2! 2! 3! (2 points)
b) A bagel store has 500 different types of bagels. You want to buy 50,000 bagels.
i) How many different ways can you do this? 50, 499
499
(4 points)
ii) How many different ways can you do this if you need at least 10 of each type? 45, 499
499
(4 points)
8.5 Find # A B C given that # # # 10A B C , any two of A, B, C have 5 things in common, and there are exactly two things in all three sets. (5 points)
# # # # # # # #
= 10 + 10 + 10 5 5 5 2
= 17
A B C A B C A B A C B C A B C
6.4 (5.4) Prove that 1
1
n n k n
k k
(5 points)
Story: The left hand side is the number of ways to pick a committee of
size k from n students, then pick a president from the committee. The
right hand side the number of ways to pick the president first, then the
remaining 1k committee members from the remaining 1n students.
Definition:
! !
! ! 1 ! !
1 1 ! !
1 1 ! !1 ! 1 1 !
n n n k k
k k n k k n k
n n n n n
k k n kk n k
6.2 (5.2) An octopus is looking for socks to wear. In his dresser he has 20 red socks, 20 white socks and 20 blue
socks. Unfortunately, it is dark and he cannot distinguish between the different colors.
A human, having two feet, is happy with having two socks of the same color. An octopus, having 8 feet, is only
happy having 8 matching socks: 8 red, 8 white, or 8 blue.
a) How many socks must he pull out to guarantee he has eight that match? 22
It is possible to have 21 socks without 8 matching: 7 red, 7 white and 7
blue. Sock #22 must give 8 matching socks.
b) How many socks must he pull out to guarantee he has eight matching red socks or eight matching white
socks? 35
Worst case: All 20 blues, 7 reds and 7 whites = 34 socks.
Sock #35 will make a match.
c) How many socks must he pull out to guarantee he has eight matching red socks? 48
Worst case: 20 whites, 20 blues, 7 reds.
Sock #48 will match the 7 reds.
