http:^^www.cs.washington.edu^education^courses^421^96w^bboard.shtml

来自「This data set contains WWW-pages collect」· SHTML 代码 · 共 1,546 行 · 第 1/5 页

From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: cse421@cs
Subject: <b>expected time for insertion sort</b>
</a>

Andy poins out that as part of the answer to  8.4-4 on page 167, you
seemingly have to prove something about the expected case running
time for insertion sort.  That's correct, but it turns out that a
simple upper bound on the worst-case running time is all you need,
so this isn't too hard.  In other words, unlike the quicksort part,
you do NOT need to  try to set up or solve a recurrence for the
expected time of the insertion part.
<hr size=4><a name="822560087001">Date: 25 Jan 1996 00:41 PST
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: cse421@cs
Subject: <b>Re: (CSE421) Problems using induction to prove correctness</b>
</a>


  &gt; I'm having difficulty making the leap from base case and inductive hyp. 
  &gt; to the inductive step for the case when n+1.  In other words, I can 
  &gt; convince myself that StoogeSort works for length 1 or three, and assume 
  &gt; that it works for length n, but I just don't see anyway to reason about 
  &gt; sorting length n+1.  
  &gt; 
  &gt; Are there any hints you could offer or am I approaching this wrong?

Approach sounds right.  

