Solution 1. Key idea We use a divide-and-conquer approach.
Divide the list into two sublists, a1,a2,…,a⌈n⌉ and a⌈n⌉+1,a⌈n⌉+2,…,an. 222
Then, the targeted ordered pairs (a, b) can be classified into three types: both a and b are in the first sublist, both a and b are in the second sublist, a is in the first sublist and b is in the second sublist.
The number of targeted ordered pairs of the first two types are calculated recursively. The number of targeted ordered pairs of the third type are calculated by comparing each number in the first sublist with every number in the second sublist. However, to speed up the process, we sort both sublists first. This means that we can embed the calculation into mergesort. The modified Algorithm mergesort is as follows.
Copyright By PowCoder代写 加微信 powcoder
Algorithm mod-mergesort(L, l, u, icount); Input: L[l..u]: a list of integers;
Output: L[l..u] sorted in ascending order;
icount: the number of ordered pairs, (L[i], L[j]), in L such that i < j and L[i] > 2L[j]; if (lower < upper) then
mod-mergesort(L, l, ⌊ (l+u) ⌋, icnt1); 2
mod-mergesort(L, ⌊ (l+u) ⌋ + 1, u, icnt2); 2
Merge(L[l..⌊ (l+u) ⌋], L[⌊ (l+u) ⌋ + 1..u], L[l..u], icnt3); 22
icount := icnt1 + icnt2 + icnt3; end.
Algorithm Merge(A, B, AB, icnt)
Input: Two sorted lists A = a1,a2,...,am and B = b1,b2,...,bn;
Output: icnt = the number of ordered pairs (a,b) such that a ∈ A,b ∈ B and a > 2b,
AB = A ∪ B sorted in ascending order;
/* this part is essentially Algorithm mergesort */ i:=1; j:=1; k:=1;
while (i ≤ m and j ≤ n) do
if (ai ≤bj)
then ck := ai; i := i + 1; elseck :=bj; j:=j+1;
k := k + 1 endwhile;
then copy bj,bj+1,…,bn into ck,ck+1,…,cm+n; else copy ai,ai+1,…,am into ck,ck+1,…,cm+n;
/* end of mergesort */
/* Calculate the number of targeted ordered pairs of the third type */ k:=1; h:=1; icnt:=0;
while (k ≤ m and h ≤ n) do
if (ak ≤2∗bh)
thenk:=k+1; //no(sk,bj),h≤j≤n,isatargetedorderedpair elseicnt:=icnt+(m−k+1); //(si,bh),k≤i≤m,aretargetedorderedpairs
h := h + 1; endwhile;
copy c1,c2,…,cm+n into AB; end.
For clarity, in the following correctness proofs, we shall call an ordered pair (a,b) that satisfies a ∈ A, b ∈ B and a > 2b a targeted ordered pair.
Lemma 1: At the end of each iteration of the second while loop in Algorithm Merge, (a) for 1 ≤ i < k, the targeted ordered pairs (ai, b) have been accounted for in icnt;
(b) for k ≤ i ≤ m, the targeted ordered pairs (ai,bj),1 ≤ j < h, have been accounted for in icnt.
Proof: (By induction on the iteration number)
Induction basis: Both (a) and (b) vacuously hold true.
Induction hypothesis: Suppose at the end of the (l − 1)th iteration, both (a) and (b) hold.
Induction step: During the lth iteration,
ifak ≤2bh,thenasBisinascendingorder,bh
By Condition (a) of the induction hypothesis, all targeted ordered pairs (ai,bh),1 ≤ i < k, have been accounted for in icnt. It follows that all targeted ordered pairs (ai,bh),1 ≤ i ≤ m, have been accounted for in icnt. Hence, after h is incremented, Condition (b) is satisfied. Condition (a) clearly remains satisfied.
Theorem 2: Algorithm Merge(A, B, AB, icnt) calculates icnt such that icnt is the number of tar- geted ordered pairs in A ∪ B.
Proof: When execution of the second while loop terminates, either k = m + 1 or h = n + 1.
In the former case, By Lemma 1, Condition (a) implies that for 1 ≤ i < m + 1, the targeted ordered pairs (ai,b), where b ∈ B have been accounted for in icnt. This is equivalent to ∀a ∈ A,b ∈ B the targeted ordered pairs (a, b) have been accounted for in icnt. Hence, icnt = the number of targeted ordered pairs in A ∪ B.
In the latter case, By Lemma 1, Condition (a) implies that for 1 ≤ i < k, the targeted ordered pairs (ai,b), where b ∈ B have been accounted for in icnt, and Condition (b) implies that for k ≤ i ≤ m, the targeted ordered pairs (ai,bj),1 ≤ j < n + 1, have been accounted for in icnt.
This implies that the targeted ordered pairs (ai, b), 1 ≤ i < k, where b ∈ B have been accounted for in icnt, and the targeted ordered pairs (ai,b),k ≤ i ≤ m, where b ∈ B have been accounted for in icnt. It follows that the targeted ordered pairs (ai, b), 1 ≤ i ≤ m, where b ∈ B have been accounted for in icnt, which is equivalent to ∀a ∈ A, b ∈ B the targeted ordered pairs (a, b) have been accounted for in icnt. Hence, icnt = the number of targeted ordered pairs in A ∪ B.
Theorem 3: Algorithm Mod-Mergesort runs in O(n lg n) time.
Let T (n) be the time complexity of Algorithm Mod-Mergesort for inputs of size n. The two recursive calls take T(⌈n⌉) and T(⌊n⌋) time, respectively.
In Algorithm Merge, the initialization instructions before the first while loop takes O(1) time. Since the body of the first while loop takes O(1) time per iteration, and the while loop iterates at
most ⌈n⌉ + ⌊n⌋ = n time, the while loop thus takes O(n) time. 22
The if statement after the while loop takes max{O(⌈ n ⌉), O(⌊ n ⌋)} = O(n) time. 22
the initialization instructions before the second while loop takes O(1) time.
Since the body of the second while loop takes O(1) time per iteration, and the while loop iterates
at most ⌈n⌉ + ⌊n⌋ = n time, the while loop thus takes O(n) time. 22
The last statement takes O(n) time.
Hence, Algorithm Merge takes O(1) + O(n) + O(n) + O(1) + O(n) + O(n) = O(n) time.
The statement after Algorithm Merge clearly takes O(1) time.
We thus have T (n) = T (⌈ n ⌉) + T (⌊ n ⌋) + O(n) + O(1) = T (⌈ n ⌉) + T (⌊ n ⌋) + O(n). 22 22
The recurrence is identical to that of mergesort (see the courseware) whose solution is T (n) = O(n lg n).
Hence, Algorithm Mod-Mergesort runs in O(n lg n) time.
2. (a) Key idea:
The reduction comprises a pair of algorithms (Aπ,AS).
First, consider Algorithm Aπ.
Given L as the input list.
Determine the smallest element, min, and the largest element, max, of L.
Create a list L′ consisting of n copies of min, following by L, and then 2n copies of max. Next, consider Algorithm AS.
Let si, 1 ≤ i ≤ 4n, be the output generated by the interactive-means algorithm on input L′. Then, s2n+(2i−1)1, 1 ≤ i ≤ n, is the list L sorted in ascending order.
The following are pseudo codes for algorithms Aπ and AS.
Algorithm Aπ
Input: A list of n elements L : a1,a2,...,an for Sorting.
Output: A list of 4n elements L′ : a′1, a′2, . . . , a′4n for Interactive Median. begin
1. Determine the smallest element min and largest element max of L. 2. Output the list L′ = a′1,a′2,...,a′4n such that
• a′i =min,1≤i≤n; //ncopiesofmin
• a′n+i =ai,1≤i≤n; //theinputlistL
• a′2n+i =max,1≤i≤2n. //2ncopiesofmax
end. Algorithm AS
Input: The output list of 4n elements S′ : s1, s2, . . . , s4n of an Interactive Median algorithm on input L′.
Output: A sublist S of S′. begin
1. Extract S = s2n+1, s2n+3, s2n+5, . . . , s4n−3, s4n−1 (i.e s2n+(2i+1), 0 ≤ i < n) from S′. 2. Output S.
Lemma 1: ∀i, 1 ≤ i ≤ n, s2n+(2i−1) is the ith smallest element in L.
Proof: By induction on i. Induction basis:
When i = 1, 2n+(2i−1) = 2n+(2(1)−1) = 2n+1, and the corresponding input list for the interactive-mean algorithm is L′2n+1 = a′1, a′2, . . . , a′2n+1.
Let ah be the smallest element in L. Then ah = a′n+h.
Since a′i = min,1 ≤ i ≤ n, there are n elements x in L′2n+1 such that x ≼ a′n+h.
On the other hand, ah is the smallest element in L implies that a′n+h is the smallest element in a′n+i, 1 ≤ i ≤ n, which imples that a′n+h ≼ a′n+i, (i ̸= h)∧1 ≤ i ≤ n. Moreover, a′n+h ≼ a′2n+1(= max). Therefore, there are n elements x in L′2n+1 such that a′n+h ≼ x.
Hence, a′n+h(= ah) is the median of L′2n+1 which implies that s′2n+1 = ah.
Induction hypothesis: Suppose s2n+(2(k−1)−1) is the (k − 1)th smallest element in L.
Induction step: Consider s2n+(2k−1).
The corresponding input list for the interactive-mean algorithm is L2n+2(k−1) = a′1, a′2, . . . , a′2n+(2k−1).
By the induction hypothesis, s2n+(2(k−1)−1) is the (k − 1)th smallest element in L’
But s2n+(2(k−1)−1) is the median of L2n+2((k−1)−1) = a′1, a′2, . . . , s′2n+(2(k−1)−1).
Therefore, there are n + k − 1 elements x in L2n+2((k−1)−1) such that x ≼ s2n+(2(k−1)−1), and
there are n + k − 1 elements x in L2n+2((k−1)−1) such that s2n+(2(k−1)−1) ≼ x. ⇒ there are n + k elements x in L2n+(2(k−1)−1) such that x ≼ al, and
there are n + k − 2 elements x in L2n+(2(k−1)−1) such that al ≼ x, where al is the kth smallest
element in L.
⇒ there are n + k elements x in L2n+(2k−1) such that x ≼ al, and
there are n + k elements x in L2n+(2k−1) such that al ≼ x as a′2n+(2k−2) = a′2n+(2k−1) = max, ⇒ al is the median of L2n+(2k−1)
Hence, s2n+(2k−1) = al.
Theorem 2: The list S is the list L in ascending order. Proof: Immediate from Lemma 1.
Theorem 3: The reduction algorithm runs in O(n) time.
Proof: In Algorithm Aπ,
Step 1 takes O(n) time (e.g. use Algorithm minmax in the lecture notes).
Since making a copy of min or max takes O(1) time, creating a′i,1 ≤ i ≤ n, takes O(n) time and creating a′2n+i, 1 ≤ i ≤ 2n, also takes O(n) time. Creating a′n+i, 1 ≤ i ≤ n, involves copying L which takes O(n) time.
Hence, Algorithm Aπ takes O(n) time.
In Algorithm AS By scanning the list S, the list m2n+1,m2n+3,...,m2n+(2i+1),...,n2n+(2n−1) can
be created in O(n) time.
Hence, the reduction algorithm runs in O(n)-time.
(b) We shall prove that Ω(n lg n) is a lower bound for the problem of finding medians interactively. Theorem 4: Any algorithm that finds medians interactively takes Ω(n lg n) time to process a se-
quence of n elements in the worst case.
Let Algorithm M be an algorithm that solves the interactive-means problem.
Using the reduction developed in Part (a), we obtain the following algorithm for sorting a list of n elements.
Algorithm Sort
Input: An output list L of n elements drawn from a totally ordered set; Output: The list L in ascending order;
1. Run Algorithm Aπ on input L to produce the list L′; 2. Run Algorithm M on input L′ to produce the list S′; 3. Run Algorithm AS on input S′ to produce the list S;
By Theorem 2, Algorithm Sort correctly sorts the list L. By Theorem 3, sorting is O(n)-transformable
to the problem of finding medians interactively.
Since Ω(n lg n) is a lower bound on time complexity for sorting a list of n elements and n ∈ o(n lg n),
by Theorem 3.7 (see lecture notes), Ω(n lg n) is a lower bound on time complexity for the problem of finding medians interactively.
3. (a) Key idea: By assumption, let b be an entry such that b ∈/ B but has a neighbour in B and b < x,∀x ∈ B. ······ (I)
{A[i,j] | A[i,j] is in row ⌈n⌉ or column ⌈n⌉}, 2 2
n is odd; niseven,
excluding the entries in B.
D={A[i,j]|A[i,j]∈/B∪C, andA[i,j]hasaneighbourinB∪C}.
Then, b ∈/ B and b has a neighbour in B implies b ∈ C ∪D. ······ (II) Letm=min≤(B∪C∪D). Thenm≤b ((II),definitionofmin)
⇒ m < x,∀x ∈ B. (by (I))
⇒m∈C∪D (∵m∈(B∪C∪D)) ······ (III)
If m ∈ C, then m is a local minimum.
{A[i,j]|A[i,j]isinrow⌈n⌉or⌈n⌉+1, orcolumn⌈n⌉or⌈n⌉+1}, 22 22
I f m ∈/ C , t h e n b y ( I I I ) , m ∈ D .
B and C divide array A into 4 sub-arrays. The entries on the boundary of each of these sub-arrays are in B ∪ C.
Let A′ be the sub-array containing m.
Since m ∈ D, A′ satisfies the condition that A satisfies.
We can thus continue to find a local minimum of A in A′.
The following is a pseudo code of the algorithm.
AlgorithmLocal-min(A,lr,ur,lc,uc) begin
n:=ur −lr +1;
if (n ≥ 5) then
/* B: all A[i,j] in row lr, row ur, column lc or column uc
row ⌊lr+ur ⌋, column ⌊lc+uc ⌋, if n is odd; C: all A[i,j] in 2 2
rows⌊lr+ur⌋,⌊lr+ur⌋+1, columns⌊lc+uc⌋,⌊lc+uc⌋+1, ifniseven, 22 22
and not in B.
D : a l l A [ i , j ] ∈/ B ∪ C t h a t h a s a n e i g h b o u r i n B ∪ C . * /
A[h,k] := min≤{A[i,j] | A[i,j] ∈ B ∪ C ∪ D};
if (A[h, k] ∈ C) then return A[h, k] // A[h, k] is a local min else
ε := if (n is odd) then 0 else 1; case (m = A[h, k]) of
h < ⌊lr+ur ⌋, k < ⌊lc+uc ⌋: Local-min(A,lr,⌊lr+ur ⌋,lc,⌊lc+uc ⌋ ); 2222
h>⌊lr+ur⌋+ε, k<⌊lc+uc⌋: Local-min(A,⌊lr+ur⌋+ε,ur,lc,⌊lc+uc⌋); 2222
h<⌊lr+ur⌋, k>⌊lc+uc⌋+ε: Local-min(A,lr,⌊lr+ur⌋,⌊lc+uc⌋+ε,uc ); 2222
h>⌊lr+ur⌋+ε, k>⌊lc+uc⌋+ε: Local-min(A,⌊lr+ur⌋+ε,ur,⌊lc+uc⌋+ε,uc ); 2222
else // base cases
return min≤{A[i,j] | lr < i < ur,lc < j < uc};
Lemma 1: If A[h, k] ∈ C then A[h, k] is a local min. Proof:
Let mr = [lr+ur ], mc = ⌊lc+uc ⌋, and n = ur − lr + 1 = uc − lc + 1. 22
Then C consists of all the entries in row mr or column mc, if n is odd, or all the entries in rows mr ± ε or columns mc ± ε, where ε ∈ {0, 1}, if n is even, excluding all those entries that are also in B.
By definition, D contains all the entries in rows mr ± 1 or columns mc ± 1, if n is odd, or all the entries in rows mr ± ε, or columns mc ± ε, where ε ∈ {−1, 2}, if n is even, excluding all those entries that are also in B.
It follows that the entries in C have their neighbouring entries in B ∪ C ∪ D.
Since A[h,k] = min≤{A[i,j] | A[i,j] ∈ B ∪ C ∪ D}, if A[h,k] ∈ C, then A[h,k] is a local min of A.
Theorem 2: Algorithm Local-min correctly finds a local min of the array A. Proof: Byinductiononn(=ur−lr+1=uc−lc+1)
Induction basis: When n < 5, since min≤{A[i,j] | lr < i < ur,lc < j < uc} is the smallest number in the array. It is thus a local min.
Induction hypothesis:
Suppose Algorithm Local-min correctly finds a local min for k × k arrays, where k < n.
Induction step:
Let A be an n × n array.
By assumption, let b ∈/ B such that b has a neighbour in B and b < x,∀x ∈ B. ······ (I) Then, b ∈/ B such that b has a neighbour in B
⇒ b ∈ C ∪ D
⇒ b ∈ B ∪ C ∪ D
⇒ A[h, k] ≤ b
⇒ A[h,k] < x,∀x ∈ B (by (I))
⇒ A [ h , k ] ∈/ B
⇒A[h,k]∈C∪D (A[h,k]∈B∪C∪D)······ (II)
If A[h, k] ∈ C, then A[h, k] is correctly returned as a local min by Lemma 1. Otherwise, A[h, k] ∈/ C ⇒ A[h, k] ∈ D. (by (II))
S i n c e A [ h , k ] ∈/ C i m p l i e s t h a t h ̸ = ⌊ l r + u r ⌋ a n d k ̸ = ⌊ l c + u c ⌋ , i f n i s o d d ; o r h ̸ = ⌊ l r + u r ⌋ ± ε a n d 222
k̸=⌊lc+uc⌋±ε,whereε∈{0,1},ifniseven. Thisleadstothefollowingfourcases: 2
Letε= 0, ifnisodd; 1, if n is even.
(a) (h<⌊lr+ur⌋)∧(k<⌊lc+uc⌋): 22
Let A′ be the sub-array A[lr..⌊lr+ur ⌋;lc..⌊lc+uc ⌋] and B′ be its border. 2′2
Since the upper and left borders of A consist of entries of B, and the lower and right borders of A′ consist of entries of C, B′ ⊆ B ∪C.
Then A[h,k] = min≤{A[i,j] | A[i,j] ∈ B ∪ C ∪ D}
⇒A[h,k]
SimilartoCase(a)exceptA′ isthesub-arrayA[lr..⌊lr+ur⌋;⌊lc+uc⌋+ε..uc] 22
(d) (h>⌊lr+ur⌋+ε)∧(k>⌊lc+uc⌋+ε): 22
SimilartoCase(a)exceptA′ isthesub-arrayA[⌊lr+ur⌋+ε..ur;⌊lc+uc⌋+ε..uc] 22
In each of the above cases, as A′ is an ⌈ n ⌉ × ⌈ n ⌉ array, by the induction hypothesis, Algorithm 22
Local-min correctly finds a local min for array A.
Theorem 2: Algorithm Local-min runs in O(n).
Proof: Let T (n) be the time complexity of Algorithm Local-min for all inputs of size n.
Then, determining A[h,k] involves scanning at most 4 rows and 4 columns of A which takes O(n) time.
Verifying A[h,k] ∈ C can be accomplished by checking the following conditions which can be done in O(1) time:
h=⌊lr+ur⌋∨k=⌊lc+uc⌋, ifnisodd; 22
h=⌊lr+ur⌋+ε∨k=⌊lc+uc⌋+ε,ε∈{0,1}, ifniseven. 22
In each of the four cases, finding a local min in the sub-array takes T(⌈n⌉) time.
Wethushave: T(n)=T(⌈n⌉)+O(n). 2
Solving the recurrence using the Master Theorem (Case 3), we have T (n) = O(n). (b) We reduce this problem to the problem in Part (a) as follows:
Algorithm Local-minimum(A)
A[h, k] := min≤{A[i, j] | A[i, j] ∈ B}, where B be the border of Array A. if (h ∈ {1,n} ∧ k ∈ {1,n}) then return A[h,k] as a local min
else let b be the neighbour of A[h, k] not in B
if (A[h, k] < b) then return A[h, k] as a local min
else Local-min(A, 1, n, 1, n) // call the algorithm of Part (a) end.
Theorem 1: Algorithm Local-minimum correctly finds a local min of the array A. Proof: Since A[h, k] is the smallest number in B, A[h, k] < x, ∀x ∈ B.
if (h ∈ {1,n} ∧ k ∈ {1,n}), then A[h,k] is one of A[1,1],A[1,n],A[n,1], and A[n,n]. Since A[h, k] is smaller than all of its neighbours in each of the cases, it is a local min. Otherwise, b is its only neighbour not in B.
If A[h, k] < b, then A[h, k] is smaller than all of its neighbours which implies that it is a local min.
Otherwise, A[h,k] > b which imples that b < x,∀x ∈ B. Hence, A is an array satisfying the condition given in Part (a). We can thus use Algorithm Local-min to find a local min in A.
Theorem 2: Algorithm Local-minimum runs in O(n) time.
Determining A[h, k] involves scanning the bonder of A which takes O(n) time. Verifying the condition (h ∈ {1, n} ∧ k ∈ {1, n}) takes O(1) time.
Determining b takes O(1) time.
Checking A[h, k] < b takes O(1) time, and executing Algorithm Local-min with input A takes O(n) time by Part (a).
Hence, the algorithm takes O(n) + O(1) + O(1) + O(1) + O(n) = O(n) time.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com