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

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

> corrected version of the problem is correct). However, one should note 
> that this is not the case when n >= 2. (Proof: Suppose there exists 
> function g(x) st n^g(x) = 0 for all n >= 2. Then g(n) gives us a 
> base n logarithm of zero.) It therefore follows that either 0 is not in 
> O(n^k) [contradiction of definition on page 26] or it is possible to take 
> logarithms of zero.
> 
> 
> +---- Yih-Chun Hu (finger:[e-mail]) ----------------------+
> | http://www.cs.washington.edu/homes/yihchun     [e-mail] |
> | http://weber.u.washington.edu/~yihchun         [e-mail]  |
> +--------------------------------------------------------------------------+
> 
> 
> ------- End of Forwarded Message
> 
> 

+---- Yih-Chun Hu (finger:[e-mail]) ----------------------+
| http://www.cs.washington.edu/homes/yihchun     [e-mail] |
| http://weber.u.washington.edu/~yihchun         [e-mail]  |
+--------------------------------------------------------------------------+


------- End of Forwarded Message

<hr size=4><a name="821449363001">Date: 12 Jan 1996 04:21 PST
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: cse421@cs
Subject: <b>HW#2</b>
</a>

HW#2 will be passed out in class today, and is also on the web, for
those of you who want to get a start on it this morning. 
<hr size=4><a name="821473663001">To: cse421@cs
Subject: <b>TA Office Hours</b>
Date: Fri, 12 Jan 1996 11:07:34 PST
From: <b>Andrew Berman &lt;[e-mail]&gt;</b>
</a>


I have scheduled Office Hours for Monday and Tuesday, 9:30-10:30 am
in room 326a.

Andy




_______________________________________________________________________________
|    Andrew P. Berman     |Dept. Of Computer Science, University Of Washington|
|[e-mail]|  http://www.cs.washington.edu/homes/aberman       |
|_________________________|___________________________________________________|

<hr size=4><a name="821477066001">To: cse421@cs
Subject: <b>Office Hours Conflict/Change</b>
Date: Fri, 12 Jan 1996 12:04:18 PST
From: <b>Andrew Berman &lt;[e-mail]&gt;</b>
</a>


I've just been alerted that my Monday morning office hours conflicts with
a class which many students may be taking. Henceforth, my Monday office hours
are from 11:30 to 12:20.

New Schedule:  Monday 11:30-12:30, Tuesday 9:30-10:30


Andy



_______________________________________________________________________________
|    Andrew P. Berman     |Dept. Of Computer Science, University Of Washington|
|[e-mail]|  http://www.cs.washington.edu/homes/aberman       |
|_________________________|___________________________________________________|

<hr size=4><a name="822003133001">Date: Thu, 18 Jan 1996 14:11:51 -0800 (PST)
From: <b>Joseph Heitzeberg &lt;[e-mail]&gt;</b>
To: [e-mail]
Subject: <b>421 Book</b>
</a>

421 -

  I forgot my 421 book in Sieg 326 today, Did anyone happen to see it?  
If so please let me know, I'de really appreciate it (because it's so 
ex$pen$ive)

Thanks,
Joe Heitzeberg
<hr size=4><a name="822191620001">Date: 20 Jan 1996 18:30 PST
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: cse421@cs
Subject: <b>sorting animations</b>
</a>

If any of you happen to have access to a web browser supporting Java
applets, you might enjoy seeing their sorting demo applet:
http://java.sun.com/applets/applets/SortDemo/example1.html
<hr size=4><a name="822327389001">Date: 22 Jan 1996 07:39 PST
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: cse421@cs
Subject: <b>Re: hw questions...</b>
</a>

  &gt; When the book asks for us to 'argue' something does it want a formal 
  &gt; proof or does it want a intuitive explanation?  I'm specifically 
  &gt; referring to the first two questions. 

I take &quot;argue&quot; and &quot;prove&quot; to be synonymous.

