Description
Problem 1
Using a loop invariant, prove that the following property holds for max:
∀ 0 ≤ i < n, list[i] ≤ max(list)
max(list)
1: i = 0
2: maxV alue = list[i]
3: while i < n do
4: if list[i] > maxV alue then
5: maxV alue = list[i]
6: end if
7: i = i + 1
8: end while
9: return maxV alue
Problem 2
Using mathematical induction, prove that a tree with n vertices has precisely n − 1 edges.
Problem 3
Prove using the definition of Θ that 6n
4 + 2n
3 + n + 12 ∈ Θ(n
4
).
Problem 4
Prove using the definition of Θ that any polynomial of degree k (that is, any function of the form
ak ∗ n
k + ak−1 ∗ n
k−1 + . . . + a1 ∗ n
1 + a0 ∗ n
0
) is a member of Θ(n
k
), where ak, ak−1, . . . , a1, and a0 are
nonnegative constants.
Problem 5
Do problem 2-12 from the text.
Problem 6
Do problem 2-20 from the text.
Problem 7
Do problem 2-13 from the text.
1
Problem 8
Suppose f1 ∈ Θ(g1) and f2 ∈ Θ(g2). Prove using the definition of Θ that f1/f2 ∈ Θ(g1/g2).
Problem 9
Suppose f ∈ O(g).
(a) Prove using the definition of O that f + g ∈ O(g).
(b) Prove using the definition of O that O(f + g) = O(g).
Problem 10
Prove or disprove: Big Oh defines an equivalence relation on the set of all functions f : N → R.
Problem 11
An adversary challenges you to a game. He gives you a board upon which is drawn a grid of squares
with 2n rows and 2n columns (So there are therefore (2n)
2
squares in the grid). He also gives you a
bag containing a large number of L-shaped pieces like the one shown below. The challenge is this: the
adversary will first select a single square on the grid and mark it as unusable. If you can then place
the L-shaped tiles in such a way that they cover the entire grid – with no overlaps, and leaving only
the unusable square uncovered – you win. Otherwise, the adversary wins. Prove using mathematical
induction that you can win the game for any n and any adversary-selected unusable square.
Figure 1: An L-shaped piece. Each square is the size of one grid location.
2