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

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

<hr size=4><a name="823280499001">To: cs421@geoduck
Subject: <b>elephant humor</b>
Date: Fri, 02 Feb 1996 09:01:35 PST
From: <b>Martin Tompa &lt;[e-mail]&gt;</b>
</a>


This was a small part of one of those very long jokes that you can't wait to
get to the end of.  

&gt;&gt;COMPUTER SCIENTISTS hunt elephants by exercising Algorithm A:
&gt;&gt;      1. Go to Africa.
&gt;&gt;      2. Start at the Cape of Good Hope.
&gt;&gt;      3. Work northward in an orderly manner, traversing the continent
&gt;&gt;         alternately east and west.
&gt;&gt;      4. During each traverse pass,
&gt;&gt;            a. Catch each animal seen.
&gt;&gt;            b. Compare each animal caught to a known elephant.
&gt;&gt;            c. Stop when a match is detected.
&gt;&gt;
&gt;&gt;EXPERIENCED COMPUTER PROGRAMMERS modify Algorithm A by placing a known
&gt;&gt;elephant in Cairo to ensure that the algorithm will terminate.
<hr size=4><a name="823307984001">To: cse421@geoduck
Subject: <b>HW4, problem 5</b>
Date: Fri, 02 Feb 1996 16:39:35 PST
From: <b>Martin Tompa &lt;[e-mail]&gt;</b>
</a>


The book talks about THE weighted median, but a few students pointed out that
it may not be unique, for instance, if w1 = 1/6, w2 = 2/6, and w3 = 3/6.  It's
not too hard to prove that there will either be 1 or 2 weighted medians.  If
there happen to be two, let's agree that THE weighted median is the larger of
those two, to agree with the way we've disambiguated the ordinary median in
the case when there are an even number of elements.
<hr size=4><a name="823468427001">Date: Sun, 4 Feb 1996 13:13:20 -0800
From: <b>claym@wolf (Michael Clay)</b>
To: [e-mail]
Subject: <b>Does problem 3 suck or am I just dense?</b>
Cc: claym@wolf
</a>

Seems like most of the homework is straightforward, albeit a bit
beyond lengthy, except problem 3.

All my attempts at a solution to #3 so far are convoluted and seem to run
in O(lg**2 n) time.  I must be missing something, either obvious or obscure.
Any hints that would steer me in the right direction without totally
giving away the solution would be greatly appreciated.

Thanks,
	Michael ([e-mail])
	(But post your answers to cs421 distribution.)
<hr size=4><a name="823472207001">To: cse421@geoduck
Subject: <b>HW4, problem 3</b>
Date: Sun, 04 Feb 1996 14:16:37 PST
From: <b>Martin Tompa &lt;[e-mail]&gt;</b>
</a>


Given that you're after an O(log n) solution, something to shoot for
is to throw away about half the problem every constant number of
steps.  

Personally, I didn't find problem 5 straightforward, and I know some
students are having trouble with problem 1.

------- Forwarded Message

Date:    Sun, 04 Feb 1996 13:13:20 -0800
From:    claym@wolf (Michael Clay)
To:      [e-mail]
cc:      claym@wolf
Subject: Does problem 3 suck or am I just dense?

Seems like most of the homework is straightforward, albeit a bit
beyond lengthy, except problem 3.

All my attempts at a solution to #3 so far are convoluted and seem to run
in O(lg**2 n) time.  I must be missing something, either obvious or obscure.
Any hints that would steer me in the right direction without totally
giving away the solution would be greatly appreciated.

Thanks,
	Michael ([e-mail])
	(But post your answers to cs421 distribution.)

------- End of Forwarded Message

<hr size=4><a name="823723004001">Date: 7 Feb 1996 11:55 PST
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: cse421@cs
Subject: <b>wednesday office hour CANCELED</b>
</a>

I have to cancel my office hour today.  I'll try to be available
tomorrow or friday to compensate; details later.
<hr size=4><a name="823806374001">To: cse421@geoduck
Subject: <b>HW5, problem 2(a)</b>
Date: Thu, 08 Feb 1996 11:05:56 PST
From: <b>Martin Tompa &lt;[e-mail]&gt;</b>
</a>


A student pointed out that we didn't discuss ties in the greedy method, that
is, what the method does when pqr = qrs.  To disambiguate the problem, you may
assume in part (a) that pqr &lt; qrs, and just give the necessary and sufficient
conditions assuming this inequality is true.  This ensures that there are no
ties, and also eliminates the need to discuss the completely dual case when
pqr &gt; qrs.  In part (b), make sure you choose values that satisfy pqr &lt; qrs.  
<hr size=4><a name="823819895001">Date: Thu, 8 Feb 1996 14:51:23 -0800
From: <b>aberman (Andrew P. Berman)</b>
To: cse421
Subject: <b>Average Homework Grades</b>
</a>


I have not included the grades of some people whom I suspect have dropped
the course.  I also only included the grades for homeworks submitted.  So
these averages (like all averages) must be taken with a grain of salt.

Hw1:  19 out of 25
Hw2:  22 out of 25
Hw3:  22 out of 30

Andy





<hr size=4><a name="823885094001">Date: 9 Feb 1996 08:55 PST
From: <b>Larry Ruzzo &lt;[e-mail]&gt;</b>
To: cse421@cs
Subject: <b>office hours</b>
</a>

To make up for my canceled office hour wednesday, I'll be available
intermittently today for questions.  I'm tied up from 12:30 - 2:00,
and need to be in and out a bit during the rest of the day, but will
be happy to answer questions if I'm in.
<hr size=4><a name="823896264001">To: cse421@geoduck
Subject: <b>Cocke, Kasami, Younger algorithm</b>
Date: Fri, 09 Feb 1996 12:04:07 PST
From: <b>Martin Tompa &lt;[e-mail]&gt;</b>
</a>


