Description
Exercise 5.1 Binary Insertion Sort
The binary insertion sort is a variation of the insertion sort that uses a binary search technique rather than a
linear search technique to insert the i element in the correct place among the previously sorted elements.
i) Express the binary insertion sort in pseudocode.
(2 Marks)
ii) Compare the number of comparisons of elements used by the insertion sort and the binary insertion sort
when sorting the list 7, 4, 3, 8, 1, 5, 4, 2.
(2 Marks)
iii) Show that the insertion sort uses O(n
2
) comparisons of elements.
(2 Marks)
iv) Find the complexity of the binary insertion sort. Is it significantly faster?
(2 Marks)
Exercise 5.2
Order the letters M,I,C,H,I,G,A,N alphabetically using
i) merge sort,
(2 Marks)
ii) insertion sort,
(2 Marks)
iii) bubble sort
(2 Marks)
algorithms. (Note that it does not matter that the letter “I” is repeated.) For each algorithm, show what the
arrangement is after each pass/merge. How many comparisons of letters are made using each algorithm?
Exercise 5.3 Application to Feng Shui
The iterated integer sum of n ∈ N \ {0} is calculated as follows: The decimal digits of n are added to yield a
sum n1. If n1 is greater than 9, the integers of n1 are added. This process is repeated until a number between 0
and 9 is obtained. For example, the iterated integer sum of 54469 is calculated as follows: 5 + 4 + 4 + 6 + 9 = 28,
2 + 8 = 10, 1 + 0 = 1.
i) Give the worst-case number of additions that need to be performed to calculate the iterated integer sum
of n ∈ N \ {0} in this way.
(2 Marks)
ii) How is the iterated integer sum of a number n related to n mod 9? Prove your assertion!
(3 Marks)
iii) Generalize (ii) to integers represented in arbitrary base b.
(2 Marks)
(The iterated integer sum plays a role in Feng Shui; see, for example,
http://fengshui.about.com/od/fengshuicures/qt/kua number.htm.)
(2+3+2 Marks)
Exercise 5.4 Modular Exponentiation
Find 41021042 mod 2014 using the algorithm for modular exponentiation given in the lecture. Show all the steps
in the algorithm.
(2 Marks)
Exercise 5.5 Stein’s Algorithm for the GCD in base 2
Let a > b be two natural numbers.
i) How can multiplication or division by 2 be efficiently performed in base 2?
(1 Mark)
ii) If a and b are both even, express gcd(a, b) in terms of gcd( a
2
,
b
2
).
(1 Mark)
iii) If a and b are both odd, express gcd(a − b, b) in terms of gcd(a, b).
(1 Mark)
iv) Work out an algorithm to calculate the gcd of two natural numbers in base 2.
(2 Marks)
(According to D. Knuth, this algorithm, called Stein’s algorithm, was probably known in 1st-century China.)
Exercise 5.6
Solve the following recurrence relations:
an = an−1 + 6an−2, n ≥ 2, a0 = 3, a1 = 6,
an+2 = −4an+1 + 5an, n ≥ 0, a0 = 2, a1 = 8.
(4 Marks)
Exercise 5.7
Prove Theorem 2.3.8 of the lecture, which states that all solution to a linear homogeneous recurrence relation
of degree two are of the form
an = α1 · r
n
0 + α2 · nrn
0
, α1, α2 ∈ R, n ∈ N.
if there is only a single characteristic root r0.
(2 Marks)
Exercise 5.8
Find all solutions of the following recurrence relations:
an = 5an−1 − 6an−2 + 42 · 4
n
,
an = −5an−1 − 6an−2 + 2n + 3n,
an = 7an−1 − 16an−2 + 12an−3 + n4
n
.
(6 Marks)
