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

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

In the beautiful city of Seattle     |  will honor you.              Solomon
*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
        Only 182 days until my wedding! (8/25/96)

<hr size=4><a name="825283302001">Date: 25 Feb 1996 13:12 PST
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: Eva Marie Allen &lt;[e-mail]&gt;
Subject: <b>Re: last problem</b>
Cc: Algorithms &lt;[e-mail]&gt;
</a>

  &gt; ... we need to take the min of d(i,j) and d(i,k) + 
  &gt; d(k,j), well, if d(i,j) is zero, and the sum of the rest is positive, 
  &gt; then the min is zero.  Right?  So I can easily see creating an all zero 
  &gt; matrix.  The implication of the algorithm is that if d(i,j) is 1, then 
  &gt; either d(i,k) or d(k,j) is one.  I do not find this to be true.  The book 
  &gt; SAYS it is true, so I assume that I am looking at this the wrong way.  
    ^^^^
    where?

edge weights/distances can be positive, negative or zero.  zero
means a free trip from point i to point j; if that's cheaper than
going via Kansas City, then that's what you should do.  E.g., bus
fares between stops  in downtown seattle would give a matrix full of
zero's.  [Note that in the transitive closure algorithm on the same
page, zero means NO path from i to j, but it's not computed the same
way.]
<hr size=4><a name="825355795001">To: cse421@geoduck
Subject: <b>last problem</b>
Date: Mon, 26 Feb 1996 09:29:39 PST
From: <b>Martin Tompa &lt;[e-mail]&gt;</b>
</a>


To amplify on Larry's answer a bit, Floyd's algorithm (for shortest paths) and
Warshall's algorithm (for transitive closure) are very similar in spirit, but
not at all identical.

  &quot;It we need to take the min of d(i,j) and d(i,k) + 
   d(k,j), well, if d(i,j) is zero, and the sum of the rest is positive, 
   then the min is zero.  Right?  So I can easily see creating an all zero
   matrix.&quot;   

This is a statement about the shortest paths algorithm.  What it says is that,
once d(i,j) is zero, it will never go positive again.  (Actually, this is true
more generally: no matter what value d(i,j) has, it will never later
increase.)  But it doesn't follow from this that the algorithm will
necessarily create an all zero matrix.  In general, it won't.

  &quot;The implication of the algorithm is that if d(i,j) is 1, then 
   either d(i,k) or d(k,j) is one.  

