CSC 201-Discrete Math for Computer
Scientists
Shai Simonson
Assignment 2
Due: midnight, Monday, October 23
From the text: Section 3.2:
3, 4, 5, 8, 9, 10, 30. Section
3.3: 13, 14, 15, 18.
- Prove that f(x) = x^{3}
1000x^{2} + x 1 is Ω(x^{3}) and O(x^{3}).
- Prove that 1^{k} + 2^{k}
+ 3^{k} +
+ n^{k} is Ω(n^{k+1})
and O(n^{k+1}),
for any fixed k>0. Hint: The Big-O
part of this is straightforward using c = 1, and the
Big-Omega part can be done by using c = 1/(k+
1), and comparing the sum to the area under the curve x^{k},
from 0 to n.
- Order the following functions in order of
their growth rate. If f(x) is O(g(x)),
but g(x) is not O(f(x)),
then put f(x) above g(x).
If they are each big-O of each other, then place them on
the same level. Beware! Some of these are easy to
compare and some are not. This is a big problem and
worth a number of points - make sure to justify every step.
x^{2} + x^{3} 3^{x}
x!
x/lgx x^{2}+ 2^{x}
xlog_{2}x 2^{xlgx}
logx^{2} 2^{x+}^{1}^{ }
lgx!
lgx
lnx 2^{x } x(1+2+
+ x)
loglogx
2^{2x}
x^{x} log^{2}x
- Compute the sum of the infinite series
below.
- 1 + 1/4 + 1/16 + 1/64 +
- 1 + 2/4 + 3/16 + 4/64 +
- Telescoping Series.
- Using the identity 1/((k)(k+1))
= 1/k 1/(k+1), find
the value of the infinite sum 1/(1*2) + 1/(2*3) + 1/(3*4) +
.
- The nth triangle number is
defined to be the sum of the first n positive
integers. What is the value of the infinite sum of the
reciprocals of the triangle numbers.
- Whats wrong with the following proofs by
induction?
- Every binary string contains identical
symbols (either all 0's or all 1's). The proof is by
induction on the size of the string. For n=0 all
binary strings are empty and therefore identical. Let X
= b_{n}b_{n-1}
b_{1}b_{0}
be an arbitrary binary string of length n+1. Let Y
= b_{n}b_{n-1}
b_{1} and Z
= b_{n-1}
b_{1}b_{0}. Since
both Y and Z are strings of length less than
n+1, by induction each contains identical symbols.
Since the two strings overlap, X must also contain
identical symbols.
- Any amount of change greater than or
equal to twenty can be gotten with a combination of five
cent and seven cent coins. The proof is by induction on the
amount of change. For twenty cents use four five-cent coins.
Let n > 20 be the amount of change. Assume that
n = 7x + 5y for some non-negative
integers x and y. For any n >
20, either x > 1, or y > 3. If x
> 1, then since 3(5) 2(7) = 1, n+1 = 5(y+3)+7(x2).
That
is, I add 3 five cent coins and subtract 2 seven cent
coins. And, I can do this because x is at
least 2. If y > 3, then since 3(7) 4(5) =
1, n+1 = 7(x+3)+5(y4). That is, I add
3 seven cent coins and subtract 4 five cent coins, which is
doable because y is at least 4. In either
case, we showed that n+1 = 7u + 5v
where u and v are non-negative integers.
- Prove by induction on n that:
a. The nth Fibonacci
number equals (1/√5)[(1/2 + √5/2)^{n} (1/2 √5/2)^{n}
], where F_{0} = 0 and F_{1}_{
}= 1 and F_{n} = F_{n}_{-1}
+ F_{n}_{-2}
b. The sum of the geometric
series 1 + a + a^{2} +
+ a^{n}
equals (1a^{n+}^{1})/(1a),
where a does not equal one.
c. 21 divides 4^{n+1}
+ 5 ^{2n-1}
- Counting each arithmetic calculation or
comparison, extraction or exchange of a card as one operation,
what is the worst-case order of growth of an algorithm that
sorts numbered cards in the following way?
- Find the largest valued card in the
deck by shuffling through one card at a time extracting a
card if it is the largest one seen so far, and swapping the
previously largest card back into the deck. When the largest
has been found, place this card face down in a new pile and
repeat the previous process until no cards in the original
pile are left. Explain your answer.
- This time we assume that the largest
number on any of the n cards is n^{2}.
We sort the cards by placing a set of n^{2}
plates numbered from 1 to n^{2} on a table.
Then one by one, place each card on top of the numbered
plate equal to it on the desk. You can assume that it takes
a single step to find a card's pile - as though the card is
the index to an array, and the slot in the array is the
pile. The sorted list can be extracted by looking
through the piles of the n^{2 }plates in
order.
- The method in part (b)can be improved
to work in linear time. Explain how. Hint: This is not easy.
Use only n plates, numbered 0 through n - 1
and turn each number into a pair of numbers, each with a
value between 0 and n-1.
back
shai@stonehill.edu
http://www.stonehill.edu/compsci/shai.htm