From devadas@glenfiddich.lcs.mit.edu Wed Sep 30 06:31:32 1998 Return-Path: Received: from LCS.MIT.EDU (mintaka.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA03216; Wed, 30 Sep 98 10:44:40 EDT Received: from glenfiddich.lcs.mit.edu by MINTAKA.LCS.MIT.EDU id aa29008; 30 Sep 98 10:38 EDT Received: from localhost by caa.lcs.mit.ed (SMI-8.6/SMI-SVR4) id KAA27842; Wed, 30 Sep 1998 10:31:32 -0400 Date: Wed, 30 Sep 1998 10:31:32 -0400 (EDT) From: X-Sender: devadas@glenfiddich To: 6042-students@theory.lcs.mit.edu Subject: Thursday Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Dear 6042 students, Please bring your Rosen textbook to lecture on Thursday. Thank you. Srinivas Devadas devadas@mit.edu MIT Laboratory for Computer Science Phone: (617) 253-0454 Room NE43-258 Cambridge, MA 02139 FAX: (617) 253-0415 World Wide Web http://caa.lcs.mit.edu/~devadas From devadas@glenfiddich.lcs.mit.edu Thu Oct 8 13:14:43 1998 Return-Path: Received: from LCS.MIT.EDU (mintaka.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA05536; Thu, 08 Oct 98 17:22:30 EDT Received: from glenfiddich.lcs.mit.edu by MINTAKA.LCS.MIT.EDU id aa08074; 8 Oct 98 17:22 EDT Received: from localhost by caa.lcs.mit.ed (SMI-8.6/SMI-SVR4) id RAA26581; Thu, 8 Oct 1998 17:14:43 -0400 Date: Thu, 8 Oct 1998 17:14:43 -0400 (EDT) From: X-Sender: devadas@glenfiddich To: 6042-students@theory.lcs.mit.edu Subject: various Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Dear 6042 students, Two announcements. First, the staff office hours for Monday October 12, will be shifted to Wednesday October 14. E.g., I have office hours 1-3PM on Mondays. I'll have office hours at 1-3PM on Wednesday. Rooms and times will be unchanged except for the day. Second, we are planning on having a makeup midterm exam on Thursday November 5 from 5-7PM. If you plan on taking the exam at this time send the entire staff 6042-staff@theory.lcs.mit.edu email. If you cannot make the regular time November 4, 7-9PM, OR November 5, 5-7PM, send us email as well. Srinivas Devadas devadas@mit.edu MIT Laboratory for Computer Science Phone: (617) 253-0454 Room NE43-258 Cambridge, MA 02139 FAX: (617) 253-0415 World Wide Web http://caa.lcs.mit.edu/~devadas From jdunagan@theory.lcs.mit.edu Tue Oct 13 07:04:39 1998 Return-Path: Received: from kingfisher.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA16784; Tue, 13 Oct 98 11:04:37 EDT Received: from kingfisher.lcs.mit.edu by kingfisher.lcs.mit.edu (5.65c/TOC-1.2C) id AA05929; Tue, 13 Oct 98 11:04:40 EDT Message-Id: <199810131504.AA05929@kingfisher.lcs.mit.edu> To: 6.042-students Subject: class web page X-Mailer: exmh version 1.3gamma 3/18/94 Date: Tue, 13 Oct 98 11:04:39 -0400 From: jdunagan@theory.lcs.mit.edu The web page is currently down, and we're working on getting it back up. If you do not yet have a copy of the problem set, please attempt to get a copy from a friend, from your TA, or from the course secretary (Joanne Talbot) in ne43-366. As a reminder, the problem set is not due until this Thursday, October 15th. Please bear with us during this time of technical difficulty. -John Dunagan From devadas@glenfiddich.lcs.mit.edu Tue Oct 13 08:11:28 1998 Return-Path: Received: from LCS.MIT.EDU (mintaka.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA18620; Tue, 13 Oct 98 12:19:20 EDT Received: from glenfiddich.lcs.mit.edu by MINTAKA.LCS.MIT.EDU id aa20884; 13 Oct 98 12:19 EDT Received: from localhost by caa.lcs.mit.ed (SMI-8.6/SMI-SVR4) id MAA10359; Tue, 13 Oct 1998 12:11:28 -0400 Date: Tue, 13 Oct 1998 12:11:28 -0400 (EDT) From: X-Sender: devadas@glenfiddich To: 6042-students@theory.lcs.mit.edu Subject: skeleton web page Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Due to a horrible disk crash, virtually all of the theory classes including 6.042 lost their web pages. We have created a skeleton web page that has all the handouts, but not much else in http://theory.lcs.mit.edu/classes/6.042/Fall98 Most of the links on this page are still under construction, however, if you follow the links to Handouts you should be able to get the handouts up to #28. Spring 98 and Fall97 can also be accessed in case you need the lecture notes. Sorry for the inconvenience. Srinivas Devadas devadas@mit.edu MIT Laboratory for Computer Science Phone: (617) 253-0454 Room NE43-258 Cambridge, MA 02139 FAX: (617) 253-0415 World Wide Web http://caa.lcs.mit.edu/~devadas From jdunagan@theory.lcs.mit.edu Wed Oct 21 08:12:09 1998 Return-Path: Received: from stork.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA16218; Wed, 21 Oct 98 12:12:15 EDT Received: from stork.lcs.mit.edu by stork.lcs.mit.edu (5.65c/TOC-1.2C) id AA03869; Wed, 21 Oct 98 12:12:09 EDT Message-Id: <199810211612.AA03869@stork.lcs.mit.edu> To: 6042-students Subject: 6.042 web page Date: Wed, 21 Oct 98 12:12:09 -0400 From: jdunagan@theory.lcs.mit.edu I am pleased to announce that the 6.042 web page is in reaonable shape. The URL is http://theory.lcs.mit.edu/classes/6.042 Sincerely, John Dunagan on behalf of the 6.042 staff From jdunagan@theory.lcs.mit.edu Thu Oct 29 14:18:52 1998 Return-Path: Received: from kingfisher.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA16997; Thu, 29 Oct 98 19:20:12 EST Received: from kingfisher.lcs.mit.edu by kingfisher.lcs.mit.edu (5.65c/TOC-1.2C) id AA01988; Thu, 29 Oct 98 19:19:32 EST Message-Id: <199810300019.AA01988@kingfisher.lcs.mit.edu> To: 6.042-students@theory.lcs.mit.edu Cc: jdunagan@theory.lcs.mit.edu Subject: IMPORTANT 6.042 ANNOUNCEMENTS X-Mailer: exmh version 1.3gamma 3/18/94 Date: Thu, 29 Oct 98 19:18:52 -0500 From: jdunagan@theory.lcs.mit.edu The review session which was originally scheduled for Monday, 11/2, 7-9pm 4-270, 4-370 NOT THE REVIEW SESSION has been moved. The time is the same, but the new room is 24-311, the same room in which a majority of the TA's hold their office hours. To sum up, the review session is now going to be Monday, 11/2, 7-9pm 24-311 THE REVIEW SESSION (+ ICE CREAM) That's right, the review session will double as a 6.042 ice-cream social. The style of the review session will be informal. It will be structured as extra office hours. No new material will be covered. In order to get something out of the review session, you probably need to come with questions. Also, the TA's will be working through the practice quiz during the review session. (Solutions to the practice quiz will also be handed out in recitation tomorrow.) The midterm is still Wednesday, 11/4, 7-9pm 4-270, 4-370 THE MIDTERM The make-up midterm is Thursday, 11/5, 5-7pm 4-153 THE MAKE-UP MIDTERM You may only attend the make-up midterm if you have a conflict, and you have notified the 6.042 staff of your conflict well in advance of the midterm. Notifying the staff consists of sending an email to 6.042-staff@theory.lcs.mit.edu Students who have not notified the staff that they plan to take the make-up midterm and who fail to show up for the regular midterm will receive a large goose egg for a grade on the midterm. (Large goose egg is a metaphor for zero. Consider its shape.) ADDITIONAL OFFICE HOURS: All TA's who hold office hours on Monday will be holding additional office hours on Wednesday of next week (the day of the midterm). The location and time will be the same. Additionally, TA Adam Gould, who normally holds office hours before lecture on Tuesdays, will also be holding office hours after lecture on Tuesday, from 4-6pm. Best of luck to you all, TA John Dunagan From devadas@glenfiddich.lcs.mit.edu Sat Oct 31 08:04:51 1998 Return-Path: Received: from LCS.MIT.EDU (mintaka.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA11575; Sat, 31 Oct 98 13:13:35 EST Received: from glenfiddich.lcs.mit.edu by MINTAKA.LCS.MIT.EDU id aa24873; 31 Oct 98 13:13 EST Received: from localhost by caa.lcs.mit.edu (SMI-8.6/SMI-SVR4) id NAA05913; Sat, 31 Oct 1998 13:04:51 -0500 Date: Sat, 31 Oct 1998 13:04:51 -0500 (EST) From: X-Sender: devadas@glenfiddich To: 6042-students@theory.lcs.mit.edu Subject: Midterm Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Dear 6.042 students, The 6.042 midterm will be open notes, open book. Good luck on it. Srinivas Devadas devadas@mit.edu MIT Laboratory for Computer Science Phone: (617) 253-0454 Room NE43-258 Cambridge, MA 02139 FAX: (617) 253-0415 World Wide Web http://caa.lcs.mit.edu/~devadas From agould@MIT.EDU Tue Nov 3 20:06:11 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA22409; Wed, 04 Nov 98 01:06:30 EST Received: from MASS-TOOLPIKE.MIT.EDU by MIT.EDU with SMTP id AA09896; Wed, 4 Nov 98 01:06:16 EST Received: by mass-toolpike.mit.edu (8.8.7/4.7) id BAA23203; Wed, 4 Nov 1998 01:06:11 -0500 (EST) Message-Id: <199811040606.BAA23203@mass-toolpike.mit.edu> To: 6042-students@theory.lcs.mit.edu Subject: office hours on Thursday Date: Wed, 04 Nov 1998 01:06:11 EST From: Adam J Gould Dear class, I will not be holding my normal office hours this week on Thursday. I am sorry for the extremely late notice, but if you were planning to attend office hours this Thursday, then please email me and I will try to work out other arrangements with you. Good luck to everyone on the exam. -Adam Gould From devadas@glenfiddich.lcs.mit.edu Tue Nov 10 11:02:27 1998 Return-Path: Received: from LCS.MIT.EDU (mintaka.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA02867; Tue, 10 Nov 98 16:11:31 EST Received: from glenfiddich.lcs.mit.edu by MINTAKA.LCS.MIT.EDU id aa11774; 10 Nov 98 16:10 EST Received: from localhost by caa.lcs.mit.edu (SMI-8.6/SMI-SVR4) id QAA22437; Tue, 10 Nov 1998 16:02:27 -0500 Date: Tue, 10 Nov 1998 16:02:27 -0500 (EST) From: X-Sender: devadas@glenfiddich To: 6042-students@theory.lcs.mit.edu Subject: problem set readings Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Dear 6.042 students, PS9, which just went out today, has Readings: Essentials of Probability book on it. That is an error. It should be Rosen 4.4, and 4.5. Sorry for any confusion. Srinivas Devadas devadas@mit.edu MIT Laboratory for Computer Science Phone: (617) 253-0454 Room NE43-258 Cambridge, MA 02139 FAX: (617) 253-0415 World Wide Web http://caa.lcs.mit.edu/~devadas From amsduran@theory.lcs.mit.edu Sat Nov 28 13:05:10 1998 Return-Path: Received: from harrier.lcs.mit.edu ([18.52.0.159]) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA22487; Sat, 28 Nov 98 18:03:26 EST Received: from harrier.lcs.mit.edu (localhost [127.0.0.1]) by harrier.lcs.mit.edu (8.9.0/8.9.0) with ESMTP id SAA15099; Sat, 28 Nov 1998 18:05:11 -0500 Message-Id: <199811282305.SAA15099@harrier.lcs.mit.edu> To: 6042-students@theory.lcs.mit.edu Cc: 6042-staff@theory.lcs.mit.edu Subject: Problem Set Error Date: Sat, 28 Nov 1998 18:05:10 -0500 From: Alex Duran On PS11, Problem number 1, part F, the problem asks about the expectation of S intersect T. One does not intersect random variables, they are not events. The problem should read: Ex(S * T) = Ex(S) * Ex(T). From amsduran@theory.lcs.mit.edu Mon Nov 30 05:14:51 1998 Return-Path: Received: from harrier.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA18492; Mon, 30 Nov 98 10:12:59 EST Received: from harrier.lcs.mit.edu (localhost [127.0.0.1]) by harrier.lcs.mit.edu (8.9.0/8.9.0) with ESMTP id KAA16635; Mon, 30 Nov 1998 10:14:51 -0500 Message-Id: <199811301514.KAA16635@harrier.lcs.mit.edu> To: 6042-students@theory.lcs.mit.edu Cc: 6042-staff@theory.lcs.mit.edu Subject: Office Hours and Pset Date: Mon, 30 Nov 1998 10:14:51 -0500 From: Alex Duran The problem set is due on Friday, December 4, at the beginning of recitation. That is not a typo on the problem set. Since the problem set is due on Friday, and not Tuesday, TAs will be holding office hours on Wednesday instead of Monday. They will be at the same time Wednesday that they were on Monday, e.g., I will have office hours from 5-8 p.m. on Wednesday evening. Adam will have his regular office hours on Tuesday and Thursday. --Alex amsduran@mit.edu From jdunagan@theory.lcs.mit.edu Fri Dec 4 06:54:39 1998 Return-Path: Received: from stork.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA10818; Fri, 04 Dec 98 11:55:07 EST Received: from stork.lcs.mit.edu by stork.lcs.mit.edu (5.65c/TOC-1.2C) id AA05718; Fri, 04 Dec 98 11:54:39 EST Message-Id: <199812041654.AA05718@stork.lcs.mit.edu> To: 6.042-students Cc: 6.042-staff Subject: SUPER-IMPORTANT 6.042 ANNOUNCEMENT X-Mailer: exmh version 1.3gamma 3/18/94 Date: Fri, 04 Dec 98 11:54:39 -0500 From: jdunagan@theory.lcs.mit.edu There will be an optional review session on Friday the 11th from 1-5pm. No new material will be covered, and attendees should bring questions which they would like answered. The review session for the final will be structured identically to the review session for the midterm, and it will be held in the classrooms on the 3rd floor of building 34. Since the review session is on Friday the 11th, and Thursday the 10th is the last day of classes, it is our hope that everybody who would like to attend can make some of the 1-5pm time. Just like the last review session, there will be ice cream for the students who arrive before 1:15pm. Similar to the midterm review session, the various TA's will answer questions in separate rooms. To sum up, that's Friday, 12/11, 1-5pm 34-301, 34-3-2, 34-303, 34-304 REVIEW SESSION (+ ICE CREAM) and just in case you needed a reminder, the time and location for the final is Tuesday, 12/15, 9am-noon Johnson Athletic Center FINAL EXAM wishing you all grades above the mean, The Staff From lynch@theory.lcs.mit.edu Thu Dec 10 11:44:36 1998 Return-Path: Received: from sandpiper.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA13680; Thu, 10 Dec 98 16:45:07 EST From: lynch@theory.lcs.mit.edu (Nancy Lynch) Received: by sandpiper.lcs.mit.edu (5.65c/TOC-1.2C) id AA04060; Thu, 10 Dec 98 16:44:36 EST Date: Thu, 10 Dec 98 16:44:36 EST Message-Id: <199812102144.AA04060@sandpiper.lcs.mit.edu> To: 6042-students Subject: Thanks Cc: 6042-staff Thanks on behalf of myself and Prof. Devadas for the red-ribboned Theory Spam Christmas present. I am sorry I did not notice during lecture that the first ingredient is Theory Pig. It looks like our poor pig has met a very sad ending. (Check out the course Web page if you don't know what I'm talking about.) Nancy Lynch From jdunagan@theory.lcs.mit.edu Fri Dec 11 13:02:20 1998 Return-Path: Received: from kingfisher.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA26754; Fri, 11 Dec 98 18:02:53 EST Received: from kingfisher.lcs.mit.edu by kingfisher.lcs.mit.edu (5.65c/TOC-1.2C) id AA14545; Fri, 11 Dec 98 18:02:21 EST Message-Id: <199812112302.AA14545@kingfisher.lcs.mit.edu> To: 6042-students Subject: minor correction to one of the sample problems In-Reply-To: Your message of Thu, 10 Dec 98 16:44:36 -0500. <199812102144.AA04060@sandpiper.lcs.mit.edu> X-Mailer: exmh version 1.3gamma 3/18/94 Date: Fri, 11 Dec 98 18:02:20 -0500 From: jdunagan@theory.lcs.mit.edu There are some minor typos on sample problem 6. (I haven't had the oppurtunity to check this with another TA, but I'm sure one of them will correct me if I'm wrong.) The line in 6b, >Let $C_k$ be a random variable that is equal to $1$ if $i_{k+1} > i_{k}$. >What is $\Ex[C_k]$? Should actually read >Let $C_k$ be a random variable that is equal to $1$ if, on the k'th step, >$i_{k+1} > i_{k}$. >What is $\Ex[C_k]$? Then, the solution which currently reads >\[\Ex[C_k] = \Pr({C_k = 1}) > = \Pr({\mbox{ $i_k$ is highest so far}}) > = \frac{1}{k+1}.\] should actually read >\[\Ex[C_k] = \Pr({C_k = 1}) > = \Pr({\mbox{ $i_{k+1}$ is highest so far}}) > = \frac{1}{k+1}.\] Moving on to 6c), the solution currently reads >$C$ is the total number of swaps, >so $\Ex[C]$ is the expected number of swaps. It should actually state that C is the number of times you don't swap, so (n - ln n) is the expected number of swaps performed. Also, C can only be summed from k=1 to n-1, not from 1 to n, since C_n is not defined (but this doesn't make much of a difference in the overall computation.) Thanks to one of my students for pointing this out. Wishing You A Happy Exam Period, John Dunagan