on problem 8.4-4, the requested analysis is the analysis of the
expected (average) time for randomized quicksort (i.e., quicksort
with random selection of pivot), modified as suggested in the
problem.  We'll give partial credit for correct analysis of
worst-case time of this variant of *deterministic* quicksort with
exact (linear time) median.  Using a recursion tree to analyze the
recurrence might be easiest in this case.
<hr size=4><a name="822352515001">Date: 22 Jan 1996 15:11 PST
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: cse421@cs
Subject: <b>Reading assignment</b>
</a>

here's an updated reading assignment, for material up to and
including today's lecture.  (You'll get a hardcopy of this with your
next homework assignment.)

    \begin{itemize}
        \item Ch. 3 (Summations): We've seen examples of most of
	    the techniques in this chapter by now.  This would
	    be a good time to read it if you haven't already.
        \item Ch. 4 (Recurrences): ditto, except you may skip 4.4.
        \item Ch. 8 (Quicksort): read all of it.
    \end{itemize}
<hr size=4><a name="822353495001">To: cse421@geoduck
Subject: <b>further reading</b>
Date: Mon, 22 Jan 1996 15:31:13 PST
From: <b>Martin Tompa &lt;[e-mail]&gt;</b>
</a>


Wednesday we'll dive into Chapter 10.  Read the whole chapter, concentrating
on 10.3.

The remaining divide-and-conquer algorithm that was on the syllabus is the
fast Fourier transform, from Chapter 32.  We will skip this for the moment,
and possibly return to it later in the quarter.  

So the next topic after Chapter 10 is Chapter 16 (following the syllabus).
<hr size=4><a name="822436650001">Date: 23 Jan 1996 14:30 PST
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: cse421@cs
Subject: <b>problem 8.4-4</b>
</a>

a student pointed out that many of you looked at a version of
quicksort in 326 that switched to doing insertion sort when the
problem size was less than some small k, so in total you'll do at
least n/k insertion sorts on small subproblems of size at most k.
Although related, this is NOT the version that you are to analyze in
8.4-4.  Rather than switching to insertion sort at the bottom of the
recursion, 8.4-4 says DO NOTHING when the subproblems are of size
&lt;=k; just return, leaving that subproblem unsorted.  Patch up ALL of
these small unsorted subproblems with ONE global insertion sort at
the end.  [This has a slight advantage in practice, since you only
setup &amp; run the insertion-sort loops once, rather than n/k times.]
<hr size=4><a name="822438053001">To: cse421@geoduck
Subject: <b>proofs of correctness</b>
Date: Tue, 23 Jan 1996 15:00:43 PST
From: <b>Martin Tompa &lt;[e-mail]&gt;</b>
</a>


A student asked for suggestions or models of how to do proofs of correctness
of algorithms.  In particular &quot;Stooge sort&quot; and Quicksort' on the homework ask
for correctness proofs.  

In both of these cases, the fact that a problem is being reduced to smaller
problems (either by recursion or by iteration) suggests a proof by induction
on the size of the problem.  Using induction, I think you can come up with a
reasonably rigorous proof in each case.  

In the case of Quicksort', there are at least two ways of applying induction:
you can either appeal to the induction hypothesis once per iteration (for the
recursive call), or you can have exactly two appeals to the induction
hypothesis (one for the first recursive call, and one for what's accomplished
together by all iterations after the first).  
<hr size=4><a name="822513459001">Date: Wed, 24 Jan 1996 11:57:33 -0800
From: <b>aberman@hobbes (Andrew Berman)</b>
To: cse421@hobbes
</a>

Proof Tips: CSE 421

Here are some tips to writing good readable proofs.  This document is not a 
complete guide to proofwriting (we'd like to one of those for ourselves). We
hope, however, that this document will help people who are a little unsure of
what a good proof looks like.


1) Proofs are communications:
A proof is not an abstract mathematical construct.  It is a very
concrete and specific communication.  Specifically, you
are communicating to others that they should believe something.  Most
of the points in this note follow from this paradigm.


