http:^^www.cs.washington.edu^education^courses^431^96s^bboard.shtml
来自「This data set contains WWW-pages collect」· SHTML 代码 · 共 1,486 行 · 第 1/4 页
SHTML
1,486 行
Date: Mon, 02 Dec 1996 14:44:42 GMTServer: NCSA/1.4.2Content-type: text/html<html> <head><title>CSE 431 Bboard/Mail Log</title></head><body><h1>CSE 431 - Intro to Theory of Computation <br> Bboard/Mail Log<br> Spring 1996</h1>This page contains a log of all email sent to the CSE431 classmailing list <tt>cse431@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>jayram@cs</tt>) or instructor (<tt>ruzzo@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>cse431-request@cs</tt>.<h2>Index of Messages</h2>(Latest message Friday, 31-May-96 22:25:08 PDT.)<p><ul><li><a href=#827903528001><tt>26 Mar 96 ruzzo@cs ______ CSE 431 mailing list & web</tt></a><li><a href=#828086115001><tt>28 Mar 96 ruzzo@cs ______ textbook errata</tt></a><li><a href=#828565629001><tt> 3 Apr 96 jayram@curie __ hw1</tt></a><li><a href=#828568975001><tt> 3 Apr 96 ruzzo@cs ______ HW1</tt></a><li><a href=#828666880001><tt> 4 Apr 96 roske@cs ______ HW 1 #3.2</tt></a><li><a href=#828671785001><tt> 4 Apr 96 claym@cs ______ Re: HW1</tt></a><li><a href=#828672423001><tt> 4 Apr 96 claym@cs ______ Re: HW 1 #3.2</tt></a><li><a href=#828676866001><tt> 4 Apr 96 jmur@cs _______ Re: HW1</tt></a><li><a href=#828677062001><tt> 4 Apr 96 jmur@cs _______ Re: HW1</tt></a><li><a href=#828679546001><tt> 4 Apr 96 claym@cs ______ Re: HW1</tt></a><li><a href=#828680601001><tt> 4 Apr 96 ruzzo@cs ______ Re: HW 1 #3.2</tt></a><li><a href=#828682867001><tt> 4 Apr 96 ruzzo@cs ______ Re: HW1</tt></a><li><a href=#828683292001><tt> 4 Apr 96 ruzzo@cs ______ Re: HW1</tt></a><li><a href=#828684564001><tt> 4 Apr 96 claym@cs ______ Re: HW1</tt></a><li><a href=#828945735001><tt> 7 Apr 96 ruzzo@cs ______ Office Hours This week</tt></a><li><a href=#829715127001><tt>16 Apr 96 ruzzo@cs ______ Re: CSE431: Hw #2 questions</tt></a><li><a href=#829723132001><tt>16 Apr 96 ruzzo@cs ______ Re: CSE431: Hw #2 questions</tt></a><li><a href=#829742010001><tt>17 Apr 96 roske@cs ______ Re: CSE431: Hw #2 questions</tt></a><li><a href=#829755533001><tt>17 Apr 96 jayram@cs _____ Re: CSE431: Hw #2 questions </tt></a><li><a href=#829756248001><tt>17 Apr 96 ruzzo@cs ______ Re: CSE431: Hw #2 questions</tt></a><li><a href=#829850875001><tt>18 Apr 96 jayram@cs _____ statistics for hw1</tt></a><li><a href=#829940288001><tt>19 Apr 96 jayram@curie __ office hours today</tt></a><li><a href=#830203567001><tt>22 Apr 96 ruzzo@cs ______ Office hours/Midterm</tt></a><li><a href=#830322083001><tt>23 Apr 96 ruzzo@cs ______ Re: Homework #3, 5.7</tt></a><li><a href=#830456544001><tt>25 Apr 96 ruzzo@cs ______ Partner's</tt></a><li><a href=#830537716001><tt>26 Apr 96 claym@cs ______ Apr</tt></a><li><a href=#830643569001><tt>27 Apr 96 ruzzo@cs ______ exercise</tt></a><li><a href=#831090259001><tt> 2 May 96 roske@cs ______ HW #3 Problem 5.7</tt></a><li><a href=#831098472001><tt> 2 May 96 ruzzo@cs ______ Re: HW #3 Problem 5.7</tt></a><li><a href=#831269855001><tt> 4 May 96 roske@cs ______ HW Solution Questions</tt></a><li><a href=#831493913001><tt> 7 May 96 ruzzo@cs ______ talk today</tt></a><li><a href=#831499402001><tt> 7 May 96 ruzzo@cs ______ Re: talk today</tt></a><li><a href=#832005486001><tt>13 May 96 ruzzo@cs ______ book review</tt></a><li><a href=#832218048001><tt>15 May 96 roske@cs ______ HW #4</tt></a><li><a href=#832309764001><tt>16 May 96 roske@cs ______ HW 4 Prob. 7.30</tt></a><li><a href=#832360862001><tt>17 May 96 jayram@cs _____ Re: NP vx. NP </tt></a><li><a href=#832397386001><tt>17 May 96 ruzzo@cs ______ late HW policy</tt></a><li><a href=#833343977001><tt>28 May 96 jayram@cs _____ Re: Proofs</tt></a><li><a href=#833384953001><tt>29 May 96 ruzzo@cs ______ Re: Handout 6</tt></a><li><a href=#833393843001><tt>29 May 96 jayram@cs _____ hws etc.</tt></a><li><a href=#833507671001><tt>30 May 96 roske@cs ______ HW #5 #7 part (3)</tt></a><li><a href=#833509703001><tt>30 May 96 jayram@cs _____ Re: HW #5 #7 part (3)</tt></a><li><a href=#833512165001><tt>30 May 96 jayram@cs _____ hint for UHAMPATH</tt></a><li><a href=#833512652001><tt>30 May 96 jayram@cs _____ hw4</tt></a><li><a href=#833520727001><tt>30 May 96 fineman@grizzly A little end-of-the-quarter thought</tt></a><li><a href=#833573118001><tt>31 May 96 jayram@hobbes _ solutions for the 3-COLOR and UHAMPATH</tt></a><li><a href=#833587822001><tt>31 May 96 jayram@hobbes _ hot off the oven</tt></a><li><a href=#833589342001><tt>31 May 96 ruzzo@cs ______ Midterm solution</tt></a><li><a href=#833590988001><tt>31 May 96 jayram@cs _____ hw5 solutions</tt></a><li><a href=#833605482001><tt>31 May 96 jayram@cs _____ solutions to 3-COLOR and UHAMPATH</tt></a><li><a href=#833606680001><tt>31 May 96 jayram@cs _____ class web</tt></a></ul><pre></pre><h2>Messages</h2><pre><hr size=4><a name="827903528001">Date: 26 Mar 1996 20:59 PSTFrom: <b>Larry Ruzzo <ruzzo@quinault.cs.washington.edu></b>To: cse431@csSubject: <b>CSE 431 mailing list & web</b></a>Welcome to CSE 431!If you got this message, you're on the CSE 431 class mailing listfor Spring '96. We will use this list for announcements of generalinterest to the class, and you should also feel free to use it toask questions, post information, or initiate discussions. Ofcourse, questions or comments that don't seem of general interestcan be directed to jayram@cs or ruzzo@cs, instead. All mail is also logged to the course web, in case you want toscroll back though messages you didn't save, etc.Following usual Internet conventions, administrative requestsconcerning the mailing list itself, such as add/delete/addresschange requests, should be addressed to cse431-request@cs.Hope you enjoy the course!<hr size=4><a name="828086115001">Date: 28 Mar 1996 23:49 PSTFrom: <b>Larry Ruzzo <ruzzo@quinault.cs.washington.edu></b>To: cse431@csSubject: <b>textbook errata</b></a>I've added a link from the class home page to Sipser's page oferrata for his book. If you see things that look wrong in the text,check his list to see if you've found a reported bug. (There are ahandfull in chapter 3, for example.) If it has not been reported,and you're pretty sure it's wrong, please send email to me and/orsipser@math.mit.edu. [Mike is very meticulous. I'm sure he'd liketo hear about even tiny things like commas out of place before hecreates the final edition of the book.]<hr size=4><a name="828565629001">Date: Wed, 3 Apr 1996 13:06:52 -0800From: <b>jayram@curie (Jayram Thathachar)</b>To: cse431@csSubject: <b>hw1</b></a>Exercise 3.3 deals with enumerators which have not been talked aboutin class as yet. That section is quite readable though and you shouldbe able to understand the proof of Theorem 3.9 quite easily. Both LArry and I feel that you should be ableto solve Problem 3.3after going through that material. So it will still be part of theturn-in on Friday. But if any of you have problems, let me know and you can submit the solution to that problem alone on Monday.For Exercise 3.2, go through the definition of a non-deterministicdecider quite carefully to understand exactly what you need to show.-jayram<hr size=4><a name="828568975001">Date: 3 Apr 1996 13:32 PSTFrom: <b>Larry Ruzzo <ruzzo@quinault.cs.washington.edu></b>To: cse431@csSubject: <b>HW1</b></a>#3.3 ps: there is no late penalty for turning in #3.3 on monday. Takea stab at it, I think many of you will have no trouble with it. Butif you do, don't panic! I'll talk about enumerators 1st thingfriday .#3.2: There's a crucial bug in the text related to this problem ---in the first sentence in the paragraph preceeding corollary 3.8(p122), it is *NOT* true that D will always halt if N does. Inparticular, D will run forever on any input w that N rejects, eventhough N halts on all paths on input w.<hr size=4><a name="828666880001">Date: Thu, 4 Apr 1996 17:14:30 -0800 (PST)From: <b>Larry Roske <roske@lynx.cs.washington.edu></b>To: cse431@lynx.cs.washington.eduSubject: <b>HW 1 #3.2</b></a>Hi, I have questions regarding Homework #1:First, I don't understand why D will run forever on any input wthat N rejects. N rejects a string w if it reaches the end ofw and is not in q_accept. D simulates N with a copy of w ontape 2, and by following a particular branch of N via thenode addresses given on tape 3. If some branch results in arejecting configuration, why shouldn't D also reject?Second, I'm not sure what is meant by the last sentence onpage 121: "Sometimes a symbol may not correspond to any choiceif too few choices are available for a configuration."Third, some clarification on #5 (b): the example ADD instructiongiven combines the use of literal and indirect addressing? Whereliteral addressing refers to, what I learned as, an immediateinstruction in CSE 378. So I take it that the "=" symbol means that j is a literal or constant, and k up-arrow is an address?Thanks,--Larry<hr size=4><a name="828671785001">Date: Thu, 4 Apr 1996 18:36:17 -0800 (PST)From: <b>Michael Clay <claym@wolf.cs.washington.edu></b>To: Larry Ruzzo <ruzzo@cs.washington.edu>cc: cse431@cs.washington.eduSubject: <b>Re: HW1</b></a>On 3 Apr 1996, Larry Ruzzo wrote:> #3.2: There's a crucial bug in the text related to this problem ---> in the first sentence in the paragraph preceeding corollary 3.8> (p122), it is *NOT* true that D will always halt if N does. In> particular, D will run forever on any input w that N rejects, even> though N halts on all paths on input w.Why does N run forever? What is it doing, once it has run outof "lexicographically next strings"? Besides halting in a rejectstate, that is.> #3.3 ps: there is no late penalty for turning in #3.3 on monday. Take> a stab at it, I think many of you will have no trouble with it. But> if you do, don't panic! I'll talk about enumerators 1st thing> friday .I think that this text has enough bugs and the rug has been pulled out from under us enough times on this assignment, that the entire *assignment* should be due Monday, not just 3.3. Please advise, Michael (claym@wolf.cs.washington.edu)<hr size=4><a name="828672423001">Date: Thu, 4 Apr 1996 18:46:38 -0800 (PST)From: <b>Michael Clay <claym@wolf.cs.washington.edu></b>To: Larry Roske <roske@cs.washington.edu>cc: cse431@lynx.cs.washington.eduSubject: <b>Re: HW 1 #3.2</b></a>On Thu, 4 Apr 1996, Larry Roske wrote:> Hi, I have questions regarding Homework #1:> > First, I don't understand why D will run forever on any input w> that N rejects.Neither do I, and I've put my 2 cents in about it.> N rejects a string w if it reaches the end of> w and is not in q_accept. D simulates N with a copy of w on> tape 2, and by following a particular branch of N via the> node addresses given on tape 3. If some branch results in a> rejecting configuration, why shouldn't D also reject?Reread the last two sentences of stage 3 on page 122. It shouldbecome clear.> Second, I'm not sure what is meant by the last sentence on> page 121: "Sometimes a symbol may not correspond to any choice> if too few choices are available for a configuration."The sentence following clarifies what sentence in question means. The real question is how you get into a situation where a symbol does not correspond to any choice in the first place. Reread thelast paragraph on page 121 a few times and you'll figure it out.Hoping I have enlightened more than confused, Michael (claym@wolf.cs.washington.edu)<hr size=4><a name="828676866001">Date: Thu, 4 Apr 1996 20:00:59 -0800 (PST)From: <b>Jason Murray <jmur@grizzly.cs.washington.edu></b>To: Michael Clay <claym@cs.washington.edu>cc: Larry Ruzzo <ruzzo@cs.washington.edu>, cse431@cs.washington.eduSubject: <b>Re: HW1</b></a>On Thu, 4 Apr 1996, Michael Clay wrote:> > > On 3 Apr 1996, Larry Ruzzo wrote:> > > #3.2: There's a crucial bug in the text related to this problem ---> > in the first sentence in the paragraph preceeding corollary 3.8> > (p122), it is *NOT* true that D will always halt if N does. In> > particular, D will run forever on any input w that N rejects, even> > though N halts on all paths on input w.> > Why does N run forever? What is it doing, once it has run out> of "lexicographically next strings"? Besides halting in a reject> state, that is.It doesn't run out of lexicographical next strings. It doesn't say anywhere that it halts in a reject state. The only way to make it halt is with an excepting state. Jason<hr size=4><a name="828677062001">Date: Thu, 4 Apr 1996 20:04:18 -0800 (PST)From: <b>Jason Murray <jmur@grizzly.cs.washington.edu></b>To: Michael Clay <claym@cs.washington.edu>, Larry Ruzzo <ruzzo@cs.washington.edu>, cse431@cs.washington.eduSubject: <b>Re: HW1</b></a>On Thu, 4 Apr 1996, Jason Murray wrote:> > On Thu, 4 Apr 1996, Michael Clay wrote:> > > > > > > On 3 Apr 1996, Larry Ruzzo wrote:> > > > > #3.2: There's a crucial bug in the text related to this problem ---> > > in the first sentence in the paragraph preceeding corollary 3.8> > > (p122), it is *NOT* true that D will always halt if N does. In> > > particular, D will run forever on any input w that N rejects, even> > > though N halts on all paths on input w.> > > > Why does N run forever? What is it doing, once it has run out> > of "lexicographically next strings"? Besides halting in a reject> > state, that is.> > It doesn't run out of lexicographical next strings. It doesn't say > anywhere that it halts in a reject state. The only way to make it halt > is with an excepting state.> > Jason> Oops, I mean accepting........ :) Jason<hr size=4><a name="828679546001">Date: Thu, 4 Apr 1996 20:45:37 -0800 (PST)From: <b>Michael Clay <claym@wolf.cs.washington.edu></b>To: Jason Murray <jmur@cs.washington.edu>cc: Larry Ruzzo <ruzzo@cs.washington.edu>, cse431@cs.washington.eduSubject: <b>Re: HW1</b></a>On Thu, 4 Apr 1996, Jason Murray wrote:> > It doesn't run out of lexicographical next strings. It doesn't say > > anywhere that it halts in a reject state. The only way to make it halt > > is with an excepting state.> > Oops, I mean accepting........ :)Yeah, I figured that out while trying to answer Larry's questions.Like Prof. Ruzzo said, this is pretty dense reading. The more Iread, the denser I feel. ;^)Thanks, Michael (claym@u.washington.edu)<hr size=4><a name="828680601001">Date: 4 Apr 1996 20:23 PSTFrom: <b>Larry Ruzzo <ruzzo@quinault.cs.washington.edu></b>To: Larry Roske <roske@lynx.cs.washington.edu>Subject: <b>Re: HW 1 #3.2</b>Cc: cse431@lynx.cs.washington.edu</a>other students nicely answered most of this. I have just a few more⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?