This is a statement about the transitive closure algorithm, although it should
say &quot;if d(i,j) changes from 0 to 1, then either d(i,k) or d(k,j) is one.&quot;  In
class we never talked about the transitive closure (Warshall's) variant.
<hr size=4><a name="825358601001">Date: Mon, 26 Feb 1996 10:16:23 -0800 (PST)
From: <b>Michael Clay &lt;[e-mail]&gt;</b>
To: Martin Tompa &lt;[e-mail]&gt;
cc: [e-mail]
Subject: <b>Re: HW6, #2 (Warning: this message contains a hint.)</b>
</a>

Where the text says &quot;describe an algorithm&quot;,
how detailed a description are we supposed to
give?  Please specify _exactly_ what you do
and do not expect in the description.

Thanks,
	Michael ([e-mail])
<hr size=4><a name="825359061001">To: cse421@geoduck
Subject: <b>&quot;describe an algorithm&quot;</b>
Date: Mon, 26 Feb 1996 10:24:10 PST
From: <b>Martin Tompa &lt;[e-mail]&gt;</b>
</a>


Ideally this should be done in the style of the textbook: a precise algorithm
described in pseudocode (see e.g. Matrix-Chain-Order or LCS-Length), plus a
short English description of how the algorithm works in general and any tricky
portions of it in particular.  If correctness of your algorithm isn't obvious,
part of this description should convince the reader of its correctness.

------- Forwarded Message

Date:    Mon, 26 Feb 1996 10:16:23 -0800
From:    Michael Clay &lt;[e-mail]&gt;
To:      Martin Tompa &lt;[e-mail]&gt;
cc:      [e-mail]
Subject: Re: HW6, #2 (Warning: this message contains a hint.)

Where the text says &quot;describe an algorithm&quot;,
how detailed a description are we supposed to
give?  Please specify _exactly_ what you do
and do not expect in the description.

Thanks,
	Michael ([e-mail])

------- End of Forwarded Message

<hr size=4><a name="825405471001">To: cse421
Subject: <b>space</b>
Date: Mon, 26 Feb 1996 23:17:43 PST
From: <b>Martin Tompa &lt;[e-mail]&gt;</b>
</a>


A student asked how to measure the space required by an algorithm.

Generally, the space is the maximum number of words of memory needed
by the algorithm at any one time.  Most dynamic programming algorithms
need much more space than the space used by the inputs and outputs.
For instance, matrix-chain-order needs space Theta(n^2) for the m and
s tables, even though the input and output only take up Theta(n)
space.

<hr size=4><a name="825407777001">To: cse421
Subject: <b>HW6, #4</b>
Date: Mon, 26 Feb 1996 23:56:02 PST
From: <b>Martin Tompa &lt;[e-mail]&gt;</b>
</a>


On problem 4 of the homework sheet, I gave the following useful bit of
advice:

&quot;Note that what is computed in line 6 during iteration k is not
exactly the value d_{ij}^(k).&quot;

One of the students has convinced me that this advice is ... uh
... err ... not, strictly speaking, exactly, completely true.

But no matter: if you believe the advice, you will be led to the proof
that I had in mind.  If you don't believe the advice, you will be led
to the proof this student came up with.

This is what is so great about teaching: no matter how often you teach
one of these classical results, each time you learn something new
about it, often from students.
<hr size=4><a name="825893064001">To: cse421@geoduck
Subject: <b>details on Chapter 36 reading assignment</b>
Date: Sun, 03 Mar 1996 14:44:14 PST
From: <b>Martin Tompa &lt;[e-mail]&gt;</b>
</a>


You should read the whole chapter, but you can skim the following
parts:

from Lemma 36.1 to the end of Section 36.1
the proofs of Theorems 36.9 and 36.10

The main technical meat that we want to cover is in Section 36.5, but
you need some of the motivation and definitions from earlier in the
chapter to make sense of this.  On a first reading, I would strongly
recommend delaying the reading from Lemma 36.5 to the end of Section
36.3 until you've finished the chapter.  These are important results
and proofs, but you will have trouble understanding them until you get
more experience with reducibilities in Section 36.5.

<hr size=4><a name="825916218001">Date: 3 Mar 1996 21:03 PST
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: cse421@cs
Subject: <b>24-1(a)</b>
</a>

  &gt; Please define a second best minimum spanning tree: suppose there are 
  &gt; two MSTs-- does one qualify as a 2'nd best? Or do you want to see the 
  &gt; one with the second-smallest DISTINCT weight?

I'm willing to credit a good solution to the problem under either
interpretation.  Howeverm, I think the book intended, and I think it
will be easier to prove, the first interpretation: if there happen
to be several spanning trees with weight equal to the minimum, then
T can be any of them, and any of the others can be taken as the &quot;2nd
best&quot;.
<hr size=4><a name="825917703001">Date: 3 Mar 1996 21:33 PST
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
Subject: <b>Re: 24-1(a)</b>
To: cse421@cs
</a>

PS: In line with the previous message, you should change &quot;the
second-best&quot; to &quot;a second-best&quot; in part (c), in the case where the
second-best is not unique.
<hr size=4><a name="825917904001">Date: 3 Mar 1996 21:36 PST
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: cse421@cs
Subject: <b>HW7, 17.2-4</b>
</a>


  &gt; Could I make the assumption that the longest distance possible between 
  &gt; two gas stations is n miles, the same miles as the professor's car can run 
  &gt; with a full tank of gas?  

Yes, you may assume there is no section of road longer than n miles
without a gas station.
<hr size=4><a name="825969234001">Date: 4 Mar 1996 11:44 PST
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: cse421@cs
Subject: <b>HOMEWORK REVISION</b>
</a>

Problem 24-1(a) is trickier than I had first realized.  It's a good
test of your understanding of min spanning trees, and not beyond
what I think you can do, but the assignment seems meaty enough
without it.  So I'm making part (a) EXTRA CREDIT.  Parts (b) and (c)
are STILL REQUIRED, and of course you can use the result stated in
part (a)  even if you don't prove it.

****** WARNING:  HINT FOLLOWS *******



In case you want a start on the extra credit part, here's a hint  -- 








Let T1 be a min spanning tree.
Let T2 be a 2nd best spanning tree with as many edges in common with
T1 as possible.
<hr size=4><a name="825992615001">Date: 4 Mar 1996 18:20 PST
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: cse421@cs
Subject: <b>OFFICE HOUR CHANGE</b>
</a>

Unfortunately, I will be unavailable during my normal office hour,
2:30-3:30 tomorrow, Tuesday 3/5.  However, I should be in most of
the morning, and from 1:30 to 2:30.  Sorry for the inconvenience.
<hr size=4><a name="826054579001">Date: 5 Mar 1996 10:59 PST
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: cse421@cs
Subject: <b>Re: HW 7, 17-2.2  (***CAUTION; HINT BELOW***)</b>
</a>


  &gt; 	I am have some trouble coming up with an algorithm that runs in 
  &gt; O(nW) for this problem.  I can see using variations of Floyd-Warshall or 
  &gt; Matrix Chain Order, but these seem to take O(n**3).  I haven't been able 
  &gt; to come up with a variation of Longest Common Subsequence that works.  Is 
  &gt; there something I am missing?

(***CAUTION; HINT BELOW***)

The key issue with dynamic programming is that an optimal solution
to the problem can be built out of optimal solutions to related
smaller problems.  The smaller problems often arise by fixing in
various ways some of the choices that ultimately must be made.
E.g., in matrix parenthesization, there was a choice as to where the
outermost parentheses go, and assuming they go at position k,
certain subproblems arise.  You don't know k, but can consider all
possibilities.  In the string edit problem you did for homework,
there's a choice as to the last edit operation used to build the
output string from the input string, and assuming it was, say, a
copy, then a certain subproblem  arises; assuming it was a twiddle,
a different subproblem arises, etc.  Again, you don't know which is
the right choice to make for the last operation, so you consider
them all.  LCS is similar.  

What are the choices in Knapsack?  If you fix one, does it give rise
to a smaller knapsack-like problem?  Which choice should you fix?
How many ways are there to fix it?  Can you tell what the right
choice is?  If not, can you consider all possibilities in some
systematic way?

If you're stuck, I always recommend playing with some examples.
Make up some simple instances of the problem with 1 object; what's
it's solution?  Vary W; how does the solution change?  Add another
object or 3, etc.  There's of course some danger that your examples
will be too simple or too specialized or that you will leap to the 
wrong conclusion from them, but that's what proofs are for, and
concrete examples often help crystalize your thinking.
<hr size=4><a name="826149018001">To: cse421@geoduck
Subject: <b>evaluations Friday</b>
Date: Wed, 06 Mar 1996 13:50:08 PST
From: <b>Martin Tompa &lt;[e-mail]&gt;</b>
</a>


Don't forget your #2 pencils on Friday.  We'll take the last 10 minutes of
class to do student evaluations.
<hr size=4><a name="826247983001">To: cse421@geoduck
Subject: <b>HW8 (just kidding)</b>
Date: Thu, 07 Mar 1996 17:19:16 PST
From: <b>Martin Tompa &lt;[e-mail]&gt;</b>
</a>


Here are some exercises on Chapter 36 to help you study for the final.  You
don't need to turn these in.

p. 923, 36.1-1
p. 924, 36.1-4
p. 929, 36.2-5
p. 938, 36.3-1
p. 960, 36.5-1
<hr size=4><a name="826326241001">Date: Fri, 8 Mar 1996 15:03:37 -0800
From: <b>aberman@hobbes (Andrew Berman)</b>
To: cse421@