http:^^www.cs.washington.edu^education^courses^421^96w^bboard.shtml
来自「This data set contains WWW-pages collect」· SHTML 代码 · 共 1,546 行 · 第 1/5 页
SHTML
1,546 行
Date: Mon, 02 Dec 1996 17:40:14 GMTServer: NCSA/1.4.2Content-type: text/html<html> <head><title>CSE 421 Bboard/Mail Log</title></head><body><h1>CSE 421 Formal Models<br> Bboard/Mail Log<br> Winter 1996</h1>This page contains a log of all email sent to the CSE421 classmailing list <tt>cse421@cs</tt>. We will use this list forannouncements of general interest to the class. Students shouldalso feel free to use it to ask questions, post information, orinitiate discussions of general interest to the class. Of course,questions or comments that don't seem of general interest can bedirected to the TA (<tt>aberman@cs</tt>) or instructors(<tt>ruzzo@cs</tt> or <tt>tompa@cs</tt>), instead. <p> Following usual Internet conventions, administrative requestsconcerning the mailing list itself, such as add/delete/addresschange requests, should be addressed to <tt>cse421-request@cs</tt>.<h2>Index of Messages</h2>(Latest message Friday, 15-Mar-96 14:49:40 PST.)<p><ul><li><a href=#820891592001><tt> 5 Jan 96 ruzzo@cs ______ cse421 mailing list</tt></a><li><a href=#821123595001><tt> 8 Jan 96 eallen@cs _____ study group</tt></a><li><a href=#821137145001><tt> 8 Jan 96 eallen@cs _____ Re: study group</tt></a><li><a href=#821150788001><tt> 8 Jan 96 ruzzo@cs ______ Homework #1 Bugs & Clarifications.</tt></a><li><a href=#821167943001><tt> 8 Jan 96 yihchun@u _____ Re: Homework #1 Bugs & Clarifications.</tt></a><li><a href=#821231741001><tt> 9 Jan 96 tompa@cs ______ HW1, problem 3</tt></a><li><a href=#821232978001><tt> 9 Jan 96 tompa@cs ______ Re: HW1, problem 3</tt></a><li><a href=#821449363001><tt>12 Jan 96 ruzzo@cs ______ HW#2</tt></a><li><a href=#821473663001><tt>12 Jan 96 aberman@cs ____ TA Office Hours</tt></a><li><a href=#821477066001><tt>12 Jan 96 aberman@cs ____ Office Hours Conflict/Change</tt></a><li><a href=#822003133001><tt>18 Jan 96 joeh@cs _______ 421 Book</tt></a><li><a href=#822191620001><tt>20 Jan 96 ruzzo@cs ______ sorting animations</tt></a><li><a href=#822327389001><tt>22 Jan 96 ruzzo@cs ______ Re: hw questions...</tt></a><li><a href=#822352515001><tt>22 Jan 96 ruzzo@cs ______ Reading assignment</tt></a><li><a href=#822353495001><tt>22 Jan 96 tompa@cs ______ further reading</tt></a><li><a href=#822436650001><tt>23 Jan 96 ruzzo@cs ______ problem 8.4-4</tt></a><li><a href=#822438053001><tt>23 Jan 96 tompa@cs ______ proofs of correctness</tt></a><li><a href=#822513459001><tt>24 Jan 96 aberman@hobbes Proof Tips</tt></a><li><a href=#822525184001><tt>24 Jan 96 ruzzo@cs ______ expected time for insertion sort</tt></a><li><a href=#822560087001><tt>25 Jan 96 ruzzo@cs ______ Re: (CSE421) Problems using induction to</tt></a><li><a href=#822622279001><tt>25 Jan 96 tompa@cs ______ Re: (CSE421) Problems using induction to</tt></a><li><a href=#822938502001><tt>29 Jan 96 tompa@cs ______ CSE 421 lecture cancelled today</tt></a><li><a href=#823131737001><tt>31 Jan 96 tompa@cs ______ more on the (in)efficiency of the select</tt></a><li><a href=#823214482001><tt> 1 Feb 96 eallen@cs _____ problem 5</tt></a><li><a href=#823224536001><tt> 1 Feb 96 michael@u _____ Tutors for 421?</tt></a><li><a href=#823225857001><tt> 1 Feb 96 wbarrett@cs ___ So HOW BAD IS IT, Really?</tt></a><li><a href=#823279993001><tt> 2 Feb 96 tompa@cs ______ HW4, problem 2</tt></a><li><a href=#823280499001><tt> 2 Feb 96 tompa@cs ______ elephant humor</tt></a><li><a href=#823307984001><tt> 2 Feb 96 tompa@cs ______ HW4, problem 5</tt></a><li><a href=#823468427001><tt> 4 Feb 96 claym@wolf ____ Does problem 3 suck or am I just dense?</tt></a><li><a href=#823472207001><tt> 4 Feb 96 tompa@cs ______ HW4, problem 3</tt></a><li><a href=#823723004001><tt> 7 Feb 96 ruzzo@cs ______ wednesday office hour CANCELED</tt></a><li><a href=#823806374001><tt> 8 Feb 96 tompa@cs ______ HW5, problem 2(a)</tt></a><li><a href=#823819895001><tt> 8 Feb 96 aberman@cs ____ Average Homework Grades</tt></a><li><a href=#823885094001><tt> 9 Feb 96 ruzzo@cs ______ office hours</tt></a><li><a href=#823896264001><tt> 9 Feb 96 tompa@cs ______ Cocke, Kasami, Younger algorithm</tt></a><li><a href=#823911481001><tt> 9 Feb 96 ogan@cs _______ mailing list</tt></a><li><a href=#824085721001><tt>11 Feb 96 dgodon@u ______ Re: Cocke, Kasami, Younger algorithm</tt></a><li><a href=#824143936001><tt>12 Feb 96 tompa@cs ______ HW5, problem 3a</tt></a><li><a href=#824151375001><tt>12 Feb 96 tompa@cs ______ next reading assignment</tt></a><li><a href=#824157655001><tt>12 Feb 96 aberman@hobbes Average for HW#4</tt></a><li><a href=#824319697001><tt>14 Feb 96 aberman@cs ____ Mistake in Homework Grading</tt></a><li><a href=#824799498001><tt>19 Feb 96 tompa@cs ______ HW6 on the web</tt></a><li><a href=#825006052001><tt>22 Feb 96 aberman@hobbes Office Hours *CANCELLED* This Monday and</tt></a><li><a href=#825026870001><tt>22 Feb 96 tompa@cs ______ HW6, #2 (Warning: this message contains </tt></a><li><a href=#825271119001><tt>25 Feb 96 eallen@cs _____ last problem</tt></a><li><a href=#825283302001><tt>25 Feb 96 ruzzo@cs ______ Re: last problem</tt></a><li><a href=#825355795001><tt>26 Feb 96 tompa@cs ______ last problem</tt></a><li><a href=#825358601001><tt>26 Feb 96 claym@cs ______ Re: HW6, #2 (Warning: this message conta</tt></a><li><a href=#825359061001><tt>26 Feb 96 tompa@cs ______ "describe an algorithm"</tt></a><li><a href=#825405471001><tt>26 Feb 96 tompa@cs ______ space</tt></a><li><a href=#825407777001><tt>26 Feb 96 tompa@cs ______ HW6, #4</tt></a><li><a href=#825893064001><tt> 3 Mar 96 tompa@cs ______ details on Chapter 36 reading assignment</tt></a><li><a href=#825916218001><tt> 3 Mar 96 ruzzo@cs ______ 24-1(a)</tt></a><li><a href=#825917703001><tt> 3 Mar 96 ruzzo@cs ______ Re: 24-1(a)</tt></a><li><a href=#825917904001><tt> 3 Mar 96 ruzzo@cs ______ HW7, 17.2-4</tt></a><li><a href=#825969234001><tt> 4 Mar 96 ruzzo@cs ______ HOMEWORK REVISION</tt></a><li><a href=#825992615001><tt> 4 Mar 96 ruzzo@cs ______ OFFICE HOUR CHANGE</tt></a><li><a href=#826054579001><tt> 5 Mar 96 ruzzo@cs ______ Re: HW 7, 17-2.2 (***CAUTION; HINT BELO</tt></a><li><a href=#826149018001><tt> 6 Mar 96 tompa@cs ______ evaluations Friday</tt></a><li><a href=#826247983001><tt> 7 Mar 96 tompa@cs ______ HW8 (just kidding)</tt></a><li><a href=#826326241001><tt> 8 Mar 96 aberman@hobbes Office Hours During Finals Week</tt></a><li><a href=#826750584001><tt>13 Mar 96 roske@cs ______ Re: HW8 (just kidding)</tt></a><li><a href=#826751342001><tt>13 Mar 96 jshill@u ______ Re: HW8 (just kidding)</tt></a><li><a href=#826755484001><tt>13 Mar 96 tompa@cs ______ HW8 sketchy solutions</tt></a><li><a href=#826758989001><tt>13 Mar 96 tompa@cs ______ HW7</tt></a><li><a href=#826759625001><tt>13 Mar 96 tompa@cs ______ Problem 36.1-4</tt></a><li><a href=#826774955001><tt>13 Mar 96 eallen@cs _____ NP</tt></a><li><a href=#826840060001><tt>14 Mar 96 aberman@hobbes Hw7</tt></a><li><a href=#826930173001><tt>15 Mar 96 tompa@cs ______ HW7 and final exam pickup</tt></a></ul><pre></pre><h2>Messages</h2><pre><hr size=4><a name="820891592001">Date: 5 Jan 1996 17:21 PSTFrom: <b>Larry Ruzzo <ruzzo@quinault.cs.washington.edu></b>To: cse421@csSubject: <b>cse421 mailing list</b></a>We have established a mailing list, cse421@cs, for class informationand discussion. Initial email addresses are taken from theregistrar's 1st day class list, hence are all "...@u" addresses.Please set up mail forwarding from that account if you don'tnormally read mail there. Mail sent to the list is alsoautomatically logged to the course web,http://www.cs.washington.edu/education/courses/421Send mail to cse421-request@cs to be added to or removed from thelist.<hr size=4><a name="821123595001">Date: Mon, 8 Jan 1996 09:53:10 -0800 (PST)From: <b>Eva Marie Allen <eallen@wolf.cs.washington.edu></b>To: cse421@csSubject: <b>study group</b></a>Hi everyone,Several people have started a study group, and want to invite others to join. The meetings times thus far are Monday and Friday, 8:30 to 10:30. Early? Yes. But then, painful times call for painful hours. :)Eva<hr size=4><a name="821137145001">Date: Mon, 8 Jan 1996 13:39:01 -0800 (PST)From: <b>Eva Marie Allen <eallen@wolf.cs.washington.edu></b>To: Cele Couch <cele@grizzly.cs.washington.edu>cc: cse421@csSubject: <b>Re: study group</b></a>On Mon, 8 Jan 1996, Cele Couch wrote:> where do you guys meet? the lounge?> > Yes, so far in the Undergrad lounge. Eva<hr size=4><a name="821150788001">Date: 8 Jan 1996 17:01 PSTFrom: <b>Larry Ruzzo <ruzzo@quinault.cs.washington.edu></b>To: cse421@csSubject: <b>Homework #1 Bugs & Clarifications.</b></a>1. pg 15 1.3-3: Assume n = 2^ k for some integer k>=0.3. pg 37 2.2-2: Assume the domain of T(n) is the set of integers n >= 2. (A careful reading of the definitions seems to show the "if" direction is false otherwise.)4. pg 37 2.2-3: "Equation (2.9)" just means the last of the 7 equations.5. pg 37 2.2-8: Use the recurrence (2.13) and induction. You may NOT use equation (2.15) (or problem 2.2-7).<hr size=4><a name="821167943001">Date: Mon, 8 Jan 1996 22:12:17 -0800 (PST)From: <b>Yih-Chun Hu <yihchun@u.washington.edu></b>To: Larry Ruzzo <ruzzo@cs.washington.edu>Cc: cse421@cs.washington.eduSubject: <b>Re: Homework #1 Bugs & Clarifications.</b></a>On 8 Jan 1996, Larry Ruzzo wrote:> 3. pg 37 2.2-2: Assume the domain of T(n) is the set of integers n> >= 2. (A careful reading of the definitions seems to show the> "if" direction is false otherwise.)The definition given on page 26 of the Big Book of Knowledge seems to indicate that the function 0 (the constant function with value zero) is in O(n), thus there exists a k such that 0 is in O(n^k). It therefore follows that the function T(n) = 0 should be in n^{O(1)} (if the 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:yihchun@cs.washington.edu) ----------------------+| http://www.cs.washington.edu/homes/yihchun yihchun@cs.washington.edu || http://weber.u.washington.edu/~yihchun yihchun@u.washington.edu |+--------------------------------------------------------------------------+<hr size=4><a name="821231741001">To: Yih-Chun Hu <yihchun@u.washington.edu>cc: cse421@cs.washington.eduSubject: <b>HW1, problem 3</b>Date: Tue, 09 Jan 1996 15:55:33 PSTFrom: <b>Martin Tompa <tompa@geoduck.cs.washington.edu></b></a>Thanks for pointing out this further problem with n^{O(1)}. I believe you areright, that if T(n) = 0 for any value of n (say, n=3), then there is nofunction g(n) in O(1) such that 0 = T(3) = 3 ^ {g(3)}.For this problem, then, it's o.k. to assume that T(n) > 0 for all n.Sorry that the problem has yet another bug.------- Forwarded MessageDate: Mon, 08 Jan 1996 22:12:17 -0800From: Yih-Chun Hu <yihchun@u.washington.edu>To: Larry Ruzzo <ruzzo@cs.washington.edu>cc: cse421@cs.washington.eduSubject: Re: Homework #1 Bugs & Clarifications.On 8 Jan 1996, Larry Ruzzo wrote:> 3. pg 37 2.2-2: Assume the domain of T(n) is the set of integers n> >= 2. (A careful reading of the definitions seems to show the> "if" direction is false otherwise.)The definition given on page 26 of the Big Book of Knowledge seems to indicate that the function 0 (the constant function with value zero) is in O(n), thus there exists a k such that 0 is in O(n^k). It therefore follows that the function T(n) = 0 should be in n^{O(1)} (if the 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:yihchun@cs.washington.edu) ----------------------+| http://www.cs.washington.edu/homes/yihchun yihchun@cs.washington.edu || http://weber.u.washington.edu/~yihchun yihchun@u.washington.edu |+--------------------------------------------------------------------------+------- End of Forwarded Message<hr size=4><a name="821232978001">To: Yih-Chun Hu <yihchun@u.washington.edu>cc: cse421@cs.washington.eduSubject: <b>Re: HW1, problem 3</b>Date: Tue, 09 Jan 1996 16:16:01 PSTFrom: <b>Martin Tompa <tompa@geoduck.cs.washington.edu></b></a>You're right again: I was thinking of T(n) as mapping integers to integers,which isn't necessarily the case. So make the assumption T(n) >= 1 for all n. ------- Forwarded MessageDate: Tue, 09 Jan 1996 16:00:25 -0800From: Yih-Chun Hu <yihchun@u.washington.edu>To: Martin Tompa <tompa@cs.washington.edu>cc: ruzzo@cs.washington.eduSubject: Re: HW1, problem 3Is this fix sufficient? If I have T(n) = 0.5, we will have a negative g(n).But then the negative g(n) is not in O(h(n)) for any function h(n) by definition of O(h(n)).On Tue, 9 Jan 1996, Martin Tompa wrote:> > Thanks for pointing out this further problem with n^{O(1)}. I believe you are> right, that if T(n) = 0 for any value of n (say, n=3), then there is no> function g(n) in O(1) such that 0 = T(3) = 3 ^ {g(3)}.> > For this problem, then, it's o.k. to assume that T(n) > 0 for all n.> > Sorry that the problem has yet another bug.> > ------- Forwarded Message> > Date: Mon, 08 Jan 1996 22:12:17 -0800> From: Yih-Chun Hu <yihchun@u.washington.edu>> To: Larry Ruzzo <ruzzo@cs.washington.edu>> cc: cse421@cs.washington.edu> Subject: Re: Homework #1 Bugs & Clarifications.> > > On 8 Jan 1996, Larry Ruzzo wrote:> > > 3. pg 37 2.2-2: Assume the domain of T(n) is the set of integers n> > >= 2. (A careful reading of the definitions seems to show the> > "if" direction is false otherwise.)> > The definition given on page 26 of the Big Book of Knowledge seems to > indicate that the function 0 (the constant function with value zero) is in > O(n), thus there exists a k such that 0 is in O(n^k). It therefore > follows that the function T(n) = 0 should be in n^{O(1)} (if the ⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?