chap10.htm

介绍算法的书籍

<a name="079f_13b5">10.3-3<a name="079f_13b5"><P>
<a name="079f_13b0">Show how quicksort can be made to run in <I>O</I>(<I>n </I>1g <I>n</I>) time in the worst case.<P>
<a name="079f_13b6">10.3-4<a name="079f_13b6"><P>
Suppose that an algorithm uses only comparisons to find the <I>i</I>th smallest element in a set of <I>n</I> elements. Show that it can also find the <I>i</I> - 1 smaller elements and the <I>n</I> - <I>i</I> larger elements without performing any additional comparisons.<P>
<a name="079f_13b7">10.3-5<a name="079f_13b7"><P>
Given a "black-box" worst-case linear-time median subroutine, give a simple, linear-time algorithm that solves the selection problem for an arbitrary order statistic.<P>
<a name="079f_13b8">10.3-6<a name="079f_13b8"><P>
<a name="079f_13b1">The <I>k</I>th <I><B>quantiles </I></B>of an <I>n</I>-element set are the <I>k</I> - 1 order statistics that divide the sorted set into <I>k</I> equal-sized sets (to within 1). Give an <I>O</I>(<I>n </I>1g <I>k</I>)-time algorithm to list the <I>k</I>th quantiles of a set.<P>
<a name="079f_13b9">10.3-7<a name="079f_13b9"><P>
Describe an <I>O</I>(<I>n</I>)-time algorithm that, given a set <I>S</I> of <I>n </I>distinct numbers and a positive intege<I>r k</I> <img src="../images/lteq12.gif"> <I>n</I>, determines the <I>k</I> numbers in <I>S</I> that are closest to the median of <I>S</I>.<P>
<a name="079f_13ba">10.3-8<a name="079f_13ba"><P>
Let <I>X</I>[1 . . <I>n</I>] and <I>Y</I>[1 . . <I>n</I>] be two arrays, each containing <I>n</I> numbers already in sorted order. Give an <I>O</I>(1g <I>n</I>)-time algorithm to find the median of all 2<I>n</I> elements in arrays <I>X</I> and <I>Y</I>.<P>
<a name="079f_13bb">10.3-9<a name="079f_13bb"><P>
Professor Olay is consulting for an oil company, which is planning a large pipeline running east to west through an oil field of <I>n</I> wells. From each well, a spur pipeline is to be connected directly to the main pipeline along a shortest path (either north or south), as shown in Figure 10.2. Given <I>x</I>- and <I>y</I>-coordinates of the wells, how should the professor pick the optimal location of the main pipeline (the one that minimizes the total length of the spurs)? Show that the optimal location can be determined in linear time.<P>
<img src="193_a.gif"><P>
<h4><a name="079f_13bc">Figure 10.2 We want to determine the position of the east-west oil pipeline that minimizes the total length of the north-south spurs.<a name="079f_13bc"></sub></sup></h4><P>
<P>


<P>







