Transcript Slide - UF CISE

Disclaimer: You should try to solve all problems by yourself.
The solutions provided in these slides should serve only as
hints and not as a study guide.
Problem 1: f(x) is O ((x+2) log(x2 + 1) ) .
For sufficiently large
x, (x+2) < 4x (4 is chosen arbitrarily, i.e., it can be 5 or 6.) and x2+1
< x4. That is, for sufficiently large x, f(x) < K ( 4x log x4 ) = 16K (x
log x), for some constant K. That is, f(x) = O(x log x).
Problem 2: Compute f( Ai ) for i from 1 to m.
You need to come
up with an algorithm that can determine if the list { f (A1), f(A2), …
f(Am) } contains duplicated elements. There is a O(m2) algorithm
(the one we worked out in class).
Problem 3: 5! Because we can fix one person’s position and
permute the other 5 people.
Fix
Permute
Problem 4: 3100
Problem 5: Use induction.
2K+1 +1
(K-1)2K +1 + (K+1) 2K = 2K 2K +1 = K
Problem 6: There are 2100 subsets.
There is 1 subset with
zero element, 100 subsets with one element and (100*99)/2 =
50*99 = 4950 subsets with two elements: 2100 – 101 – 4950 = 2100
- 5051
Problem 7:
(a) 210 = 1024.
(b) C(10, 2)=45.
(c) C(10, 0) + C(10, 1) + C(10, 2) + C(10, 3) = 1 + 10 +45 + 120.
(d) There are exactly 5 heads and 5 tails. The number of C(10, 5).
Problem 8: count the numbers of committees with 4, 5, 6 women
(or 2, 1, 0 men)
(2 men) C(10, 2)xC(15, 4)
(1 man) C(10, 1)xC(15, 5)
(0 man) C(15, 6).
Add these numbers together and that’s the answer.
Problem 9: There are 8 pairs of 01 and two free 1s.
- - 01 - - 01 - - 01 - - 01 - - 01 - - 01 - - 01 - - 01 - There are 9 ways to put the two free 1s next to each other ( 11 ) and
there are C(9, 2) =36 ways to put these two free 1s so that they are
NOT next to each other. Total is 36+9 = 45.
Problem10: Each computer can connect to either 1, 2, 3, 4, or 5
computers. Use pigeonhole principle, there are five boxes and six
objects: a computer is put into box K ( K=1, 2, 3, 4, 5) if it is connected
to K other computers. The result follows.
Problem11: The hint (see the textbook page 354) is to use the
result that for a group of 10 people, there are either three mutual
friends or four mutual enemies, and there are either three mutual
enemies or four mutual friends.
Now we are given 20 people. Take one person A from the group. A
either (1) has at least 10 friends or (2) at least 10 enemies.
Case (1): we can find 4 mutual enemies among these 10 friends of A (we are
done) or we can find 3 mutual friends among these 10 friends of A and this
gives us 4 mutual friends (adding A).
Case (2): Similarly, among the 10 enemies of A, we can find four mutual
friends (we are done) or we can find 3 mutual enemies and this gives us 4
mutual enemies (adding A).
Problem12: Clearly, you can apply the pigeonhole principle to
solve the problem. We will define 50 boxes
B500, B501, …., B549
For each street address x, we can put x into box Ba, where a =
floor(x/2). There are 50 boxes and 51 objects. One box must have
more than 1 street address
Problem15: There are n variables.
Therefore, in every truth
table, we have 2n True/False entries to fill. In this way, the
number is the same as the number of outcomes of flipping a coin
2n times, which is 2^(2n).
Problem 13:
The solution is quite simple. Let’s do a simple
example (the general case is straightforward). Take n= 6.
A
-3/6 = -1/2
B
-2/6
C
-1/6
D
0
1/6
u, v
F
E
2/6
3/6 = 1/2
Given any irrational number x, and j some positive integer not exceeding n, the
difference between jx and the nearest integer to jx must fall into the above six
intervals (why?) If this difference falls into interval C or D, we are done (because
its absolute value will be less than 1/n=1/6). So suppose the difference never
lands on interval C or D.
For each positive integer h not exceeding n, we place h into the interval A, B, E,
F depending on the difference between hx and the nearest integer to hx. There
are 4 intervals and we have 6 numbers. By the pigeonhole principle, one interval
will have at least two numbers, say a and b with a > b: (with A, B integers and u,
v the differences belonging to the same interval | u- v | < 1/6.)
ax = A + u, bx = B + v
(a-b) x = (A-B) + u-v
a-b is an integer not exceeding 6 and the
absolute value of (a-b)x and its nearest integer is < 1/6 !
Problem 14
From the problem statement, we are almost certain that the problem can be
solved using generalized pigeonhole principle. We have 101 objects (heights)
and let’s have 10 boxes, B1, B2 … B10. And we need to define how to put the
101 objects into these 10 boxes. If we can do this, by the pigeonhole principle,
one box will have at least 11 objects and this will solve the problem.
Let’s suppose that we can’t find 11 people standing in the line with decreasing
height (this will allow us to use 10 boxes to put all objects in). First, the value of
each box is initialized to minus infinity: for each object (the height of the person
in line) x, we go from the first box to the last one. If the value of Box N is smaller
than x, we will put x into Box N and increase the value of the Box N to x.
Take a few seconds to process the definition above. Notice that each box
contains an increasing sequence of heights and if one box contains at least 11
objects (heights), then we are done. What is left to show is that all objects an be
put into these 10 boxes (we need to use the assumption that there is no 11
decreasing heights).
Now, if an x got put into Box N ( 1 <= N <=10), there is a sequence of N
decreasing heights (make sure you see this). Because of the assumption, we
know that N can never be more than 10, hence all objects can be put into one of
the 10 boxes.
Problem 16: The tree could be quite tedious to draw. However,
Example 20 on page 343 (5.1) is very similar to this problem and
make sure that you know this example well.
Problem17: The total number of arrangements is 4!=24.
The number of arrangements with a followed immediately by b is 3!.
So the answer is 24-6 = 18.
Problem19: If Sum(n) is the algorithm that find the sum of first n
positive integers. Then the recursive algorithm is
Procedure Sum ( n )
if n =1 Sum(1) =1
else Sum(n) = n + Sum(n-1).
Remember that you need to define the base case (n=1) and the
recursion (else statement).
Problem 20: Let L be a list of integers and L(n) is the nth integer in
the list L.
Procedure Max ( L )
if length(L) = 1 Max (L) = L(1)
else
if L(n) > Max( L( 1:n-1) ) Max(L) = L(n)
else Max(L) = Max (L(1:n-1))
In the above, L(1:n-1) is the sublist of L that contains the first n-1 elements in L.
Problem 21: The string has equal number of 0s and 1s.
The
string has 2n bits for some positive integer n: the first n bits are 0s
followed by n bits of 1s.
Problem 22: . All integers except 3 and 1.
Strong induction will
go like this. Basis case : 4 = 2+2 and 5=5.
Suppose any integer 3 < n < = K can be written as a sum of 2s and
5s. For K+1, we know that K+1 = (K-1) + 2 and K-1 can be written as
a sum of 2s and 5s. It follows that K+1 can be written as a sum of 2s
and 5s as well.
Problem 23: The strong induction will go like this:
The base case: 1 = 20 and 2 = 21.
Now suppose the result is true for all integers less than or equal to
K. We need to show that the result is also true for K+1.
If K+1 is odd: then K is even and by induction hypothesis it can be
written as a sum of powers of 2 (without 20 term). Then we can writhe
K+1 as a sum of powers of 2 by adding 20 to the sum for K.
If K+1 is even: then (K+1)/2 is an integer so according to the
induction hypothesis, it is a sum of powers of 2. From this, we can that
K+1 is also a sum of powers of 2 by increasing the powers in the sum
for (K+1)/2 by 1.
Problem 24: You should be able to figure out what’s wrong with
this proof. Note that the statement of this theorem is outrageously
incorrect.
Problem 25: This is a simple induction.
Check the basis step
and notice that
n(n+1)(n+2)(n+3)/4 + (n+1)(n+2)(n+3) = (n+1)(n+2)(n+3)(n+4)/4
This equality will complete the inductive step.
Problem 26: Check the basis step when n=1,
1 + h < = (1+h)n=1
The inductive step assumes that the above inequality is valid for all
integer 1 <= n < = K (note that because h > -1, 1 + h > 0 ).
1 + K h < = (1+ h)K
From this, we have (because 1 + h > 0 )
(1 + h) (1 + K h) < = (1 + h)k+1
The left hand side is
1 + (K+1) h + K h2
which is greater than 1+ (K+1)h because K h2 is positive.
Putting these together, we have
1 + (K+1) h <= (1 + h)k+1
Problem 27: You should be able to solve this problem without
difficulty.
Problem 28: You can ignore this problem.
Problem 29:
Stratightforward.
Problem 30: The main idea is to show that ( n! )2 >= n n.
If we can show this, then the result follows easily by taking the log both
sides 2 (log n! ) > = n log n, i.e. n log n is O( log n!).
Notice that
( n ! ) 2 = n x (n-1) x (n-2) x…x 2 x 1 x
1x2x
3
x … x n-1 x n
and each vertical pair has product >= n ( 2 (n-1) >=n and 3(n-2) > n,
etc.) From this, we have that
(n!)2>nn
Problem 32: The previous problem shows that log n! is
Ω(n log n).
To show that log n! is θ(n log n), you need to show that log n! is also
O(n log n). This is quite straightforward and I will leave it to you.
Problems 33 and 34.
Make sure that you know how to do
these problems. We’ve gone over several of them in class before.