Algorithm Design COMP3027/3927 Tutorial questions The University of Sydney 2019 Semester 1 Tutorial 4 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 recursions usually needed to analyse the running time of a Divide-and-Conquer algorithm?
2. Algorithms
(a) Describe the general idea of merge sort.
(b) What are the three main steps in the algorithm for counting inversions?
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) =
Problem 2
Consider the
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
following algorithm.
1
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 Alex 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
Alex 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:
2
1. Find the time complexity of new-sort
2. Prove that the algorithm actually sorts the input array
Problem 5
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
[Advanced] Suppose we are given a set S of n elemnts. Each element has a value and a weight. For an element x ∈ S, let
• S
For any subset R ⊆ S, define its weight w(R) to be the sum of the weights of elements in R. The weighted median of S is any element x such that w(S
Give an algorithm that computes the weighted median of S in O(n) time. Your input consists of two unsorted arrays V[1…n] and W[1…n] where V[i] and W[i] are the values and weights of element i, respec- tively. You may assume that the values are distinct and all weights are positive.
3