math vic
RiverFlowsInYou
Exam2.pdf
Exam #2: Solution
5.1 Define a sequence n
a as follows.
1 1a ,
2 1 1a a ,
3 1 2 1a a a
4 1 2 3 1a a a a
…
1 2 1 1 ...
n n a a a a
for 1n
a) Find the following: (0 points)
2 1 1 2a
3 1 1 2 4a
4 1 1 2 4 8a
5 1 1 2 4 8 16a
b) What is the general formula for n
a ? (3 points)
Note that 1
2 2a ,
2
3 2a ,
3
4 2a . The general formula is
1 2
n
n a
c) Use regular (not strong) mathematical induction to prove that your formula is correct. (7 points)
Proof:
1 1
1 1 2a
Assume 2
1 2
n
n a
, i.e.
2
1 2 2 1 ... 2
n
n a a a
Then 2 2 2 11 2 2 1 1 11 ... 2 2 2 2 2 n n n n
n n n n n a a a a a a a
5.2 (10 points) The Tribonacci sequence is defined by 1 2 3
0, 1, 1a a a , 1 2 3n n n n
a a a a
for 3n . Use
strong induction to prove that 2 n
n a for all n.
1
1 0 2a ,
2
2 1 2a ,
3
3 1 2a .
Assume 3
3 2
n
n a
,
2
2 2
n
n a
, and
2
2 2
n
n a
.
3 2 1 2 2 1 2 1 1 1 1
3 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2
n n n n n n n n n n n n
n n n n 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 index of the last even
number in the list. If there is no even number on the list, return 1 . Write your answer in pseudo-code or any well-
known procedural language like Python, Java, C++, …. (5 points)
You may assume that you have a function even? built in to your language. even? will return TRUE for even numbers and
FALSE for odd numbers.
E.g. For the list 1 2 3 4 5 , , , ,a a a a a = 5, 6, 7, 8, 9 your program should return 4 because
4 a is the last even number on the
list.
procedure Index_of_Last_Even ( 1 2 , ,..., :
n a a a integers)
index = -1
for i = 1 to n:
if i
a is even:
index = i
return index
8.3 (7.3) Recall the Fibonacci numbers we defined in class (here denoted by n
F ),
1
1F , 2
1F , 1 2n n n
F F F
for 2n
One could prove by induction that the following relationships hold for the Fibonacci numbers.
2 2
2 1 1
2 1 2
n n n
n n n n
F F F
F F F F
a) Use the given recursions to compute 3 4 ,F F and
5 F . Show your work. (2 points)
2 2 2 2 2 2
3 (2 1) 2 1 22 2 1 1 1 2F F F F F F
4 2 2 2 3 22 2 2 12 2 1 2 2 1 3F F F F F F F F
2 2 2 2 2 2
5 2 1 2 1 22 2 1 1 2 5F F F F F F
b) Write a recursive algorithm in pseudo-code or any well-known procedural language like Python, Java, C++,
&c to compute n
F based on the above recurrences. (8 points)
procdure Fib( n Z
)
if n < 3:
return 1
else if n is odd:
return Fib( 12 1 1n )2 + Fib( 1 2
1n )2
else:
return Fib( 2 n )(2Fib( 2 1
n )-Fib( 2 n ))
3.2/3.2 (2.5 points each)
a) Find C and k to show that 2 n
n is !O n
Note that
2 2 2 2 ... 2
! 1 2 3 4 ... 1
2 ! 2 2 3 ... 1
n n n
n n n
n n n
If 1 2n , then 2 2 ! n
n n , i.e.
If 3n ,then 2 2 ! n
n n
Pick k = 3 and C = 2.
b) True or False?: 3 n is 2nO
If true, find C and k to show this. If false, explain why.
False. 3 3
lim lim lim1.5 2 2
nn n
n n n n
c) True or False?: log 3n is log(2 )nO
If true, find C and k to show this. If false, explain why.
True. log 3 log(3)n n and log 2 log(2)n n
For every n, log(3) log(3)
log 3 log 3 log(2) log 3 log(2) log(2)
n n n n
log(3)
1, 1.585 log(2)
k C (We traditionally use base-2 logarithms here, but you can
use any base. Do you know why?)
d) True or False?: log 3 n is log 2
n O
If true, find C and k to show this. If false, explain why.
False.
log 3 log 3 lim lim lim1.585
log 2log 2
nn
n
n n n n
3.3 Give a big-Theta estimate for the number of additions in the following algorithm. Express your answer in
the form ( )f n where 2 3( ) 1, log( ), , log( ), , ,..., 2 , 3 ,..., !,..., ,...n n nf n n n n n n n n n (2.5 points each)
a)
procedure p(n)
i = 1
while (i < n):
i = i *2
return i
This algorithm is log n
(Write your answer in the parentheses above)
b)
procedure p(n)
i = 1
while (i < n):
j = 1
while (j < n):
j = j + 2
i = i + 1
return i
This algorithm is 2n (Write your answer in the parentheses above)
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:
1x x
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)
a 4 b 3 c 1 d 2
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 , we use the top line.
This algorithm is 2n (Write your answer in the parentheses above)
6.1 (5.1) Hexadecimal numbers are made using the sixteen digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. (2.5 points each)
a) How many 5 digit hexadecimal numbers that do not start with the digit 0 and do not end with the digit 0?
Pick the first number (15 choices), and then
pick the second number (16 choices), and then
pick the third number (16 choices), and then
pick the fourth number (16 choices), and then
pick the fifth number (15 choices)
15 16 16 16 15
b) How many 5 digit hexadecimal numbers start with a letter or end with a letter but not both?
Starts with letter and ends with non-letter or
starts with non-letter and ends with letter
3 3 6 15 10 10 15 6
c) How many 5 digit hexadecimal numbers start with a letter or end with a letter or both?
(Number that start with letter + number that end with letter)
- (number that start and end with letter)
4 4 3 6 16 16 6 6 16 6
d) How many 5 digit hexadecimal numbers where all digits are consecutive? E.g. 01234, 89ABC, …
Note: the numbers can’t “wrap-around”: EF0123 is not allowed.
Note that the starting digit determines the entire number. We can’t start
with C, D, E, or F because we wouldn’t be able to make a five digit number
without running out of digits.
The only possible starting numbers are 0, 1, 2, …, B
There are 12 5-digit numbers with consecutive digits.
6.2 Consider the first 250 Fibonacci numbers
1,1, 2, 3, 5,..., 7896325826131730509282738943634332893686268675876375
a) Fill in the blank with the largest possible integer that will make a true sentence. (2.5 points)
There are at least __ that have the same remainder when
divided by 11.
250 11 22.7 . We round up to 23.
There are at least 23 that have the same remainder when divide by 11.
b) Fill in the blank with the largest possible integer that will make a true sentence. (2.5 points)
There are at least 19 that have the same remainder when
divided by ___.
We need to find the largest solution to 250
18 n
8 9
250 250 18 13
18 n
n . Since n must be an integer, we pick 13n .
Note this actually guarantees 20 that have the same remainder.
6.3/5.3 A class has 21 students and is to be divided into indistinguishable groups. I.e, The two groups ABC and
DEF are the same as the two groups DEF and ABC
a) How many ways to divide the students into three groups of 7? (2.5 points)
Pick the first group of 7, and then
Pick the second group of 7, and then
Pick the last group of 7.
Notice that the order of the three groups does not matter.
21 14 7
7 7 7
3!
b) How many ways to divide the students into seven groups of 3? (2.5 points)
Similarly,
21 18 15 12 9 6 3
3 3 3 3 3 3 3
7!
6.5/8.3 (5.5/7.3) You have 12 bones that you want to distribute to three dogs.
a) How many ways to do this? (3 points)
12 *’s, 2 |’s
14
2
b) How many ways to do this if each dog gets at least 2 bones? (3 points)
First give each dog 2 bones. This leaves 6 bones left over.
6 *’s, 2 |’s
8
2
c) How many ways to do this if each dog gets at most 5 bones? (4 points)
Let
1 P be Dog 1 gets at most 5 bones,
2 P be Dog 2 gets at most 5 bones,
3 P be Dog 3 gets at most 5 bones,
Notice that 1
P is Dog 1 gets at least 6 bones.
Similarly for 2
P and 3
P .
1 2 3 1 2 3 1 2 1 3 2 3 1 2 3, , ( ) ( ) ( ) ( , ) ( , ) ( , ) ( , , )N P P P N N P N P N P N P P N P P N P P N P P P
By symmetry, 1 2 3 1 1 2 1 2 3, , 3 ( ) 3 ( , ) ( , , )N P P P N N P N P P N P P P
N is the answer to part a)
For 1N P : Give the first dog 6 bones. This leaves 6 bones to distribute
to the three dogs with no restrictions: 6 *’s, 2 |’s: 8
2
For 1 2,N P P : There is only one way to do this: 6 bones to dog 1, and 6
bones to dog 2.
1 2 3, ,N P P P is impossible as we don’t have enough bones.
1 2 3 14 8
, , 3 3 1 0 2 2
N P P P
7.1 An urn contains 7 red balls, 7 white balls and 7 blue balls.
5 balls are randomly picked from the urn without replacement.
a) What is the probability that all of the balls are red? (2 points)
7
5
21
5
b) What is the probability that all of the balls are the same color? (2 points)
All red or all white or all blue
7 7 7
5 5 5
21
5
c) What is the probability that none of the balls are blue? (3 points)
All red or all white
7 7
5 5
21
5
d) What is the probability that 3 balls are red and 2 balls are white? (3 points)
Pick 3 red balls, and then pick 2 white balls
7 7
3 2
21
5
6.4/5.4 Assuming 2 1n k , prove that 1
n n
k k
.
Hints: a) Work with 1
n
k
n
k
instead.
b) You did some similar calculations in Calculus 2 using the Ratio Test.
c) Subtracting k from both sides of the inequality might be useful.
Following the third hint: 1n k k
!
1 ! 1 ! ! !1 ! 1 1
! 1 ! 1 ! ! 1 1
! !
n n
k n k k n kk n n k k
nn k n k n k k
k n kk
1 1
1
n
n nk
n k k
k
,