I mentioned in class that there is another dynamic programming algorithm that
is extremely similar in form to the one we are looking at now for matrix chain
product and polygon triangulation.  It is a cubic algorithm for testing
context-free language membership.  If you are interested in seeing it, there
is a PostScript writeup in the following URL:

  http://www.cs.washington.edu/education/courses/322/94a/cky.ps

I have a feeling that there should be some unification of that problem and
polygon triangulation, just because of the similarity of these algorithms, but
I have not discovered it.  If you have ideas along these lines, I'd love to
hear them.
<hr size=4><a name="823911481001">Date: Fri, 9 Feb 1996 16:17:50 -0800 (PST)
From: <b>Robert Oganyan &lt;[e-mail]&gt;</b>
To: [e-mail]
Subject: <b> mailing list</b>
</a>


Please remove me from the mailing list

Robert

<hr size=4><a name="824085721001">Date: Sun, 11 Feb 1996 16:41:38 -0800 (PST)
From: <b>&quot;D. Godon&quot; &lt;[e-mail]&gt;</b>
To: Martin Tompa &lt;[e-mail]&gt;
Cc: [e-mail]
Subject: <b>Re: Cocke, Kasami, Younger algorithm</b>
</a>


On problem 3a, can we assume k is an integer?  If not, it would seem part 
a and b are the same.

Thanks
<hr size=4><a name="824143936001">To: cse421@geoduck
Subject: <b>HW5, problem 3a</b>
Date: Mon, 12 Feb 1996 08:52:02 PST
From: <b>Martin Tompa &lt;[e-mail]&gt;</b>
</a>


Yes, you should assume k is an integer.

------- Forwarded Message

Date:    Sun, 11 Feb 1996 16:41:38 -0800
From:    &quot;D. Godon&quot; &lt;[e-mail]&gt;
To:      Martin Tompa &lt;[e-mail]&gt;
cc:      [e-mail]
Subject: Re: Cocke, Kasami, Younger algorithm


On problem 3a, can we assume k is an integer?  If not, it would seem part 
a and b are the same.

Thanks

------- End of Forwarded Message

<hr size=4><a name="824151375001">To: cse421@geoduck
Subject: <b>next reading assignment</b>
Date: Mon, 12 Feb 1996 10:56:07 PST
From: <b>Martin Tompa &lt;[e-mail]&gt;</b>
</a>


Read the introduction to Chapter 26, and all of Section 26.2.
<hr size=4><a name="824157655001">Date: Mon, 12 Feb 1996 12:40:26 -0800
From: <b>aberman@hobbes (Andrew Berman)</b>
To: cse421@hobbes
Subject: <b>Average for HW#4</b>
</a>


40

Andy
<hr size=4><a name="824319697001">To: [e-mail]
Subject: <b>Mistake in Homework Grading</b>
Date: Wed, 14 Feb 1996 09:41:25 PST
From: <b>Andrew Berman &lt;[e-mail]&gt;</b>
</a>



HW#4 (the one we just gave back)

Problem 10-1 Largest i numbers in sorted order:

I took off credit for those who gave the answer n lg n.
Both n lg n and n lg n + i are legitimate answers---n lg n is actually
the better answer.

What *is* still wrong is claiming 'i' is a constant--you won't get any
points back if you did that. 

However, if you wrote n lg n but did not claim 'i' was a constant, please
bring your homework in either to Friday's class or to my office hours
to get credit for your answer.

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="824799498001">To: cse421@geoduck
Subject: <b>HW6 on the web</b>
Date: Mon, 19 Feb 1996 22:58:06 PST
From: <b>Martin Tompa &lt;[e-mail]&gt;</b>
</a>


HW6 will be handed out in Wednesday's lecture, due a week later.  It
is on the web, if you want to get a headstart.

<hr size=4><a name="825006052001">Date: Thu, 22 Feb 1996 08:20:09 -0800
From: <b>aberman@hobbes (Andrew Berman)</b>
To: cse421@hobbes
Subject: <b>Office Hours *CANCELLED* This Monday and Tuesday</b>
</a>


Sorry, but I'm gonna be out for a week starting today and lasting until
next Thursday.

Andy
<hr size=4><a name="825026870001">To: cse421@geoduck
Subject: <b>HW6, #2 (Warning: this message contains a hint.)</b>
Date: Thu, 22 Feb 1996 14:07:45 PST
From: <b>Martin Tompa &lt;[e-mail]&gt;</b>
</a>


One student, stuck on problem 2, asked for an idea of how to start.  Think
about finding the edit distance between the prefixes x[1..i] and y[1..j].
<hr size=4><a name="825271119001">Date: Sun, 25 Feb 1996 09:57:56 -0800 (PST)
From: <b>Eva Marie Allen &lt;[e-mail]&gt;</b>
To: Algorithms &lt;[e-mail]&gt;
Subject: <b>last problem</b>
</a>

I have a problem.  I need to prove that Warshall' algorithm works, and I 
don't believe it does.  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.  The implication of the algorithm is that if d(i,j) is 1, then 
either d(i,k) or d(k,j) is one.  I do not find this to be true.  The book 
SAYS it is true, so I assume that I am looking at this the wrong way.  
How DOES this work?

Thanks,

Eva

*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
Eva Marie Allen                      |  Though it cost all you have, get 
[e-mail]             |  understanding.  Esteem her, and she
UW Computer Science Department       |  will exalt you; embrace her, and she