代写3121-21T2编程、代做C/C++，Java程序设计

日期：2021-07-16 11:54

3121-21T2-HW1-SOLUTION

1. Question 1

You are given an array A of n distinct positive integers.

(1) Design an algorithm which decides in time O(n2 log n) (in the worst case) if there exist four

distinct pairs of integers {m, s} and {k, p} in A such that m2 + s = k + p2 (10 points)

(2) Solve the same problem but with an algorithm which runs in the expected time of O(n2).

(10 points)

Solution for Question 1(a):

(1) Square all numbers in A, storing in an array S.

(2) Find all combinations of sum ai + sj, i, j ∈ [0, n? 1], i 6= j storing in an array C with i, j.

(3) Sort C based on sum using merge sort, guarantee worst case O(nlogn).

(4) Loop through C and find two adjacent elements with the same sum and distinct is, js values,

and these 4 integers are the indexes of answers.

(5) Time complexity = O(n) +O(n2) +O(n2logn) = O(n2logn).

Solution for Question 1(b):

(1) Square all numbers in A, storing in an array S.

(2) Find all combinations of sum ai + sj, i, j ∈ [0, n ? 1], i 6= j storing in a hash table M ,

M [sum] = [(A[i], A[j]), ...].

(3) Loop through M and in each slot find if there is more than one pair of (A[i], A[j]) that

produces the same value of (A[i])2 + A[j].

(4) Time complexity = O(n) +O(n2) +O(n2) = O(n2).

2. Question 2

You are given a set of n fractions of the form xi/yi (1 ≤ i ≤ n), where xi and yi are positive inte-

gers. Unfortunately, all values yi are incorrect; they are all of the form yi = ci + E where numbers

ci ≥ 1 are the correct values and E is a positive integer (equal for all yi). Fortunately, you are also

given a number S which is equal to the correct sum S =

∑n

i=1 xi/ci. Design an algorithm which

finds all the correct values of fractions xi/ci and which runs in time O(n log min{yi : 1 ≤ i ≤ n}).

(20 points)

Solution for Question 2: In order to find all the correct values of the fractions, we need to find

the value of E that all denominators were increased by. Since for all i, yi > ci > 0 and E = yi ? ci

is positive, we know that

0 < E < min{yi : 1 ≤ i ≤ n}

Then, define

P (k) =

n∑

i=1

xi

yi ? k =

n∑

i=1

xi

ci + E ? k

which is strictly increasing for 0 < k < min{yi : 1 ≤ i ≤ n}, with P (k) = S precisely when k = E.

This means that we can binary search over this range using P (k) to find E in O(log min{yi : 1 ≤

1

2 3121-21T2-HW1-SOLUTION

i ≤ n}) steps. Each step involves evaluating P once, which takes O(n) time. As such, the overall

runtime of our algorithm is O(n log min{yi : 1 ≤ i ≤ n})

3. Question 3

You are given an array A consisting of n positive integers, not necessarily all distinct. You are

also given n pairs of integers (Li, Ui) and have to determine for all 1 ≤ i ≤ n the number of elements

of A which satisfy Li ≤ A[m] ≤ Ui by an algorithm which runs in time O(n log n). (20 points)

Solution for Question 3:

We first sort the array A in O(n log n) time using merge sort. For the ith query (Li, Ui), we do

binary search twice to find the index of:

(1) the first element with value less than Li; and

(2) the last element with value greater or equal to Ui.

The difference between these indices is the answer to the ith query.

We can do a binary search in O(log n) time. There are n queries and we need to do 2 × n binary

searches. Therefore, the total time complexity is O(n log n).

4. Question 4

You are given an array containing a sequence of 2n?1 consecutive positive integers starting with 1

except that one number was skipped; thus the sequence is of the form 1, 2, 3, . . . , k? 1, k+ 1, . . . , 2n.

You have to determine the missing term accessing at most O(n) many elements of A. (20 points)

Solution for Question 4:

Let’s denote the array as A. It can be inferred that:

(1) for all i = 1, 2, ..., k ? 1, we have A[i] = i.

(2) for all i = k, k + 1, ..., 2n ? 1, we have A[i] = i+ 1.

Clearly, if A[j] = j then also for all i < j we have A[i] = i and if A[j] > j then for all i > j we have

A[i] > i. Thus the task is to find the smallest index i such that A[i] > i and we can do this with a

binary search in O(log (2n ? 1)) = O(n) time.

5. Question 5

Read about the asymptotic notation in the review material and determine if f(n) = O(g(n)) or

g(n) = O(f(n) or both (i.e., f(n) = Θ(g(n))) or neither of the two, for the following pairs of functions

(1) f(n) = log2(n); g(n) =

10