Hint one: forget (temporarily) that it's recursion/induction;
generally all you should need to assume about what goes on in the
recursive calls is THAT they sort; you shouldn't need to ever know
HOW they sort.  (That's the beauty of induction...)  

Hint two: work from some examples.  What happens if the input is
already sorted?  what happens if the input is reverse-sorted?  What
happens if it's sorted but some particular 2 elements are out of
order?  Can you argue in general that the smallest element ends up in
position 1? the 5th smallest in position 5?  The largest in position
n?  Turning in scattered examples like these won't get full credit;
that's not the point.  But hopefully they will help you understand
what the algorithm is doing so that you can generalize from these
specific examples to a comprehensive correctness argument.
<hr size=4><a name="822622279001">To: cse421@geoduck
Subject: <b>Re: (CSE421) Problems using induction to prove correctness</b>
Date: Thu, 25 Jan 1996 18:11:05 PST
From: <b>Martin Tompa &lt;[e-mail]&gt;</b>
</a>


Another possible stumbling block that may be causing this kind of problem is
using the wrong form of induction.  (Just a guess from the way the question
below was worded.) You don't want to proceed from n to n+1, but rather from
about 2n/3 to n.  This suggests using the strong form of induction rather than
ordinary induction.

------- Forwarded Message

  &gt; Date:    25 Jan 1996 00:41:00 -0800
  &gt; From:    Larry Ruzzo &lt;[e-mail]&gt;
  &gt; To:      cse421@cs
  &gt; Subject: Re: (CSE421) Problems using induction to prove correctness
  &gt; 
  &gt; 
  &gt;   &gt; I'm having difficulty making the leap from base case and inductive hyp.
 
  &gt;   &gt; to the inductive step for the case when n+1.  In other words, I can 
  &gt;   &gt; convince myself that StoogeSort works for length 1 or three, and assume
 
  &gt;   &gt; that it works for length n, but I just don't see anyway to reason about
 
  &gt;   &gt; sorting length n+1.  
  &gt;   &gt; 
  &gt;   &gt; Are there any hints you could offer or am I approaching this wrong?
  &gt; 
  &gt; Approach sounds right.  
  &gt; 
  &gt; Hint one: forget (temporarily) that it's recursion/induction;
  &gt; generally all you should need to assume about what goes on in the
  &gt; recursive calls is THAT they sort; you shouldn't need to ever know
  &gt; HOW they sort.  (That's the beauty of induction...)  
  &gt; 
  &gt; Hint two: work from some examples.  What happens if the input is
  &gt; already sorted?  what happens if the input is reverse-sorted?  What
  &gt; happens if it's sorted but some particular 2 elements are out of
  &gt; order?  Can you argue in general that the smallest element ends up in
  &gt; position 1? the 5th smallest in position 5?  The largest in position
  &gt; n?  Turning in scattered examples like these won't get full credit;
  &gt; that's not the point.  But hopefully they will help you understand
  &gt; what the algorithm is doing so that you can generalize from these
  &gt; specific examples to a comprehensive correctness argument.

------- End of Forwarded Message
<hr size=4><a name="822938502001">To: cse421@geoduck
cc: [e-mail]
Subject: <b>CSE 421 lecture cancelled today</b>
Date: Mon, 29 Jan 1996 10:01:30 PST
From: <b>Martin Tompa &lt;[e-mail]&gt;</b>
</a>


Because of the icy roads and what I hear is low student attendance on
campus today, I'm cancelling lecture and my office hour today.  I
apologize to those of you who struggled to get to campus.  See you on
Wednesday, I hope.

<hr size=4><a name="823131737001">To: cse421@geoduck
Subject: <b>more on the (in)efficiency of the selection algorithm</b>
Date: Wed, 31 Jan 1996 15:41:49 PST
From: <b>Martin Tompa &lt;[e-mail]&gt;</b>
</a>


I was somewhat dismayed in lecture today about the fact that the linear time
selection algorithm only seemed to use fewer comparisons than sorting when n &gt;
2 ^ (80d) = 2 ^ 240.  This is obviously totally impractical.  (I hope you
realized that when I said we wouldn't be doing any useful algorithms in this
class, I was being facetious.  Although the stress is on elegant algorithms
with good theoretical analyses, we wouldn't be doing much good if they or
their techniques weren't also useful in practice.  For most of the algorithms
we cover, I hope you will find them practical as well as elegant.)

I gave the analysis more thought, and with some care you can get the constant
down from 240 to nearly 24.  This comes from two sources:

(1) A careful analysis shows that d = 2.4 -- the overhead is 1.4n for sorting
the blocks of size 5, and n+1 for partitioning about x.

(2) As Yih-Chun suggested, raising the basis of the recurrence beyond 80 pays
off.  Remember that, in determining the constant c, I had an expression that
was 80d when n=80 and decreased monotonically to 10d in the limit?  By raising
the basis, you can get as close to 10d as you like, and it doesn't happen too
slowly.  Of course, raising the basis also affects d, so there's a tradeoff.

Putting these together, we end up with an algorithm whose number of
comparisons is slightly more than 10dn = 24n.  

The good news is that 24n is a respectable running time, much better than the
conservative 240n derived in class.  The bad news is that this still only
beats mergesort when n &gt; 2^24 &gt; 10^7.  But this says more about how very
efficient an nlogn time algorithm is, rather than how inefficient a 24n time
algorithm is.  For instance, this 24n time selection algorithm would beat
insertion sort (in number of comparisons) when n &gt; 48.

Using blocks of size 15 and more clever tricks, the original 1972 paper by
Blum, Floyd, Pratt, Rivest, and Tarjan provided an upper bound of 5.43n
comparisons.  The best upper bound to date is 3n comparisons, by Scho&quot;nhage,
Paterson, and Pippenger (1976), using quite different techniques.  The best
lower bound to date for the median problem is 2n comparisons, by Bent and John
(1985).  
<hr size=4><a name="823214482001">Date: Thu, 1 Feb 1996 14:41:14 -0800 (PST)
From: <b>Eva Marie Allen &lt;[e-mail]&gt;</b>
To: Algorithms &lt;[e-mail]&gt;
Subject: <b>problem 5</b>
</a>

Hi,

The longer I spend on this homework, the more I feel like I need to go 
back to kindergarten.

The definition of median is the ceiling(n+1/2) largest element.  
Correct?  Doesn't this mean that any of the elements of an 
array are the median, since they all have the same value?  The weighted 
median, on the other hand is very specific.  Is this how I should see 
this problem?

Thanks,

Eva
<hr size=4><a name="823224536001">Date: Thu, 1 Feb 1996 17:28:44 -0800 (PST)
From: <b>Michael Baker &lt;[e-mail]&gt;</b>
To: [e-mail]
Subject: <b>Tutors for 421?</b>
</a>


Because of work and a bout with sickness, I've fallen drastically behind
in this course and am at the point where I should either drop it or find a
tutor.  Not being much of a quitter and this being my last quarter at the
U, I'd prefer the latter case. 

Anyone out there willing to do some tutoring for 421?  Willing to pay 
well.  Drop me a line via e-mail.  Thanks in advance.

Michael

Michael Baker  ---  [e-mail]  ---  [e-mail]

Come in from the cold, I'll owe you my heart,             
   Be my shelter and refuge for the night.           Fields of the Nephilim
      Love of my life, pour your light,               (Paradise Regained)
  On the faith I can feel, make it real....               

<hr size=4><a name="823225857001">Date: Thu, 1 Feb 1996 17:50:47 -0800 (PST)
From: <b>Wade Barrett &lt;[e-mail]&gt;</b>
To: [e-mail]
Subject: <b>So HOW BAD IS IT, Really?</b>
</a>

I did a bunch of number-crunching on my $5.00 (if that) calculator to try 
to figure out WHEN (for what value of n) the dazzlingly linear-time 
SELECT algorithm REALLY does its job with fewer comparisons than simply 
n*lg(n) sorting the n elements and indexing the one you want.

        Here's the formula I crunched:     For what value of n is:

|n/5| lg |n/5|  +  (7n/10 + 6) lg (7n/10 + 6)  +  2.4 n   &lt;   n*lg(n)   ?

        Here's why:

One of our recent homework problems suggested a sorting algorithm that 
QuickSorted n elements (recursively) until the size of the subproblem was 
less than k for some k.  The inequality I wrote above implicitly ASSUMES 
that for the value of n being tested, I will compare the n*lg(n) sort (on 
the right) with a NON-RECURSIVE version of SELECT.  In other words, see 
if it pays off to go through the SELECT routine JUST ONCE.  I submit that 
the smallest value of n that makes the above inequality true is EXACTLY 
the crossover point (counting the number of comparisons) at which one 
should benefit from using the SELECT routine instead of sorting all n 
elements.

        Details of the formula:

1.4n                        ...  Sort the |n/5| baby groups of 5 each
|n/5| lg |n/5|              ...  Sort the medians of the |n/5| groups
n                           ...  Partition the n elements about the x
(7n/10 + 6) lg (7n/10 + 6)  ...  Sort the group containing the median

The 1.4n comes from the fact that 5 elements can be sorted with 7 
comparisons, giving 7 * |n/5| = 1.4n comparisons.  (In fact, the ceiling 
can be dropped since the leftover (m = 1, 2, 3, or 4) elements always 
require less than 1.4*m comparisons to sort.)


        HERE'S THE ANSWER:

By somewhere around n = 60,000, it requires less comparisons to use the 
SELECT algorithm than to sort the whole array.  (Better value, anybody?)

So I conclude that the selection problem should be solved by:
--&gt;  sorting and indexing if n &lt; 60000,
--&gt;  calling SELECT      if n &gt;= 60000.
Note that this method should be the guide for recursive calls as well.


        If the above is correct, then it isn't at all as bad as we 
thought.  We actually COULD USE this algorithm beneficially for 
REASONABLY large n.  (However, note that this analysis only compares 
the numbers of *comparisons* used by the two methods.  Relative 
differences in the amount of other work the algorithms need to do could 
shift the tradeoff point quite a bit in either direction.  I think it 
would be great if somebody in the class would actually test this out.  
Are we IN FACT doing anything practically worthwhile here (other than 
mutilating our brains) ??


On Wed, 31 Jan 1996, Martin Tompa wrote:

&gt; 
&gt; I was somewhat dismayed in lecture today about the fact that the linear time
&gt; selection algorithm only seemed to use fewer comparisons than sorting when n &gt;
&gt; 2 ^ (80d) = 2 ^ 240.  This is obviously totally impractical.  (I hope you
&gt; realized that when I said we wouldn't be doing any useful algorithms in this
&gt; class, I was being facetious.  Although the stress is on elegant algorithms
&gt; with good theoretical analyses, we wouldn't be doing much good if they or
&gt; their techniques weren't also useful in practice.  For most of the algorithms
&gt; we cover, I hope you will find them practical as well as elegant.)
&gt; 
&gt; I gave the analysis more thought, and with some care you can get the constant
&gt; down from 240 to nearly 24.  This comes from two sources:
&gt; 
&gt; (1) A careful analysis shows that d = 2.4 -- the overhead is 1.4n for sorting
&gt; the blocks of size 5, and n+1 for partitioning about x.
&gt; 
&gt; (2) As Yih-Chun suggested, raising the basis of the recurrence beyond 80 pays
&gt; off.  Remember that, in determining the constant c, I had an expression that
&gt; was 80d when n=80 and decreased monotonically to 10d in the limit?  By raising
&gt; the basis, you can get as close to 10d as you like, and it doesn't happen too
&gt; slowly.  Of course, raising the basis also affects d, so there's a tradeoff.
&gt; 
&gt; Putting these together, we end up with an algorithm whose number of
&gt; comparisons is slightly more than 10dn = 24n.  
&gt; 
&gt; The good news is that 24n is a respectable running time, much better than the
&gt; conservative 240n derived in class.  The bad news is that this still only
&gt; beats mergesort when n &gt; 2^24 &gt; 10^7.  But this says more about how very
&gt; efficient an nlogn time algorithm is, rather than how inefficient a 24n time
&gt; algorithm is.  For instance, this 24n time selection algorithm would beat
&gt; insertion sort (in number of comparisons) when n &gt; 48.
&gt; 
&gt; Using blocks of size 15 and more clever tricks, the original 1972 paper by
&gt; Blum, Floyd, Pratt, Rivest, and Tarjan provided an upper bound of 5.43n
&gt; comparisons.  The best upper bound to date is 3n comparisons, by Scho&quot;nhage,
&gt; Paterson, and Pippenger (1976), using quite different techniques.  The best
&gt; lower bound to date for the median problem is 2n comparisons, by Bent and John
&gt; (1985).  
&gt; 

<hr size=4><a name="823279993001">To: cse421@geoduck
Subject: <b>HW4, problem 2</b>
Date: Fri, 02 Feb 1996 08:52:55 PST
From: <b>Martin Tompa &lt;[e-mail]&gt;</b>
</a>


Problem 2 is quite a bit easier than most other problems we ask, so don't look
desperately for a &quot;trick&quot; if you solved it easily.  However, if you're solving
it recursively, you're not doing it nearly as efficiently (or as simply) as
you could.