<h1><a name="07a0_13b7">Problems<a name="07a0_13b7"></h1><P>
<a name="07a0_13b8">10-1     Largest i numbers in sorted order<a name="07a0_13b8"><P>
Given a set of <I>n</I> numbers, we wish to find the <I>i</I> largest in sorted order using a comparison-based algorithm. Find the algorithm that implements each of the following methods with the best asymptotic worst-case running time, and analyze the running times of the methods in terms of <I>n</I> and <I>i</I>.<P>
<I><B>a.     </I></B>Sort the numbers and list the <I>i</I> largest.<P>
<I><B>b.     </I></B>Build a priority queue from the numbers and call <FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MAX</FONT> <I>i </I>times.<P>
<I><B>c.     </I></B>Use an order-statistic algorithm to find the <I>i</I>th largest number, partition, and sort the <I>i</I> largest numbers.<P>
<a name="07a0_13b9">10-2     Weighted median<a name="07a0_13b9"><P>
<a name="07a0_13b2"><a name="07a0_13b3"><a name="07a0_13b4"><a name="07a0_13b5">For <I>n</I> distinct elements <I>x</I><SUB>1</SUB>, <I>x</I><SUB>2</SUB>, . . . , <I>x<SUB>n</I></SUB> with positive weights <I>w</I><SUB>1</SUB>, <I>w</I><SUB>2</SUB>, . . . , <I>w<SUB>n</SUB> </I>such that <img src="193_b.gif"> the <I><B>weighted median</I></B> is the element <I>x<SUB>k</I></SUB> satisfying<P>
<img src="193_c.gif"><P>
<I><B>a.     </I></B>Argue that the median of <I>x</I><SUB>1</SUB>, <I>x</I><SUB>2</SUB>, . . . , <I>x<SUB>n</I></SUB> is the weighted median of the <I>x<SUB>i </I></SUB>with weights <I>w<SUB>i</I></SUB> = 1 / <I>n</I> for <I>i</I> = 1, 2, . . . , <I>n</I>.<P>
<I><B>b.     </I></B>Show how to compute the weighted median of <I>n</I> elements in <I>O</I>(<I>n </I>1g <I>n</I>) worst-case time using sorting.<P>
<I><B>c.     </I></B>Show how to compute the weighted median in <img src="../images/bound.gif">(<I>n</I>) worst-case time using a linear-time median algorithm such as <FONT FACE="Courier New" SIZE=2>SELECT</FONT> from Section 10.3.<P>
<a name="07a0_13b6">The<I> <B>post-office location problem</I></B><I> </I>is defined as follows. We are given <I>n </I>points <I>p</I><SUB>1</SUB>, <I>p</I><SUB>2</SUB>, . . . , <I>p<SUB>n</I></SUB> with associated weights <I>w</I><SUB>1</SUB>, <I>w</I><SUB>2</SUB>, . . . , <I>w<SUB>n</I></SUB>. We wish to find a point <I>p</I> (not necessarily one of the input points) that minimizes the sum <img src="194_a.gif">, where <I>d</I>(<I>a</I>, <I>b</I>) is the distance between points <I>a</I> and <I>b</I>. <P>
<I><B>d.     </I></B>Argue that the weighted median is a best solution for the 1-dimensional post-office location problem, in which points are simply real numbers and the distance between points <I>a</I> and <I>b</I> is <I>d</I>(<I>a</I>, <I>b</I>) = |<I>a</I> - <I>b|.</I><P>
<I><B>e.     </I></B>Find the best solution for the 2-dimensional post-office location problem, in which the points are (<I>x</I>, <I>y</I>) coordinate pairs and the distance between points <I>a</I> = (<I>x</I><SUB>1</SUB>, <I>y</I><SUB>1</SUB>) and <I>b</I> = (<I>x</I><SUB>2</SUB>, <I>y</I><SUB>2</SUB>) is the <I><B>Manhattan distance:</I></B> <I>d</I>(<I>a</I>, <I>b</I>) = |<I>x</I><SUB>1</SUB> - <I>x<SUB>2</I></SUB>| + |<I>y</I><SUB>1</SUB> - <I>y<SUB>2</I></SUB>|.<P>
<a name="07a0_13ba">10-3     Small order statistics<a name="07a0_13ba"><P>
The worst-case number <I>T</I>(<I>n</I>) of comparisons used by <FONT FACE="Courier New" SIZE=2>SELECT</FONT> to select the <I>i</I>th order statistic from <I>n</I> numbers was shown to satisfy <I>T</I>(<I>n</I>) = <img src="../images/bound.gif">(<I>n</I>), but the constant hidden by the <img src="../images/bound.gif">-notation is rather large. When <I>i</I> is small relative to <I>n</I>, we can implement a different procedure that uses <FONT FACE="Courier New" SIZE=2>SELECT</FONT> as a subroutine but makes fewer comparisons in the worst case.<P>
<I><B>a.     </I></B>Describe an algorithm that uses <I>U<SUB>i</I></SUB>(<I>n</I>) comparisons to find the <I>i</I>th smallest of <I>n</I> elements, where <I>i</I> <img src="../images/lteq12.gif"> <I>n </I>/ 2 and<P>
<img src="194_b.gif"><P>
(<I>Hint:</I> Begin with <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>n </I></FONT>/ 2<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> disjoint pairwise comparisons, and recurse on the set containing the smaller element from each pair.)<P>
<I><B>b.     </I></B>Show that <I>U<SUB>i</I></SUB>(<I>n</I>) = <I>n</I> + <I>O</I>(<I>T</I>(2<I>i</I>)1g(<I>n </I>/ <I>i</I>)).<P>
<I><B>c.     </I></B>Show that if <I>i</I> is a constant, then <I>U<SUB>i</I></SUB>(<I>n</I>) = <I>n</I> + <I>O</I>(1g <I>n</I>).<P>
<I><B>d.     </I></B>Show that if <I>i</I> = <I>n </I>/ <I>k</I> for <I>k</I> <img src="../images/gteq.gif"> 2, then <I>U<SUB>i</I></SUB>(<I>n</I>) = <I>n</I> + <I>O</I>(<I>T</I>(2<I>n </I>/ <I>k</I>) 1g <I>k</I>).<P>
<P>







<h1>Chapter notes</h1><P>
The worst-case median-finding algorithm was invented by Blum, Floyd, Pratt, Rivest, and Tarjan [29]. The fast average-time version is due to Hoare [97]. Floyd and Rivest [70] have developed an improved average-time version that partitions around an element recursively selected from a small sample of the elements.<P>
<P>


<P>
<P>
<center>Go to <a href="partiii.htm">Part III</A>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Back to <a href="toc.htm">Table of Contents</A>
</P>
</center>


</BODY></HTML>