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 15 × 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.
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:
The base case. If n ≤ ⌊α1⌋, check if v is one of the only at most ⌊α1⌋ integers in the array in a brute-force manner.
The inductive case. When n > ⌊ α1 ⌋, do the following: 1
Computer Science Tutoring
• 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(α1+log1 n).
• (c) (∗) [3 Marks] Prove that O(α1 +log 1 n) ⊆ O(α1 ·logn), for all 0 < α ≤ 1/2. Hint: The
1−α followingfactmaybeuseful: x ≤ln(1+x)≤xholdsforallx>0.
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 thereexistsapairofintegersa1 ∈Sanda2 ∈Ssuchthata1+a2 =k,wherea1 anda2 canbethe 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 Θ(nlogn) 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.
Submissions
You should lodge your submission for Assignment 1 via the LMS (i.e., Canvas). You must iden- tify yourself in your file. Poor-quality scans of solutions written or printed on paper will not be accepted. There are scanning facilities on campus, not to mention scanning apps for smartphones etc. Solutions generated directly on a computer are of course acceptable. Submit one file:
• A assignment1.pdf file, comprising your solutions to the questions in the assignment.
Programming Help, Add QQ: 749389476