CS代写 COMP3711: Design and Analysis of Algorithms

COMP3711: Design and Analysis of Algorithms
Tutorial 4: D&C, Sorting

Using Median Algorithms

For this problem, assume that you are given a black−box 𝑂(𝑛) time algorithm for finding the median ⌈𝑛/2 ⌉′nd item in a size n array.
Black-box means that you can call the algorithm and use its result, but can’t peer inside of it.
Note: This black box is solving the special case of the Selection problem in which 𝑘 = ⌈𝑛/2 ⌉.

Assume that you are given a black−box 𝑂(𝑛) time algorithm for finding the median ⌈𝑛/2 ⌉′nd item in a size n array.
(a) Show how Quicksort can be modified to run in 𝑂(𝑛 log 𝑛) worst case time.
(b) Give a simple linear-time algorithm that solves the selection problem for an arbitrary order statistic.
(c) Solve the weighted median problem in 𝑂(𝑛) time.

(a) Show how Quicksort can be modified to run in 𝑂(𝑛 log 𝑛) worst case time.
• Before every partition step in Quicksort, use the 𝑂(𝑛) black box algorithm to find the median of the current subarray.
• Then use that median as the pivot.
• This splits the subarray into two (almost) equal parts so the
running time of the full algorithm satisfies
T(n) = 2T(n/2) + O(n) implying𝑇 𝑛 = 𝑂 𝑛log𝑛 .

(b) Give a simple linear-time algorithm that solves the selection problem for an arbitrary order statistic.
That is, given 𝑘, your algorithm should solve the Selection problem of finding the 𝑘’th smallest item.
Solution: Modify the randomized selection algorithm so that it is deterministic.
At every step, instead of choosing the pivot at random from the current subarray, it uses the O(n) median finding algorithm to find the median and then uses the median as pivot.
Let 𝑇(𝑛) denote the running time of the algorithm on a problem of size at most n.
At each step, the algorithm will reduce the size of the array in which it is searching by at
least one- half so the running time satisfies
T(n) ≤ T(n/2)+O(n), implying (why?) 𝑇 𝑛 = 𝑂 𝑛 .

(c) Let 𝑥1, 𝑥2, … , 𝑥𝑛 be 𝑛 distinct (unsorted) elements with associated positive weights 𝑤 ,𝑤 ,…,𝑤 such that ∑𝑤 = 1.
Their weighted (lower) median is the element 𝑥𝑘 satisfying
෍ 𝑤<1 and ෍ 𝑤≤1. 𝑗2 𝑗2 {𝑗: 𝑥𝑗< 𝑥𝑘 } 𝑗: 𝑥𝑗 > 𝑥𝑘
𝑘 = 6 because
𝑥1,𝑥2,𝑥3,𝑥8 < 𝑥6 𝑥4,𝑥5,𝑥7,> 𝑥6
𝑤1 + 𝑤2 + 𝑤3 + 𝑤8 = .45 < 0.5 𝑤 +𝑤 +𝑤 =.4≤0.5 457 (c) Let 𝑥1, 𝑥2, , 𝑥𝑛 be 𝑛 distinct (unsorted) elements with associated positive weights 𝑤 ,𝑤 ,...,𝑤 such that ∑𝑤 = 1. Their weighted (lower) median is the element 𝑥𝑘 satisfying ෍ 𝑤<1 and ෍ 𝑤≤1. 𝑗2 𝑗2 {𝑗: 𝑥𝑗< 𝑥𝑘 } 𝑗: 𝑥𝑗 > 𝑥𝑘
If the 𝑥 are sorted, then it is easy to find the weighted median in 𝑂(𝑛) time by just 𝑗
summing up the weights from left to right and walking through the sums until k is found. Show that if the items are not sorted you can still solve the problem in linear time
using the linear –time black box median finding algorithm as a subroutine.
Intuition: We will develop a linear time test (using the black box) that reduces the size of the problem by a half each step. This immediately implies a linear time algorithm

