COMP90038 Algorithms and Complexity Assignment 1 (2023 Semester 1)

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP90038 Algorithms and Complexity

Assignment 1 (2023 Semester 1)

Hint Solutions

Dictionary Search

Recall that given a set S of n integers sorted in ascending order and stored in an array A of length n, and a target search integer v, the goal of the Dictionary Search problem is to decide whether v ∈ S. In class, we introduced the binary search algorithm for solving this problem.

Problem 1.  [3 Marks] Now, let us consider a variant of the above binary search algorithm, called 1/5- search. Specifically, the 1/5-search algorithm works as follows:

The base case. If n ≤ 5, check if v is one of the only at most 5 integers in the array in a brute-force manner. The inductive case. When n > 5, do the following:

• compare v to the integer s stored in the position of 1/5 of the length of the array (for example, if the current array is of length 10, then we pick the integer stored at position × 10 = 2 in the array);

• if v = s, return yes and done;

• otherwise,

– if v < s, recursively solve the problem on the“left”part of the array before s;

– if v > s, recursively solve the problem on the“right”part of the array after s.

Prove that the running time complexity of 1/5-search algorithm is still bounded by O(log n).

Hint: You will need to define the cost recurrence and then solve it.

Solution:

Define C(n) as the worst-case cost of the 1/5-search algorithm. We have the following recurrence:

C(n) = n

C(n) = C(n) + 1

(n ≤ 5)

(n > 5)

Solving the recurrence, we have: C(n) ∈ O(log 5 n) = O(log n).

4

Problem 2. [6 Marks] Now, we further consider an extension of the above 1/5-search algorithm, which is called α-search algorithm for some arbitrary parameter 0 < α ≤ 1/2. As a result, the 1/5-search algorithm is a special case of the α-search with α = 1/5. However, note that, here, α should not be considered as a constant, and hence, α should appear in the time complexity.

To avoid confusion, although it is highly similar to that of the 1/5-search, we put the full description of the α-search algorithm below:

⌋, check if v is one of the only at most「⌋ integers in the array in a brute-force

The inductive case. When n >「⌋, do the following:


• compare v to the integer s stored in the position of α of the length of the array, i.e., the position at「αn⌋ .

• if v = s, return yes and done;

• otherwise,

– if v < s, recursively solve the problem on the“left”part of the array before s;

– if v > s, recursively solve the problem on the“right”part of the array after s.

Answer the follow questions.

• (a) [1 Mark] What is the running time complexity of the base case in the α-search algorithm.

• (b) [2 Marks] Prove that the running time complexity of the α-search algorithm is bounded by O( + log 1 n).

1 −α

• (c) (*) [3 Marks] Prove that O( + log n) ⊆ O( · log n), for all 0 < α ≤ 1/2. Hint: The following fact may be useful: 1北 ≤ ln(1 + x) ≤ x holds for all x > 0.


Solution:

(a) O( )

(b) In the inductive case, the algorithm always recurs into a problem on an array of length no more than (1 − α) portion of the current array. Thus, we have the following recurrence:

(n ≤「⌋)

(n >「 α ⌋)

(1)

(2)

(3)

Solving the recurrence, we have: C(n) = O(log n + ).

Observe that

ln n ln n

By the fact that ln(1 + x) ≤ x holds for all x > 0 and 0 < α ≤ 1/2, we have:

ln n ln n ln n 1

Thus, we have:

1 −α 1 −α




(solution continued)

On the other hand, by the fact that ln(1 + x) ≥ holds for all x > 0, substituting to Equation (1), we have:

log n = = ≤ = · ln n (4)

Therefore, combining Equations (3) and (4), for all 0 < α ≤ 1/2, we have:

O( + log n) ⊆ O(log n) ⊆ O( · log n) .

Two-Sum

Problem 3. [6 Marks] Consider a set S of n integers sorted in ascending order and stored in an array A of length n; given a target sum value k, the goal of the Two-Sum problem is to decide if there exists a pair of integers a1  ∈ S and a2  ∈ S such that a1 + a2  = k, where a1 and a2 can be the same integer, i.e., a1  = a2 . Answer the following questions.

• (a) [1 Mark] Design a brute-force algorithm to solve the above Two-Sum problem, and analyse the time complexity of your algorithm.

• (b) [2 Marks] Design an algorithm that can solve the Two-Sum problem in Θ(nlog n) time.  You will need to prove the time complexity of your algorithm.

• (c) (*) [3 Marks] Design an algorithm that can solve the Two-Sum problem in Θ(n) time. You will need to prove the correctness and the time complexity of your algorithm.


Solution:

(a) Enumerate all possible pairs of integers in S and check if any of them sums up to k.  The time complexity is O(n2 ). A pseudocode implementation is given below:

function TWOSUM(A[0..n − 1], k)

for i ← 0 to n − 1 do

for j ← 0 to n − 1 do

if A[i] + A[j] = k then

return TRUE

return FALSE

(b) For each integer a ∈ S, perform a binary search on A to check if k − a exists in S. If so, return “yes”.  Otherwise, if no such pair is found, return“no”.  Each binary search takes O(log n) time. Therefore, the overall running time cost is bounded by O(nlog n).

function TWOSUM(A[0..n − 1], k)

for i ← 0 to n − 1 do

if BINARYSEARCH(A[0..n − 1], k − A[i]) ≥ 0 THEN

RETURN TRUE

RETURN FALSE




(solution continued)

(c) Maintain two pointers i and j . Initially, i = 0 and j = n − 1; that means, i points to the start of A and j to the end of A. Perform the following steps until i > j:

• if A[i] + A[j] = k, return yes;

• if A[i] + A[j] > k, set j ← j − 1;

• if A[i] + A[j] < k, set i ← i + 1;

If the algorithm does not stop in above loop, return no.

function CHECKSUM(A[0..n − 1], k)

i ← 0

j ← n − 1

while i ≤ j do

if A[i] + A[j] = k then

return TRUE

else

if A[i] + A[j] < k then

i ← i + 1

else

j ← j − 1

return FALSE

2023-06-05