COMP2119 Introduction to data structures and algorithms
Introduction to data structures and algorithms
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP2119 Introduction to data structures and algorithms
Assignment 2 - Time complexity
Part A
Please submit your answers to the questions in part A only.
Please show steps of your work, not just the final answer.
Unless otherwise specified, assumes log n = log2 n.
Question 1 - True or False [24%]
Prove or disprove the following:
a) [6%] log2 n = O(log10 n).
b) [6%] 1n + 1 = Θ(1).
c) [6%]
√
n = Ω(log n).
d) [6%] If f(n) = O(n3) and g(n) = O(n2), then f(n)g(n) = O(n).
Question 2 - Proof by definition [26%]
Using the basic definition of (Θ, O, Ω)-notation in p.66, 70, and 71 of Chapter 2 slides, prove
the following:
a) [6%] 4n3 − log n + 6n + 3 = Ω(n3).
b) [10%] If f(n) = Θ(g(n)), then g(n) = Θ(f(n)).
c) [10%] If f(n) = n · g(n2) and g(n) = O(log n), then f(n) = O(n log n).
Question 3 - Maximum difference [20%]
Given an array A[1, . . . , n] of n integers, find array index i, j where j > i, such that A[j]−A[i]
is the maximum.
a) [10%] Present a brute-force algorithm that tries all possible i, j and report the maximum of
A[j]−A[i]. Analyze the time complexity of your algorithm.
b) [10%] Design a recursive algorithm to solve the problem and analyze the time complexity of
your algorithm.
Hint: Split the array into two halves, then the maximum difference will either be in one half
of the array, or across the whole array.
1
Question 4 - Majority element [30%]
Given an array of n integers (n ≥ 1), find the majority element (the element that occurs more
than bn2 c times) of the array. Assume that the majority element always exists in the array.
The brute force approach iterates each element in the array and counts the element’s occurrences
by iterating the array again. The total number of comparison operations equals O(n2).
A divide-and-conquer approach consists of the following recursive steps:
1) Find the majority element left in the left half of the array (line 5 in algorithm 4.1).
2) Find the majority element right in the right half of the array (line 6 in algorithm 4.1).
3) Compare left and right. If they agree, return left (line 7 - 9 in algorithm 4.1).
4) If they do not agree, individually count left ’s and right ’s occurrences in the array. Return
the one with more occurrences (line 10 - 16 in algorithm 4.1).
Let T (n) be the total number of comparison operations to find the majority element in an
array sized n.
a) [5%] Set up a recurrence equation for T (n).
b) [5%] Solve the recurrence equation, assume that n is a power of 2.
c) [10%] Prove that T (n) = Θ(n log n) (note that n may not be a power of 2).
Hint 1: to prove by MI with odd and even cases, we can assume n = 2, 3, . . . ,m − 1 is true
where 2 and 3 are the base cases, then prove that n = m = 2k and n = m = 2k−1 are correct.
Hint 2: Properties of log could be useful, e.g., log x + 1 = log x + log 2 = log 2x.
d) [10%] Design an algorithm to find the majority element in O(n) time and constant (O(1))
memory usage.
Hint 1: If we pick an arbitrary number (e.g., the first one in the array) as a candidate of
the majority element and count the number of majority (+1 to count) versus non-majority
element (-1 to count) from the start. At some point the count may become zero, but the true
majority element will always end up with positive count.
Hint 2: If we split an array into two parts, the majority element must be a majority element
in one of the sub-arrays.
2
Algorithm 4.1 FindMajority
1: function FindMajority(A, start, end) . Find majority in A[start . . . end]
2: if star = end then
3: return A[start]
4: end if
5: middle = b(start + end)/2c
6: left = FindMajority(A, start,middle)
7: right = FindMajority(A,middle + 1, end)
8: if left = right then
9: return left
10: end if
11: left count = CountOccurrence(A, start, end, left)
12: right count = CountOccurrence(A, start, end, right)
13: if left count > right count then
14: return left
15: else
16: return right
17: end if
18: end function
Algorithm 4.2 CountOccurrence
1: function CountOccurrence(A, start, end, e) . Count occurrence of e in A[start . . . end]
2: count = 0
3: for i = start to end do
4: if A[i] = e then
5: count = count + 1
6: end if
7: end for
8: return count
9: end function