Description
Exercise 6.1
In this question, assume that f is an increasing function satisfying the recurrence relation f(n) = af(n/b) +cnd
with a ≥ 1, b ∈ N \ {0, 1}, c, d ∈ R+. Our goal is to prove the Master Theorem 2.3.19 of the lecture.
i) Show that if a = b
d and n is a power of b, then f(n) = f(1)n
d + cnd
logb n.
(2 Marks)
ii) Show that if a = b
d
, then f(n) = O(n
d
log n).
(1 Mark)
iii) Show that if a ̸= b
d and n is a power of b, then
f(n) = C1n
d + C2n
logb a
, C1 =
b
d
c
b
d − a
, C2 = f(1) + b
d
c
a − b
d
.
(2 Marks)
iv) Show that if a < bd , then f(n) = O(n d ). (1 Mark) v) Show that if a > bd
, then f(n) = O(n
logb a
).
(1 Mark)
Exercise 6.2
A recursive algorithm for modular exponentiation is given in Example 3 of Section 4.4, page 312 of the textbook.
i) Set up a divide-and-conquer recurrence relation for the number of modular multiplications required to
compute a
n mod m, where a, m, n ∈ Z+.
(2 Marks)
ii) Construct a big-O estimate for the number of modular multiplications required to compute a
n mod m.
(1 Mark)
Exercise 6.3
Prove that in a bit string, the string 01 occurs at most one more time than the string 10.
(2 Marks)
Exercise 6.4
Consider the scheme for counting the rational numbers shown below and let
φ: Q+ → N \ {0}, φ
(
p
q
)
=
(p + q − 1)(p + q − 2)
2
+ p,
where Q+ := {a ∈ Q: a > 0}. The goal of this question is to prove that, in the scheme shown, traversing
successive diagonals from top to bottom, p/q is indeed the φ(p/q)th fraction encountered and that φ gives a
bijection Q+ → N \ {0}.
i) Write the traversal of the rational numbers as a recursively
defined sequence of pairs (pn, qn).
(1 Mark)
ii) Prove that for any (p, q) ∈ N \ {0} × N \ {0} there exists
an n ∈ N such that (p, q) = (pn, qn).
(2 Marks)
iii) Prove (by induction in n) that φ(pn/qn) = n.
(2 Marks)
iv) Deduce that φ is bijective.
(0.5 Marks)
v) Find the inverse of φ.
(2 Marks)
vi) How can φ be modified to give a bijective map Q → N?
(1 Mark)
vii) How can φ be modified to give a bijective map N×N → N?
(0.5 Marks)
1
1
1
2
1
3
1
4
1
5
1
6
· · ·
2
1
2
2
2
3
2
4
2
5
2
6
3
1
3
2
3
3
3
4
3
5
3
6
4
1
4
2
4
3
4
4
4
5
4
6
5
1
5
2
5
3
5
4
5
5
5
6
6
1
6
2
6
3
6
4
6
5
6
6
· · ·
· · ·
· · ·
· · ·
· · ·
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Exercise 6.5
Show that the countable union of countable sets is countable, i.e., if {Ai}∞
i=0 is an infinite family of sets, each
of which is countable, then ∪
i∈N Ai
is countable. Hint: Let aij denote the ith element of Aj . . .
(2 Marks)
Exercise 6.6
Let M, N be finite sets with card M = card N and M ⊂ N. Prove that M = N.
(2 Marks)
Exercise 6.7
Use the Pigeonhole Principle or Theorem 2.4.21 of the lecture to prove the following theorem:
Let M, N be finite sets with card M > card N and f : M → N. Then f is not injective.
(2 Marks)
