COMP4500/7500 Advanced Algorithms & Data Structures Tutorial Exercises 2 (2014/2)∗
School of Information Technology and Electrical Engineering, University of Queensland
August 4, 2014
This material aims to familiarise you with asymptotic notation and develop your skill at manipulating formulae involving asymptotic notation. A good treatment of the basics of asymptotic notation may be found in CLRS 3.1 or CLR 2.1. It also aims to familiarise you with
• divide-and-conquer algorithms;
• the use of recurrence equations to represent the running time of recursive algorithms; and • develop your skill at solving recurrences.
Good treatments of divide-and-conquer and recurrences may be found in Chapters 2 and 4 of CLRS, respectively (1 and 4 of CLR).
1. (See CLRS Exercise 1.2-2, p14 [3rd], p13 [2nd], CLR Exercise 1.4-1, p17 [1st])
Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, assume insertion sort runs in 10n2 steps, while merge sort runs in 100n lg n steps, where lg n stands for log2 n. For which values of n does insertion sort beat merge sort? You will need to use a bit of algebra, but may then use trial and error if you wish.
How might one write a sorting algorithm which has the advantages of insertion sort for small inputs and the advantages of merge sort for larger inputs? (For an extension, see CLRS Problem 2-1 p39 [3rd], p37 [2nd], CLR Problem 1-2, p17 [1st]).
2. (CLRS Exercise 3.1-1, p52 [3rd], p50 [2nd], CLR Exercise 2.1-1, p31 [1st]) A function h is asymptotically nonnegative if there exists an nh such that
(∀n•n≥nh ⇒h(n)≥0)
Let f and g be asymptotically nonnegative functions. Using the definition of Θ-notation, prove that the function max(f(n),g(n)) ∈ Θ(f(n) + g(n)), where for each value of n the function max(f(n),g(n)) returns the maximum of f(n) and g(n). As abbreviations, define functions M and S so that, for all n
M (n) = max(f (n), g(n)) S(n) = f(n) + g(n)
3. (CLRS Exercise 3.1-3, p53 [3rd], p50 [2nd], CLR Exercise 2.1-3, p31 [1st])
Explain why the statement, “The running time of algorithm A is at least O(n2)”, is content-free.
4. (CLRS Exercise 3.1-4, p53 [3rd], p50 [2nd], CLR Exercise 2.1-4, p31 [1st]) Is 2n+1 ∈ O(2n)? Is 22n ∈ O(2n)?
5. Rank the following functions by order of growth; that is, find an arrangement g1 , g2 , . . . , g25 of the functions satisfying g1 ∈ Ω(g2), g2 ∈ Ω(g3), …, g24 ∈ Ω(g25). Partition your list into equivalence classes such that gi and gj are in the same class if and only if gi ∈ Θ(gj).
(3)n (√2)lgn lg∗ n n2 (lgn)! 2
lg n n3 (lgn)2 lg(n!) 22n n 1
lglgn n·2n nlglgn lnn 2n 2lgn (lgn)lgn 4lgn (n+1)! √lgn
n! 22lgn n nlgn 1
Try to rank as many of the above functions as you can. You may need to refer to CLRS 3.2 or CLR 2.2 for the
definition of lg∗ n and help. ∗Copyright ⃝c reserved August 4, 2014
√
1
COMP4500/7500 (2014) Tutorial Exercises 2 (August 4, 2014) 2
6. (CLRS Exercise 3.1-2, p52 [3rd], p50 [2nd], CLR Exercise 2.1-2, p31 [1st])
Show that for any real constants a and b, where b > 0,
(n + a)b ∈ Θ(nb).
7. (Programming problem)
Algorithms for both insertion sort and merge sort have been studied. You may use any implementations that you wish.
Perform an empirical analysis of these algorithms by running them in order to determine their execution time for different inputs (e.g., the best-case and worst-case inputs for insertion sort) and different sizes of input (eg, 1000, 2000, 4000). Compare your results with the results of the theoretical analysis of these algorithms. (You may find it useful to graph your experimental results.)
You may also like to experiment with profiling the execution of the algorithms.
8. A local minimum of an array segment A[lo..hi] is an element A[k] satisfying,
A[k − 1] ≥ A[k] ≤ A[k + 1]
for lo ≤ k ≤ hi. We assume that lo ≤ hi, and that the indices of the whole array, A, range from (at least) lo − 1
through to hi + 1. This allows us to also assume that
A[lo − 1] ≥ A[lo] ∧ A[hi] ≤ A[hi + 1]. (1)
This condition guarantees that a local minimum must exist; without (1) the array may be either strictly increasing or strictly decreasing, in which case there is no local minimum.
(a) DesignanalgorithmforfindingalocalminimumofthearraysegmentA[lo..hi]whichissubstantiallyfaster than the obvious O(n) one in the worst case. Hint: use a divide-and-conquer approach similar to binary search.
(b) Give an analysis of your algorithm to determine the number of comparisons of array elements required to find a local minimum of an array of size n.
9. (See CLRS Exercise 4.4-6 p93 [3rd], 4.2-2 p72 [2nd], CLR Exercise 4.2-2, p60 [1st]) Argue that the solution to the recurrence
T (n) = T ( n ) + T ( 2n ) + cn 33
where c is a constant, is Ω(n lg n) by appealing to a recursion tree. That is, we would like a lower bound on the solution to the recurrence.
10. (See CLRS Problem 4-1, p107 [3rd], p85 [2nd], CLR Problem 4-1, p72 [1st])
Give asymptotic upper and lower bounds for T (n) in each of the following recurrences. Assume that T (n) is constant for n ≤ 1. Make your bounds as tight as possible, and justify your answers. Hint: use the master theorem.
(a) T(n)=2T(n)+n3. 2
(b) T(n)=T(9n)+n. 10
(c) T(n)=16T(n)+n2. 4
(d) T(n)=7T(n)+n2. 3
(e) T(n)=7T(n)+n2. 2
11. (See CLRS Problem 4-1, p107 [3rd], p85 [2nd], CLR Problem 4-1, p72 [1st])
Give asymptotic upper and lower bounds for T (n) in each of the following recurrences. Assume that T (n) is constant for n ≤ 2. Make your bounds as tight as possible, and justify your answers. Hint: use iteration.
COMP4500/7500 (2014) Tutorial Exercises 2 (August 4, 2014) 3
(a) T(n)=T(n−1)+n. √
(b) T(n)=T( n)+1.
12. Solve (find an asymptotic upper bound for) the recurrence
T (n) = T (n − a) + T (a) + n
where a ≥ 1 is a constant, by using iteration to generate a guess and then using substitution to verify it.