Algorithm Design COMP3027/3927 Tutorial questions The University of Sydney 2020 Semester 1 Tutorial 3 School of Computer Science
Pre-tutorial questions
Do you know the basic concepts of this week’s lecture content? These questions are only to test yourself. They will not be explicitly discussed in the tutorial, and no solutions will be given to them.
1. Divide and Conquer
(a) What is the general idea of a Divide-and-Conquer algorithm? Can you break up the general structure into three steps?
(b) Why are recurrences usually needed to analyse the running time of a Divide-and-Conquer algo- rithm?
2. Algorithms
(a) Describe the general idea of merge sort.
(b) What are the three main steps in the algorithm for counting inversions?
(c) In the merge step of the Closest-Pair algorithm,
i. Why do we only need to consider points that are within the δ-strip to the left of the dividing line and the δ-strip to the right?
ii. Suppose the points in these strips are s1, . . . , sk, in ascending order of their y-coordinate. Why is it that we only need to check pairs (si, sj ) for |i − j| ≤ 11?
3. Recurrences
(a) State the master method (write down all three cases). (b) Try to explain the master method using a recursion tree.
Tutorial
Problem 1
Solve the following recurrences:
1. T(n) = 2. T(n) = 3. T(n) = 4. T(n) = 5.T(n)= 6. T(n) = 7. T(n) =
4T(n/2) + n2
T(n/2) + 2n
16T(n/4) + n
2T(n/2)+nlogn
√
2T (n/2) + logn
3T(n/2) + n
3T(n/3) +
√
n
1
Problem 2
Consider the following algorithm.
Algorithm 1 Reverse
1: 2: 3: 4: 5: 6: 7: 8:
function reverse(A) if|A|=1then
return A else
Let B and C be the first and second half of A
return concatenate reverse(C) and reverse(B) end if
end function
Let T (n) be the running time of the algorithm on a instance of size n. Write down the recurrence relation for T (n) and solve it by unrolling it.
Problem 3
Theproductoftwon×nmatricesXandY isathirdn×nmatrixZ=XY,wherethe(i,j)entryofZis Zij = nk=1 Xik Ykj . Suppose that X and Y are divided into four n/2 × n/2 blocks each:
A B E F X = C D and Y = G H .
Using this block notation we can express the product of X and Y as follows AE+BG AF+BH
In this way, one multiplication of n × n matrices can be expressed in terms of 8 multiplications and 4 additions that involve n/2×n/2 matrices. Let T(n) be the time complexity of multiplying two n×n matrices using this recursive algorithm.
1. Derive the recurrence for T (n). (Assume adding two k × k matrices takes O(k2) time.) 2. Solve the recurrence by unrolling it.
Problem 4
Your friend is very excited because he has discovered a novel algorithm for sorting an array of n numbers. The algorithm makes three recursive calls on arrays of size 2n and spends only O(1) time per call.
XY= CE+DG CF+DH .
3
Algorithm 2 New-Sort
1: 2: 3: 4: 5: 6: 7: 8: 9:
procedure new-sort(A) if|A|<3then
sort A directly else
new-sort(A[0], . . . , A[ 2n ]) 3
new-sort(A[ n ], . . . , A[n]) 3
new-sort(A[0], . . . , A[ 2n ]) 3
end if
end procedure
2
Your friend thinks his breakthrough sorting algorithm is very fast but has no idea how to analyze its complexity or prove its correctness. Your task is to help Alex:
1. Find the time complexity of new-sort
2. Prove that the algorithm actually sorts the input array
Problem 5
[COMP3027 only] Given an array A holding n objects, we want to test whether there is a majority element; that is, we want to know whether there is an object that appears in more than n/2 positions of A.
Assume we can test equality of two objects in O(1) time, but we cannot use a dictionary indexed by the objects. Your task is to design an O(n log n) time algorithm for solving the majority problem.
1. Show that if x is a majority element in the array then x is a majority element in the first half of the array or the second half of the array
2. Show how to check in O(n) time if a candidate element x is indeed a majority element.
3. Put these observation together to design a divide an conquer algorithm whose running time obeys the
recurrence T (n) = 2T (n/2) + O(n)
4. Solve the recurrence by unrolling it.
Problem 6
Suppose we are given an array A with n distinct numbers. We say an index i is locally optimal if A[i] < A[i−1] and A[i] < A[i + 1] for 0 < i < n − 1, or A[i] < A[i + 1] for if i = 0, or A[i] < A[i − 1] for i = n − 1.
Design an algorithm for finding a locally optimal index using divide and conquer. Your algorithm should run in O(log n) time.
Problem 7
[Hard] Given two sorted lists of size m and n. Give an O(log(m + n)) time algorithm for finding the kth smallest element in the union of the two lists.
Problem 8
[COMP3927 only] Can you prove a lower bound on the approximation ratio of the greedy algorithm for Set Cover?
Problem 9
[COMP3927 only] Can you prove a lower bound on the approximation ratio of the “MST-approach” (doubling the MST) for the Travelling Salesman Problem?
3