2)  Include Commentary
Sometimes students get the idea that if it isn't an equation,  it shouldn't be
in the proof.  That's not true.  While a comment doesn't substitute for a 
logical inference, it can help the reader understand what logical inference
you are using.  


3) Organization 
A good proof will be easy to read and understand.  Organization helps.  Think
of the proof as a path for the reader to follow. Tell the reader what the goals
or subgoals are, and then show the reader how these goals are reached.
Here's a simple example:

  To prove that X = Z, we will first show that X = Y, and then we will
  show Y=Z. 
    1) We show that X = Y by induction
	 ....
    2) We now show that Y = Z by contradiction....

  Since X = Y from (1) and Y = Z from (2), by transitivity, X = Z.


4) Label things:
If you are going to use a standard method such as induction, you must use the
conventions of the method.  In an inductive proof, that includes labeling the
base case, inductive hypothesis and inductive steps as such.  


5)  Don't use the &quot;reduction to 1=1&quot; strategy.
Strategies such as induction are useful because there is a guarantee that if
you use the strategy correctly then you will wind up with a correct proof. One
strategy sometimes used to prove X=Y is to start off with X=Y and reduce the
equation to something trivially correct, such as 1=1.  This strategy is invalid
because it does not offer the guarantee that using it correctly results in a
proof. For example:

                1 = -1
                1^2 = (-1)^2
                1 = 1   QED

The squaring step is not reversible which is why this doesn't work.  Yet the 
strategy does not flag this problem.  If you are thinking in these terms, try 
starting from 1=1 and deducing X=Y.  Then you are using the valid strategy of
starting with something true and using legitimate mathematical operations which
maintain truthfulness.


7) Look at boundary cases:
Is what you are saying true for N=0? How about N=1? what about as N-&gt;inf? What
about negative or non-integer N? Several problems of this sort cropped up in
question 2.2-2, and will probably crop up in later problems as well.  If you
see something like this, you can ask us about it, or, you can state that you
are limiting your domain to positive N, or integer N, or something like that.
It's far better to limit the scope of your proof than to write something false. 

8) Don't skip steps:
It can be hard to know how much detail you should put down,
but here's some examples of how to reduce one equation to another:

	Too Little:
		[2^(k+1)]/2 = N
		k log (2) = log(N)
	        k	  = log(N)

	Minimimally acceptable:
		[2^(k+1)]/2 = N
		2^(k)	  = N
		k	  = log(N)
	Better:
		[2^(k+1)]/2]= N
		2^(k)	  = N
		log(2^(k))=log(N) [base 2]
		k	  = log(N)

Note that the first two examples have the same number of lines.  However,
the first one had a leap between the first two lines which would force
the reader to puzzle over it for a while.  In general, limit each new line
to one mathematical operation.


9) Try to keep it compact:
Part of clarity is compactness.  If your proof starts to meander and look more
like an essay, try rewriting it in fewer sentences. If you can't rewrite it and
it still meanders, perhaps you're missing some key element.  Compactness is not
in conflict with point (8) as long as you remember that clarity is the overall
goal.  Either too much or too little verbiage can be detrimental.


10) A Note About Inductive Proofs:
	I noticed that some people don't use the correct base case.
Consider the statement of the first problem:
	T(N) = 2 if N=2
	     = 2T(N/2) + N if N &gt; 2 
	Prove that T(N) = N log N.

The base case is N=2, not N=4.  I think perhaps since N=2 is listed separately
in the description of T(N), people may be worried that the induction &quot;might not
work&quot; that far.  But it does--that's the whole point of having the base case
and of listing it separately in the original description. In general, try to
make the proofs as encompassing as possible.
<hr size=4><a name="822525184001">Date: 24 Jan 1996 15:06 PST