If 𝑛 = 1,2 can solve the problem in 𝑂 1 time.
Otherwise, first find the unweighted median index 𝑚 using the 𝑂 𝑛 time
median-finding algorithm.
Next, use 𝑂 𝑛 time (how?) to calculate
𝑊= ෍ 𝑤 and 𝑊=1−𝑊= ෍ 𝑤 𝐿𝑗𝑅𝐿𝑗
{𝑗: 𝑥𝑗≤ 𝑥𝑚 } 𝑗: 𝑥𝑗 > 𝑥𝑚 Major observation is
W ≤1 ifandonlyif x ≤𝑥 . 𝑅2𝑘𝑚

𝑊= ෍ 𝑤 and𝑊=1−𝑊= ෍ 𝑤 𝐿𝑗𝑅𝐿𝑗
{𝑗: 𝑥𝑗≤ 𝑥𝑚 } 𝑗: 𝑥𝑗 > 𝑥𝑚
𝑘 satisfies
෍ 𝑤<1 and ෍ 𝑤≤1. 𝑗2 𝑗2 {𝑗: 𝑥𝑗< 𝑥𝑘 } 𝑗: 𝑥𝑗 > 𝑥𝑘
W ≤1 ifandonlyif 𝑥 ≤𝑥 . 𝑅2𝑘𝑚
Observation:
: 𝑥>𝑥 𝑥𝑘 ≤ 𝑥𝑚 𝑘 𝑚
⟺ 𝑗: 𝑥 > 𝑥 ⊆ {𝑗: 𝑥 > 𝑥 }
⟺ 𝑗: 𝑥 ≤ 𝑥 ⊆ {𝑗: 𝑥 < 𝑥 } ⟹𝑊=෍𝑤≤෍𝑤≤1 ⟹𝑊=෍𝑤≤෍𝑤<1 𝑅𝑗𝑗2𝐿𝑗𝑗2 𝑗:𝑥𝑗>𝑥𝑚 𝑗:𝑥𝑗>𝑥𝑘 𝑗:𝑥𝑗≤ 𝑥𝑚 𝑗:𝑥𝑗< 𝑥𝑘 ⟹𝑊 =1−𝑊 >1

𝑥𝑚 is the (unweighted median). In 𝑂(𝑛) time have already calculated
W ≤ 1 if and only if 𝑥 ≤ 𝑥 : 𝑚, 𝑊 =∑ 𝑤, 𝑊 =1−𝑊. Observedthat 𝑅 𝑘 𝑚
𝐿𝑥𝑗≤𝑥𝑚𝑗𝑅 𝐿 2
Call “𝑥1, 𝑥2, … , 𝑥𝑛 with weights 𝑤𝑖” the original problem. Now create new smaller problems:
IfW ≤1, set𝑤′𝑖 =ቊ𝑤𝑖 if𝑥𝑖 <𝑥𝑚 𝑅2 𝑤+𝑊if𝑥=𝑥 𝑖𝑅𝑖𝑚 Throw away all 𝑥𝑖 with 𝑥𝑖 > 𝑥𝑚. ⌈𝑛/2 ⌉ items remain.
From observation, none of the removed items were solution to the weighted median problem. Further observations: ∑ 𝑤′ = 1 and the weighted median of the remaining points with new
weights 𝑤𝑖 is the same as the weighted median of the original problem.
⇒ Solving the new subproblem will solve the original problem.

Merging k lists

Input is 𝑘 sorted lists that need to be merged into one sorted list.
The “obvious” method is to modify the merging procedure from mergesort; at every step, compare the smallest items from each list and move the minimum one among them to the sorted list.
Finding the minimum value of 𝑘 items requires 𝑂(𝑘) time so,
if the lists contain 𝑛 items in total, the full 𝑘-way merge would take 𝑂(𝑛𝑘) time.
This can be improved.
Design an 𝑂(𝑛 𝑙𝑜𝑔 𝑘)-time algorithm to merge 𝑘 sorted lists into one sorted list by making use of priority queues.
Note that each sorted list may contain a different number of elements.

The obvious method is to walk through the 𝑘 lists, maintaining a pointer to the first (smallest) unmerged element in each list. This pointer is to the current head of that list.
At the start, the head of each list is its first item. Finding smallest current head uses 𝑂 𝑘 time.
At each step find the current smallest head in 𝑂(𝑘) time and insert it at the end of the current merged list A. Move the old head that had pointed to the smallest item one to the right. Continue until all items have been found. This uses 𝑂 𝑛𝑘 time.

Now modify previous algorithm by keeping the list heads in a priority queue.
Each step now requires extracting the minimum from the priority queue and inserting the
new smallest item (from the appropriate list) into the priority queue.
Since each priority queue operation requires 𝑂 log 𝑘 time, the entire merge requires 𝑂 𝑛log𝑘 time.

The idea is to modify the obvious algorithm;
find the minimum at each step using a priority queue.
Walk through the 𝑘 lists, maintaining a pointer to the first (smallest) unmerged element in each list. At the start, the pointers point to the first element of each list. We’ll call these items the heads of the lists.
1. Label each element to indicate to which sorted list it belongs. //𝑂(𝑛) 2. Build a min-heap of 𝑘 list-heads. //𝑂(𝑘 log 𝑘)
3. Extract-Min from the heap and output item. //𝑂(log 𝑘)
4. If extracted element belongs to 𝑖-th sorted list, move the 𝑖-th pointer by
one and insert the new head of the 𝑖-th list into the min-heap. //𝑂(log 𝑘) 5. Repeat 3 and 4 until all n elements have been outputted.
Step 3 and 4 will be repeated at most 𝑛 times.
=>Algorithm’s runningtimeis𝑛+𝑘log𝑘+2𝑛log𝑘=𝑂(𝑛log𝑘).

Decrease-Key (in Heaps)

Consider the heap implementation of a Priority Queue shown in class that keeps its items in an Array 𝐴[].
Let Decrease-Key(𝑖, 𝑥) be the operation that compares 𝑥 to 𝐴[𝑖] :
If 𝑥 ≥ 𝐴 𝑖 , it does nothing.
If 𝑥 < 𝐴[𝑖], it sets 𝐴[𝑖] = 𝑥 and, if necessary, fixes 𝐴[] so that it remains a Heap. Show how to implement Decrease-Key(𝑖, 𝑥) in 𝑂(log 𝑛) time, where 𝑛 is the number of items in the Heap. Note: We will use the operation Decrease-Key(𝑖, 𝑥) later in the semester. Recall the code for inserting an item into a heap. We inserted the item into location i which was the LAST item in the heap and then bubbled it up to its proper place. The solution to this problem uses almost exactly the same code as the insertion except that 𝑖 might no longer be the last value. If we do change the value in 𝐴[𝑖] to be 𝐴[𝑖] = 𝑥, everything below node 𝑖 still satisfies the heap condition and node 𝑖 satisfies the heap condition (because we've LOWERED its value). The only problem might be that ancestors of 𝑖 might have values that are greater than 𝐴[𝑖]. We can fix this by bubbling 𝐴[𝑖] up to its proper value. if 𝑥 < 𝐴[𝑖] 𝐴𝑖 =𝑥; 𝑗 = 𝑖; while 𝐴 𝑗 < 𝐴[ 𝑗 ] and 𝑗 > 1 do 2
// 𝐴[𝑗] is less than its parent
Swap 𝐴[𝑗] and 𝐴[ 𝑗 ]; // Bubble Up
See example

Decrease-Key example I
Decrease-Key(5, 10)

Decrease-Key example II
Decrease-Key(9, 15)

Decrease-Key example II
Decrease-Key(9, 15)
In the 1st example, decreased key, bubbled all of the way to the top.
In the 2nd example, it stopped below the top.

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts