BABYL OPTIONS: -*- rmail -*- Version: 5 Labels: Note: This is the header of an rmail file. Note: If you are seeing it in rmail, Note: it means the file has no messages in it.  1,, Mail-from: From miccianc@theory.lcs.mit.edu Fri Feb 7 13:08:08 1997 Return-Path: Received: from ostrich.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA06241; Fri, 07 Feb 97 18:09:44 EST From: miccianc@theory.lcs.mit.edu (Daniele Micciancio) Received: by ostrich.lcs.mit.edu (5.65c/TOC-1.2C) id AA02218; Fri, 07 Feb 97 18:08:08 EST Date: Fri, 07 Feb 97 18:08:08 EST Message-Id: <199702072308.AA02218@ostrich.lcs.mit.edu> To: 6042-forum *** EOOH *** Return-Path: From: miccianc@theory.lcs.mit.edu (Daniele Micciancio) Date: Fri, 07 Feb 97 18:08:08 EST To: 6042-forum In today's recitation taught by Alex an 8.03 kit items was left behind. If it belongs to you, you can pick it up from NE43-342. Alex.  1,, Mail-from: From dimitrip@theory.lcs.mit.edu Mon Feb 10 06:06:58 1997 Return-Path: Received: from peacock.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA05096; Mon, 10 Feb 97 11:06:29 EST Received: from peacock.lcs.mit.edu by peacock.lcs.mit.edu (5.65c/TOC-1.2C) id AA03049; Mon, 10 Feb 97 11:06:58 EST Message-Id: <199702101606.AA03049@peacock.lcs.mit.edu> To: 6042-forum Cc: 6042-tas Subject: recitations and tutorials Date: Mon, 10 Feb 97 11:06:58 -0500 From: dimitrip@theory.lcs.mit.edu *** EOOH *** Return-Path: To: 6042-forum Cc: 6042-tas Subject: recitations and tutorials Date: Mon, 10 Feb 97 11:06:58 -0500 From: dimitrip@theory.lcs.mit.edu Hello, Please check your recitation and tutorial room assignments on the web and make sure that you go to the correct room. If you wish to switch time or section please send me mail: dimitrip@theory.lcs. Cheers, Dimitri  1,, Mail-from: From gupta@theory.lcs.mit.edu Tue Feb 11 14:58:26 1997 Return-Path: Received: from peacock.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA27949; Tue, 11 Feb 97 19:57:56 EST From: gupta@theory.lcs.mit.edu (David Gupta) Received: by peacock.lcs.mit.edu (5.65c/TOC-1.2C) id AA12978; Tue, 11 Feb 97 19:58:26 EST Date: Tue, 11 Feb 97 19:58:26 EST Message-Id: <199702120058.AA12978@peacock.lcs.mit.edu> To: 6042-forum Subject: conflict tutorial *** EOOH *** Return-Path: From: gupta@theory.lcs.mit.edu (David Gupta) Date: Tue, 11 Feb 97 19:58:26 EST To: 6042-forum Subject: conflict tutorial Hello all, There will definitely be a tutorial scheduled outside the M1-3 block. If you have conflicts with *ALL* the scheduled Monday tutorials, please send e-mail ASAP to gupta@theory.lcs.mit.edu listing all times Monday 8:00am-9:00pm and Tuesday 8:00am-9:00pm when you could make a tutorial. Please don't leave out any times you could possibly make, but you can indicate which times are better or worse. You should send this information even if you have sent it before. Please include an asterisk (*) and the words "conflict tutorial" in the header of your message. This applies only to those who have conflicts with all the scheduled tutorials. Other scheduling requests should be addressed to 6042-headta@theory.lcs.mit.edu. David Gupta  1,, Mail-from: From gupta@theory.lcs.mit.edu Thu Feb 13 14:03:13 1997 Return-Path: Received: from swift.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA22729; Thu, 13 Feb 97 19:05:28 EST From: gupta@theory.lcs.mit.edu (David Gupta) Received: by swift.lcs.mit.edu (5.65c/TOC-1.2C) id AA01438; Thu, 13 Feb 97 19:03:13 EST Date: Thu, 13 Feb 97 19:03:13 EST Message-Id: <199702140003.AA01438@swift.lcs.mit.edu> To: 6042-forum Subject: new 7:00 tutorial on Tuesdays *** EOOH *** Return-Path: From: gupta@theory.lcs.mit.edu (David Gupta) Date: Thu, 13 Feb 97 19:03:13 EST To: 6042-forum Subject: new 7:00 tutorial on Tuesdays Hello all, The current plan is to keep all of the tutorials meeting in the M1-3 block and have an additional tutorial meeting Tuesday at 7:00pm. If you have unavoidable conflicts with all of these times, please send e-mail to gupta@theory.lcs.mit.edu. Please bear with us as we shuffle tutorial assignments to resolve conflicts and balance tutorial sizes. Requests for schedule changes should be sent to 6042-headta@theory.lcs.mit.edu. We have not yet reserved a room for the new 7:00pm tutorial. This information will be made available when we have it. David Gupta  1,, Mail-from: From karger@theory.lcs.mit.edu Sat Feb 15 15:56:32 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA14242; Sat, 15 Feb 97 20:58:57 EST Received: by ibis (SMI-8.6/TOC-1.2C) id UAA00847; Sat, 15 Feb 1997 20:56:32 -0500 Date: Sat, 15 Feb 1997 20:56:32 -0500 Message-Id: <199702160156.UAA00847@ibis> From: "David R. Karger" To: 6042-forum Subject: [meeroh@MIT.EDU: PS2 correction] *** EOOH *** Return-Path: Date: Sat, 15 Feb 1997 20:56:32 -0500 From: "David R. Karger" To: 6042-forum Subject: [meeroh@MIT.EDU: PS2 correction] A typo has been discovered in problem 8. ------- Start of forwarded message ------- Date: Fri, 14 Feb 1997 20:29:40 -0500 To: karger@lcs.mit.edu From: Miro Jurisic Subject: PS2 correction Problem 8, x(y+z)=xz+yz should be x(y+z)=xy+xz. Hth, meeroh Miroslav Jurisic | meeroh@mit.edu | http://www.mit.edu/people/meeroh/ MIT Information Systems (Mac development) | Athena On-Line Consulting Lt. Commander Meeroh Ambellus, TrekMUSH (ats.trekmush.org:1701) Let's grep the hard disk and see if we can find any hits on "." How do you propose we do that? [...] we dump the entire contents of the hard disk to a Web page, register it with AltaVista, and perform the search. [_d e v e l o p_, Dec 96] ------- End of forwarded message -------  1,, Mail-from: From tiuzzol@MIT.EDU Sat Feb 15 19:24:15 1997 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA17019; Sun, 16 Feb 97 00:24:15 EST Received: from PUTTANESCA.MIT.EDU by MIT.EDU with SMTP id AA26892; Sun, 16 Feb 97 00:24:15 EST From: tiuzzol@MIT.EDU Received: by puttanesca.MIT.EDU (5.57/4.7) id AA27941; Sun, 16 Feb 97 00:24:15 -0500 Date: Sun, 16 Feb 97 00:24:15 -0500 Message-Id: <9702160524.AA27941@puttanesca.MIT.EDU> To: 6042-forum@theory.lcs.mit.edu Subject: Office hours on Monday *** EOOH *** Return-Path: From: tiuzzol@MIT.EDU Date: Sun, 16 Feb 97 00:24:15 -0500 To: 6042-forum@theory.lcs.mit.edu Subject: Office hours on Monday Since Monday is a holiday and we don't have classes, I'll be holding office hours from 1-4pm in the 3rd floor lounge at NE43 (Tech Square). If the lobby doors are locked, just knock loudly. Terri  1,, Mail-from: From gupta@theory.lcs.mit.edu Sun Feb 16 12:40:12 1997 Return-Path: Received: from peacock.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA01287; Sun, 16 Feb 97 17:39:40 EST From: gupta@theory.lcs.mit.edu (David Gupta) Received: by peacock.lcs.mit.edu (5.65c/TOC-1.2C) id AA07988; Sun, 16 Feb 97 17:40:12 EST Date: Sun, 16 Feb 97 17:40:12 EST Message-Id: <199702162240.AA07988@peacock.lcs.mit.edu> To: 6042-forum Subject: office hours on Monday *** EOOH *** Return-Path: From: gupta@theory.lcs.mit.edu (David Gupta) Date: Sun, 16 Feb 97 17:40:12 EST To: 6042-forum Subject: office hours on Monday Hello all, I will be holding office hours 3-5pm Monday in the 3rd floor lounge of NE43. This is an hour earlier than my regular office hours, but still in the same place. David G.  1,, Mail-from: From dimitrip@theory.lcs.mit.edu Mon Feb 17 08:56:13 1997 Return-Path: Received: from peacock.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA25093; Mon, 17 Feb 97 13:55:43 EST Received: from peacock.lcs.mit.edu by peacock.lcs.mit.edu (5.65c/TOC-1.2C) id AA10666; Mon, 17 Feb 97 13:56:14 EST Message-Id: <199702171856.AA10666@peacock.lcs.mit.edu> To: 6042-forum Cc: dimitrip Subject: office hours Date: Mon, 17 Feb 97 13:56:13 -0500 From: dimitrip@theory.lcs.mit.edu *** EOOH *** Return-Path: To: 6042-forum Cc: dimitrip Subject: office hours Date: Mon, 17 Feb 97 13:56:13 -0500 From: dimitrip@theory.lcs.mit.edu Hello, Tomorrow is Monday so I will hold office hours from 5 to 7 as announced. Dimitri  1,, Mail-from: From dimitrip@theory.lcs.mit.edu Mon Feb 17 10:00:23 1997 Return-Path: Received: from peacock.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA26509; Mon, 17 Feb 97 14:59:54 EST Received: from peacock.lcs.mit.edu by peacock.lcs.mit.edu (5.65c/TOC-1.2C) id AA11001; Mon, 17 Feb 97 15:00:25 EST Message-Id: <199702172000.AA11001@peacock.lcs.mit.edu> To: 6042-forum Cc: dimitrip Subject: office hours Date: Mon, 17 Feb 97 15:00:23 -0500 From: dimitrip@theory.lcs.mit.edu *** EOOH *** Return-Path: To: 6042-forum Cc: dimitrip Subject: office hours Date: Mon, 17 Feb 97 15:00:23 -0500 From: dimitrip@theory.lcs.mit.edu Hello, OK, I forgot that homework is due tomorrow in tutorials. I will hold office hours tomorrow morning 10-12 in the NE43 3rd floor lounge. Please disregard my previous mail and sorry for the confusion. Dimitri  1,, Mail-from: From dimitrip@theory.lcs.mit.edu Fri Feb 21 08:37:13 1997 Return-Path: Received: from peacock.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA16231; Fri, 21 Feb 97 13:36:42 EST Received: from peacock.lcs.mit.edu by peacock.lcs.mit.edu (5.65c/TOC-1.2C) id AA02461; Fri, 21 Feb 97 13:37:14 EST Message-Id: <199702211837.AA02461@peacock.lcs.mit.edu> To: 6042-forum Cc: 6042-teachers Subject: homework Date: Fri, 21 Feb 97 13:37:13 -0500 From: dimitrip@theory.lcs.mit.edu *** EOOH *** Return-Path: To: 6042-forum Cc: 6042-teachers Subject: homework Date: Fri, 21 Feb 97 13:37:13 -0500 From: dimitrip@theory.lcs.mit.edu Hello, Starting this comming Tuesday there will be three boxes in the classroom for the purpose of collecting the homework. Please place the homework in the box with the name of your tutorial instructor. Remember to write in the first page of your homework your tutorial time and tutorial instructor's name. Thank you, Dimitri  1,, Mail-from: From karger@theory.lcs.mit.edu Sat Feb 22 19:44:16 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA09965; Sun, 23 Feb 97 00:46:46 EST From: karger@theory.lcs.mit.edu (David R. Karger) Received: by ibis (SMI-8.6/TOC-1.2C) id AAA24107; Sun, 23 Feb 1997 00:44:16 -0500 Date: Sun, 23 Feb 1997 00:44:16 -0500 Message-Id: <199702230544.AAA24107@ibis> To: 6042-forum@theory.lcs.mit.edu Subject: pset 3 notes *** EOOH *** Return-Path: From: karger@theory.lcs.mit.edu (David R. Karger) Date: Sun, 23 Feb 1997 00:44:16 -0500 To: 6042-forum@theory.lcs.mit.edu Subject: pset 3 notes A couple of notes on problem set 3: 1) for the string proof, you may assume the following axioms: v.lambda = v = lambda.v (Rosen is sloppy about not stating this explicityl) 2) in the optional question, the ! is a factorial, not a typo. c6042 graders  1,, Mail-from: From gupta@theory.lcs.mit.edu Tue Feb 25 17:59:22 1997 Return-Path: Received: from peacock.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA26229; Tue, 25 Feb 97 22:58:50 EST From: gupta@theory.lcs.mit.edu (David Gupta) Received: by peacock.lcs.mit.edu (5.65c/TOC-1.2C) id AA23075; Tue, 25 Feb 97 22:59:22 EST Date: Tue, 25 Feb 97 22:59:22 EST Message-Id: <199702260359.AA23075@peacock.lcs.mit.edu> To: 6042-forum Subject: reminder of course policy on late homework *** EOOH *** Return-Path: From: gupta@theory.lcs.mit.edu (David Gupta) Date: Tue, 25 Feb 97 22:59:22 EST To: 6042-forum Subject: reminder of course policy on late homework Hello all, The policy for late homework is described in the Course Information handout that was distributed on the first day of class and is available from the course home page. You are responsible for familiarizing yourself with course policy as described in this handout. Problem sets are to be turned in before class starts. The course staff reserves the right to mark any homework turned in after class begins as late. This will reduce the grade on that assignment by 20%. Usually, we allow a short grace period before we begin to mark homework problems late, but you should not count on this. The official time when homework is due may change to 5 minutes after class begins (or something like this) if logistics end up requiring this, but the late policy will remain the same. David G.  1,, Mail-from: From karger@theory.lcs.mit.edu Wed Feb 26 05:40:21 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA07750; Wed, 26 Feb 97 10:42:54 EST Received: by ibis (SMI-8.6/TOC-1.2C) id KAA02072; Wed, 26 Feb 1997 10:40:21 -0500 Date: Wed, 26 Feb 1997 10:40:21 -0500 Message-Id: <199702261540.KAA02072@ibis> From: "David R. Karger" To: 6042-forum@theory.lcs.mit.edu, gupta, miccianc, dimitrip, alexv, tiuzzol@mit.edu, etara@mit.edu, dmarino@mit.edu, acpatel@mit.edu, zia@mit.edu, lysi@mit.edu Subject: optional problems *** EOOH *** Return-Path: Date: Wed, 26 Feb 1997 10:40:21 -0500 From: "David R. Karger" To: 6042-forum@theory.lcs.mit.edu, gupta, miccianc, dimitrip, alexv, tiuzzol@mit.edu, etara@mit.edu, dmarino@mit.edu, acpatel@mit.edu, zia@mit.edu, lysi@mit.edu Subject: optional problems There has been some confusion regarding optional problems. This note is to unconfuse you. Optional problems are _not_ required problems. You can get an A without doing any of them. They are there for three relatively unimportant reasons: 1) some of you might enjoy the challenege 2) they may make a difference if all else is completely in balance 3) doing well on them is a good way to catch stand out in the crowded class, which may be useful for future recommendation writing, etc.  1,, Mail-from: From miccianc@theory.lcs.mit.edu Wed Feb 26 07:52:49 1997 Return-Path: Received: from lark.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA13874; Wed, 26 Feb 97 12:51:04 EST From: miccianc@theory.lcs.mit.edu (Daniele Micciancio) Received: by lark.lcs.mit.edu (5.65c/TOC-1.2C) id AA02964; Wed, 26 Feb 97 12:52:49 EST Date: Wed, 26 Feb 97 12:52:49 EST Message-Id: <199702261752.AA02964@lark.lcs.mit.edu> To: 6042-forum Subject: test message *** EOOH *** Return-Path: From: miccianc@theory.lcs.mit.edu (Daniele Micciancio) Date: Wed, 26 Feb 97 12:52:49 EST To: 6042-forum Subject: test message This is a test message. All 6.042 students should receive it. Sorry if you receive it more than once. If you know of any student that did not receive it please send email to miccianc@theory.lcs.mit.edu. Otherwise, just ignore it (you do NOT have to acknowledge this message). Daniele  1,, Mail-from: From gupta@theory.lcs.mit.edu Thu Mar 6 07:23:07 1997 Return-Path: Received: from emu.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA19070; Thu, 06 Mar 97 12:24:43 EST From: gupta@theory.lcs.mit.edu (David Gupta) Received: by emu.lcs.mit.edu (5.65c/TOC-1.2C) id AA02528; Thu, 06 Mar 97 12:23:07 EST Date: Thu, 06 Mar 97 12:23:07 EST Message-Id: <199703061723.AA02528@emu.lcs.mit.edu> To: 6042-forum Subject: correction to ps5 *** EOOH *** Return-Path: From: gupta@theory.lcs.mit.edu (David Gupta) Date: Thu, 06 Mar 97 12:23:07 EST To: 6042-forum Subject: correction to ps5 Hello all, In problem 8, the precondition for give-cent should also require that total - total' be greater than 0, as well as less than 10. David G.  1,, Mail-from: From karger@theory.lcs.mit.edu Thu Mar 6 12:56:33 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA28743; Thu, 06 Mar 97 17:59:12 EST From: karger@theory.lcs.mit.edu (David R. Karger) Received: by ibis (SMI-8.6/TOC-1.2C) id RAA20128; Thu, 6 Mar 1997 17:56:33 -0500 Date: Thu, 6 Mar 1997 17:56:33 -0500 Message-Id: <199703062256.RAA20128@ibis> To: 6042-forum@theory.lcs.mit.edu Subject: problem set bug *** EOOH *** Return-Path: From: karger@theory.lcs.mit.edu (David R. Karger) Date: Thu, 6 Mar 1997 17:56:33 -0500 To: 6042-forum@theory.lcs.mit.edu Subject: problem set bug in the optional "Bump" problem, the question should be "what happens if Bump(0) is called n times.  1,, Mail-from: From karger@theory.lcs.mit.edu Thu Mar 6 13:03:16 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA28873; Thu, 06 Mar 97 18:05:55 EST From: karger@theory.lcs.mit.edu (David R. Karger) Received: by ibis (SMI-8.6/TOC-1.2C) id SAA20137; Thu, 6 Mar 1997 18:03:16 -0500 Date: Thu, 6 Mar 1997 18:03:16 -0500 Message-Id: <199703062303.SAA20137@ibis> To: 6042-forum@theory.lcs.mit.edu Subject: pset bug *** EOOH *** Return-Path: From: karger@theory.lcs.mit.edu (David R. Karger) Date: Thu, 6 Mar 1997 18:03:16 -0500 To: 6042-forum@theory.lcs.mit.edu Subject: pset bug In problem 5, the initializations should be Fprev = 0 Fnext = 1  1,, Mail-from: From karger@theory.lcs.mit.edu Thu Mar 6 13:25:48 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA29305; Thu, 06 Mar 97 18:28:27 EST From: karger@theory.lcs.mit.edu (David R. Karger) Received: by ibis (SMI-8.6/TOC-1.2C) id SAA20174; Thu, 6 Mar 1997 18:25:48 -0500 Date: Thu, 6 Mar 1997 18:25:48 -0500 Message-Id: <199703062325.SAA20174@ibis> To: 6042-forum Subject: office hours *** EOOH *** Return-Path: From: karger@theory.lcs.mit.edu (David R. Karger) Date: Thu, 6 Mar 1997 18:25:48 -0500 To: 6042-forum Subject: office hours My office hours will be moved this week. instead of tomorrow, they will be Monday 1:30-3.  1,, Mail-from: From gupta@theory.lcs.mit.edu Thu Mar 6 13:35:17 1997 Return-Path: Received: from whippoorwill.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA29449; Thu, 06 Mar 97 18:33:51 EST From: gupta@theory.lcs.mit.edu (David Gupta) Received: by whippoorwill.lcs.mit.edu (5.65c/TOC-1.2C) id AA04182; Thu, 06 Mar 97 18:35:17 EST Date: Thu, 06 Mar 97 18:35:17 EST Message-Id: <199703062335.AA04182@whippoorwill.lcs.mit.edu> To: 6042-forum Subject: office hours *** EOOH *** Return-Path: From: gupta@theory.lcs.mit.edu (David Gupta) Date: Thu, 06 Mar 97 18:35:17 EST To: 6042-forum Subject: office hours Hello all, I am moving my office hours for next week to tomorrow (Friday) from 3-5pm in the third floor lounge of LCS (NE43). David G.  1,, Mail-from: From alexv@theory.lcs.mit.edu Fri Mar 7 19:46:33 1997 Return-Path: Received: from whimbrel.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA28858; Sat, 08 Mar 97 00:44:46 EST From: alexv@theory.lcs.mit.edu (Alex Vasilescu) Received: by whimbrel.lcs.mit.edu (5.65c/TOC-1.2C) id AA10318; Sat, 08 Mar 97 00:46:33 EST Date: Sat, 08 Mar 97 00:46:33 EST Message-Id: <199703080546.AA10318@whimbrel.lcs.mit.edu> To: 6042-forum@theory.lcs.mit.edu Subject: PS #4 *** EOOH *** Return-Path: From: alexv@theory.lcs.mit.edu (Alex Vasilescu) Date: Sat, 08 Mar 97 00:46:33 EST To: 6042-forum@theory.lcs.mit.edu Subject: PS #4 Lecture notes 6, 7 and Handout 11 are on the web. (http://theory.lcs.mit.edu/classes/6.042) They are relevant to this week's problem set. Alex.  1,, Mail-from: From alexv@theory.lcs.mit.edu Fri Mar 7 19:52:31 1997 Return-Path: Received: from whimbrel.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA28983; Sat, 08 Mar 97 00:50:45 EST From: alexv@theory.lcs.mit.edu (Alex Vasilescu) Received: by whimbrel.lcs.mit.edu (5.65c/TOC-1.2C) id AA10330; Sat, 08 Mar 97 00:52:31 EST Date: Sat, 08 Mar 97 00:52:31 EST Message-Id: <199703080552.AA10330@whimbrel.lcs.mit.edu> To: 6042-forum@theory.lcs.mit.edu Subject: PS #5 *** EOOH *** Return-Path: From: alexv@theory.lcs.mit.edu (Alex Vasilescu) Date: Sat, 08 Mar 97 00:52:31 EST To: 6042-forum@theory.lcs.mit.edu Subject: PS #5 Lecture notes 6, 7 and Handout 11 are on the web. (http://theory.lcs.mit.edu/classes/6.042) They are relevant to this week's problem set. Alex.  1,, Mail-from: From karger@theory.lcs.mit.edu Mon Mar 10 14:45:47 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA21255; Mon, 10 Mar 97 19:48:31 EST From: karger@theory.lcs.mit.edu (David R. Karger) Received: by ibis (SMI-8.6/TOC-1.2C) id TAA27129; Mon, 10 Mar 1997 19:45:47 -0500 Date: Mon, 10 Mar 1997 19:45:47 -0500 Message-Id: <199703110045.TAA27129@ibis> To: 6042-forum@theory.lcs.mit.edu Subject: proving algorithm correctness *** EOOH *** Return-Path: From: karger@theory.lcs.mit.edu (David R. Karger) Date: Mon, 10 Mar 1997 19:45:47 -0500 To: 6042-forum@theory.lcs.mit.edu Subject: proving algorithm correctness Based on some questions I've been getting, I've put together a handout on "how to prove algorithms correct." It covers the 3 techniques we've used in class. I put it together in hurry, because I thought some of you would want to refer to it before handing in the homework. So it probably has quite a few typos. But the main ideas are there. I'll hand it out in class once I have had a chance to do some editing. -David Karger  1,, Mail-from: From karger@theory.lcs.mit.edu Wed Mar 12 07:40:21 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA28550; Wed, 12 Mar 97 12:43:03 EST From: karger@theory.lcs.mit.edu (David R. Karger) Received: by ibis (SMI-8.6/TOC-1.2C) id MAA00950; Wed, 12 Mar 1997 12:40:21 -0500 Date: Wed, 12 Mar 1997 12:40:21 -0500 Message-Id: <199703121740.MAA00950@ibis> To: 6042-forum Subject: pset correction *** EOOH *** Return-Path: From: karger@theory.lcs.mit.edu (David R. Karger) Date: Wed, 12 Mar 1997 12:40:21 -0500 To: 6042-forum Subject: pset correction in pset 6, there's a type on the first problem. the 4th action is to give the _ticket_ to the conductor and get on (so the passenger no longer has the ticket).  1,, Mail-from: From karger@theory.lcs.mit.edu Wed Mar 12 15:20:01 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA07115; Wed, 12 Mar 97 20:22:45 EST Received: by ibis (SMI-8.6/TOC-1.2C) id UAA01567; Wed, 12 Mar 1997 20:20:01 -0500 Date: Wed, 12 Mar 1997 20:20:01 -0500 Message-Id: <199703130120.UAA01567@ibis> From: "David R. Karger" To: 6042-forum Subject: [gupta@theory.lcs.mit.edu: another ps6 typo] *** EOOH *** Return-Path: Date: Wed, 12 Mar 1997 20:20:01 -0500 From: "David R. Karger" To: 6042-forum Subject: [gupta@theory.lcs.mit.edu: another ps6 typo] ------- Start of forwarded message ------- From: gupta@theory.lcs.mit.edu (David Gupta) Date: Wed, 12 Mar 97 15:33:21 EST To: karger Subject: another ps6 typo Hi, In problem 12.a., The W should be a theta. David ------- End of forwarded message -------  1,, Mail-from: From karger@theory.lcs.mit.edu Fri Mar 14 10:02:06 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA16949; Fri, 14 Mar 97 15:04:51 EST Received: by ibis (SMI-8.6/TOC-1.2C) id PAA06329; Fri, 14 Mar 1997 15:02:06 -0500 Date: Fri, 14 Mar 1997 15:02:06 -0500 Message-Id: <199703142002.PAA06329@ibis> From: "David R. Karger" To: 6042-forum *** EOOH *** Return-Path: Date: Fri, 14 Mar 1997 15:02:06 -0500 From: "David R. Karger" To: 6042-forum In the "cyclic shift" problem, note that any 3 elements of the list can be cyclically shifted; for example, 1,2,3,4,5,6 ----> 1,4,3,5,2,6 is a 3 element shift involving the elements 2,4, and 5  1,, Mail-from: From karger@theory.lcs.mit.edu Fri Mar 14 10:36:33 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA17665; Fri, 14 Mar 97 15:39:18 EST Received: by ibis (SMI-8.6/TOC-1.2C) id PAA06361; Fri, 14 Mar 1997 15:36:33 -0500 Date: Fri, 14 Mar 1997 15:36:33 -0500 Message-Id: <199703142036.PAA06361@ibis> From: "David R. Karger" To: 6042-forum Subject: problem set *** EOOH *** Return-Path: Date: Fri, 14 Mar 1997 15:36:33 -0500 From: "David R. Karger" To: 6042-forum Subject: problem set As an intermediate step, you might want to restrict attention to 3-element cyclic shifts of 3 adjacent elements in the list. That is, shifts like 1,5,3,6,4,2---->1,3,6,5,4,2  1,, Mail-from: From karger@theory.lcs.mit.edu Fri Mar 14 12:13:38 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA19668; Fri, 14 Mar 97 17:16:24 EST From: karger@theory.lcs.mit.edu (David R. Karger) Received: by ibis (SMI-8.6/TOC-1.2C) id RAA06485; Fri, 14 Mar 1997 17:13:38 -0500 Date: Fri, 14 Mar 1997 17:13:38 -0500 Message-Id: <199703142213.RAA06485@ibis> To: 6042-forum Subject: practice exam *** EOOH *** Return-Path: From: karger@theory.lcs.mit.edu (David R. Karger) Date: Fri, 14 Mar 1997 17:13:38 -0500 To: 6042-forum Subject: practice exam the practice exam has been posted on the web. Due to time constraints that limited the amount of revision, it is somewhat harder than I expect the exam to be. It will be covered at the monday review sessions.  1,, Mail-from: From karger@theory.lcs.mit.edu Fri Mar 14 13:11:19 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA21138; Fri, 14 Mar 97 18:14:06 EST Received: by ibis (SMI-8.6/TOC-1.2C) id SAA06538; Fri, 14 Mar 1997 18:11:19 -0500 Date: Fri, 14 Mar 1997 18:11:19 -0500 Message-Id: <199703142311.SAA06538@ibis> From: "David R. Karger" To: 6042-forum Subject: exam *** EOOH *** Return-Path: Date: Fri, 14 Mar 1997 18:11:19 -0500 From: "David R. Karger" To: 6042-forum Subject: exam It has been brought to my attention that one is not supposed to have a problem set due the week of the exam. Because of its timing, my intent had been to distribute 1/2 a problem set (which you already have) before the exam, and another half after. Although this does give you a net of 1 cancelled problem set, it turns out that this does not meet the MIT standards. Unfortunately, it is now to late to repair the error: it would be unfair to those who have already begun it for me to cancel the tuesday problem set. I will avoid this problem next exam. Regarding the exam, some of you may have noticed that the practice exam does not cover cardinality or pigeonholing arguments. In order to give you a chance to encounter those first on problem sets, I have decided to hold those two topics over until the next exam. They will not be addressed on this one. -David Karger  1,, Mail-from: From tiuzzol@MIT.EDU Fri Mar 14 17:56:54 1997 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA24268; Fri, 14 Mar 97 22:56:55 EST Received: from RINGWORLD.MIT.EDU by MIT.EDU with SMTP id AA02233; Fri, 14 Mar 97 22:56:49 EST Received: (from tiuzzol@localhost) by ringworld.MIT.EDU (8.6.11/8.6.11) id WAA02665; Fri, 14 Mar 1997 22:56:54 -0500 Date: Fri, 14 Mar 1997 22:56:54 -0500 From: Terri Iuzzolino Message-Id: <199703150356.WAA02665@ringworld.MIT.EDU> To: 6042-forum@theory.lcs.mit.edu, alexv@theory.lcs.mit.edu Subject: Re: Exam Review *** EOOH *** Return-Path: Date: Fri, 14 Mar 1997 22:56:54 -0500 From: Terri Iuzzolino To: 6042-forum@theory.lcs.mit.edu, alexv@theory.lcs.mit.edu Subject: Re: Exam Review There will also be office hours on Monday from about 4-5:30pm covering the problem set (NE43-3rd floor lounge as usual). Terri  1,, Mail-from: From karger@theory.lcs.mit.edu Sun Mar 16 18:46:55 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA17054; Sun, 16 Mar 97 23:49:41 EST Received: by ibis (SMI-8.6/TOC-1.2C) id XAA10177; Sun, 16 Mar 1997 23:46:55 -0500 Date: Sun, 16 Mar 1997 23:46:55 -0500 Message-Id: <199703170446.XAA10177@ibis> From: "David R. Karger" To: 6042-forum Subject: reading for quiz *** EOOH *** Return-Path: Date: Sun, 16 Mar 1997 23:46:55 -0500 From: "David R. Karger" To: 6042-forum Subject: reading for quiz I've been asked about the readings from Rosen that are relevant to the quiz. Here's a rough list: 1.1-1.6 2.1-2.5 3 6.1-6.5 (we'll do 6.6 tuesday, but it won't be on the quiz) the state machine and algorithm correctness handouts  1,, Mail-from: From alexv@theory.lcs.mit.edu Tue Mar 18 12:06:04 1997 Return-Path: Received: from whimbrel.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA28535; Tue, 18 Mar 97 17:04:12 EST From: alexv@theory.lcs.mit.edu (Alex Vasilescu) Received: by whimbrel.lcs.mit.edu (5.65c/TOC-1.2C) id AA00255; Tue, 18 Mar 97 17:06:04 EST Date: Tue, 18 Mar 97 17:06:04 EST Message-Id: <199703182206.AA00255@whimbrel.lcs.mit.edu> To: 6042-forum *** EOOH *** Return-Path: From: alexv@theory.lcs.mit.edu (Alex Vasilescu) Date: Tue, 18 Mar 97 17:06:04 EST To: 6042-forum We have put on the web the solutions to: 1. Problem Set 6 2. Practice Quiz 1 Solutions 3. Selected tutorial problem solutions (We were not planning to handout any but since people asked .... We may add more later this evening) 4. Lecture 11 Good luck studying! -- Your TAs.  1,, Mail-from: From alexv@theory.lcs.mit.edu Tue Mar 18 12:20:17 1997 Return-Path: Received: from whimbrel.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA28908; Tue, 18 Mar 97 17:18:23 EST From: alexv@theory.lcs.mit.edu (Alex Vasilescu) Received: by whimbrel.lcs.mit.edu (5.65c/TOC-1.2C) id AA00261; Tue, 18 Mar 97 17:20:17 EST Date: Tue, 18 Mar 97 17:20:17 EST Message-Id: <199703182220.AA00261@whimbrel.lcs.mit.edu> To: 6042-forum Subject: Quiz 1 *** EOOH *** Return-Path: From: alexv@theory.lcs.mit.edu (Alex Vasilescu) Date: Tue, 18 Mar 97 17:20:17 EST To: 6042-forum Subject: Quiz 1 The 6.042 Exam will be held in two rooms. We would like an even split of student between the two rooms. So.... Alex's students should go to room 3-270 Daniele's students should go to room 3-370.  1,, Mail-from: From alexv@theory.lcs.mit.edu Tue Mar 18 13:00:18 1997 Return-Path: Received: from lark.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA29869; Tue, 18 Mar 97 17:58:18 EST From: alexv@theory.lcs.mit.edu (Alex Vasilescu) Received: by lark.lcs.mit.edu (5.65c/TOC-1.2C) id AA06415; Tue, 18 Mar 97 18:00:18 EST Date: Tue, 18 Mar 97 18:00:18 EST Message-Id: <199703182300.AA06415@lark.lcs.mit.edu> To: 6042-forum Subject: When is the Quiz? *** EOOH *** Return-Path: From: alexv@theory.lcs.mit.edu (Alex Vasilescu) Date: Tue, 18 Mar 97 18:00:18 EST To: 6042-forum Subject: When is the Quiz? For those who forgot: Quiz 1 will take place from 7pm--9pm in rooms 3-270(Alex' students) and 3-370(Daniele's students).  1,, Mail-from: From karger@theory.lcs.mit.edu Tue Mar 18 16:15:42 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA03369; Tue, 18 Mar 97 21:18:29 EST Received: by ibis (SMI-8.6/TOC-1.2C) id VAA14254; Tue, 18 Mar 1997 21:15:42 -0500 Date: Tue, 18 Mar 1997 21:15:42 -0500 Message-Id: <199703190215.VAA14254@ibis> From: "David R. Karger" To: 6042-forum Subject: new homework *** EOOH *** Return-Path: Date: Tue, 18 Mar 1997 21:15:42 -0500 From: "David R. Karger" To: 6042-forum Subject: new homework Those who weren't in class today might want to know: I distributed a new homework, due when you arrive at the quiz tomorrow. It shouldn't take you too long to complete, but I consider it important that you do so. Please download it from the web page and do it. -David Karger  1,, Mail-from: From karger@theory.lcs.mit.edu Tue Mar 18 16:17:22 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA03393; Tue, 18 Mar 97 21:20:09 EST Received: by ibis (SMI-8.6/TOC-1.2C) id VAA14260; Tue, 18 Mar 1997 21:17:22 -0500 Date: Tue, 18 Mar 1997 21:17:22 -0500 Message-Id: <199703190217.VAA14260@ibis> From: "David R. Karger" To: 6042-forum Subject: exam/calculators *** EOOH *** Return-Path: Date: Tue, 18 Mar 1997 21:17:22 -0500 From: "David R. Karger" To: 6042-forum Subject: exam/calculators You may bring a caclulator to the exam if you wish, but 1) no stored programs 2) it is unlikely to be of any use.  1,, Mail-from: From karger@theory.lcs.mit.edu Thu Mar 20 13:30:34 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA20723; Thu, 20 Mar 97 18:33:24 EST Received: by ibis (SMI-8.6/TOC-1.2C) id SAA18519; Thu, 20 Mar 1997 18:30:34 -0500 Date: Thu, 20 Mar 1997 18:30:34 -0500 Message-Id: <199703202330.SAA18519@ibis> From: "David R. Karger" To: 6042-forum Subject: pset 7 due april 1 *** EOOH *** Return-Path: Date: Thu, 20 Mar 1997 18:30:34 -0500 From: "David R. Karger" To: 6042-forum Subject: pset 7 due april 1 There was a date error on pset 7. it is due tuesday april 1 in class, as usual.  1,, Mail-from: From gupta@theory.lcs.mit.edu Fri Mar 21 13:01:09 1997 Return-Path: Received: from whimbrel.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA12254; Fri, 21 Mar 97 17:59:14 EST From: gupta@theory.lcs.mit.edu (David Gupta) Received: by whimbrel.lcs.mit.edu (5.65c/TOC-1.2C) id AA01469; Fri, 21 Mar 97 18:01:09 EST Date: Fri, 21 Mar 97 18:01:09 EST Message-Id: <199703212301.AA01469@whimbrel.lcs.mit.edu> To: 6042-forum *** EOOH *** Return-Path: From: gupta@theory.lcs.mit.edu (David Gupta) Date: Fri, 21 Mar 97 18:01:09 EST To: 6042-forum Hello all, I will be away the Monday after Spring Break. Those of you who are in my Monday tutorials should attend one of the other tutorials, listed on the course home page. It would be particularly good if you could attend my 7:00pm recitation on Tuesday. My apologies to all for whatever inconvenience this causes. David G.  1,, Mail-from: From karger@theory.lcs.mit.edu Mon Mar 24 10:38:45 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA21247; Mon, 24 Mar 97 15:41:37 EST Received: by ibis (SMI-8.6/TOC-1.2C) id PAA27775; Mon, 24 Mar 1997 15:38:45 -0500 Date: Mon, 24 Mar 1997 15:38:45 -0500 Message-Id: <199703242038.PAA27775@ibis> From: "David R. Karger" To: 6042-forum Subject: [mibs@MIT.EDU: tutorial moves] *** EOOH *** Return-Path: Date: Mon, 24 Mar 1997 15:38:45 -0500 From: "David R. Karger" To: 6042-forum Subject: [mibs@MIT.EDU: tutorial moves] ------- Start of forwarded message ------- Date: Mon, 24 Mar 1997 11:12:56 +0000 To: karger@lcs.MIT.EDU From: mibs@MIT.EDU (Mibsy Brooks) Subject: tutorial moves On Monday, 4/28 your tutorials (which I believe are still being held) have been moved to different rooms due to Masterworks presentations. The section meeting at 2pm in 34-302 will move to 26-314 The section meeting at 2pm in 34-303 will move to 24-121 The section meeting at 2pm in 34-304 will move to 36-839 Mibsy ------- End of forwarded message -------  1,, Mail-from: From miccianc@theory.lcs.mit.edu Fri Mar 28 11:55:02 1997 Return-Path: Received: from lark.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA20076; Fri, 28 Mar 97 16:52:56 EST Received: by lark.lcs.mit.edu (5.65c/TOC-1.2C) id AA07943; Fri, 28 Mar 97 16:55:02 EST Date: Fri, 28 Mar 97 16:55:02 EST Message-Id: <199703282155.AA07943@lark.lcs.mit.edu> From: Daniele Micciancio To: 6042-forum Subject: PS7 correction *** EOOH *** Return-Path: Date: Fri, 28 Mar 97 16:55:02 EST From: Daniele Micciancio To: 6042-forum Subject: PS7 correction In problem set 7, problem 4, the relation $R$ should be defined as {(x,y): f(x)>f(y) or x=y} instead of {(x,y): f(x)>=f(y)}. Daniele.  1,, Mail-from: From miccianc@theory.lcs.mit.edu Fri Mar 28 12:26:29 1997 Return-Path: Received: from lark.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA20671; Fri, 28 Mar 97 17:24:24 EST Received: by lark.lcs.mit.edu (5.65c/TOC-1.2C) id AA07950; Fri, 28 Mar 97 17:26:29 EST Date: Fri, 28 Mar 97 17:26:29 EST Message-Id: <199703282226.AA07950@lark.lcs.mit.edu> From: Daniele Micciancio To: 6042-forum Subject: PS7 correction *** EOOH *** Return-Path: Date: Fri, 28 Mar 97 17:26:29 EST From: Daniele Micciancio To: 6042-forum Subject: PS7 correction The word "minimum" in problem 5.b be should be replaced by "minimal". Daniele.  1,, Mail-from: From karger@theory.lcs.mit.edu Fri Mar 28 12:40:41 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA20988; Fri, 28 Mar 97 17:43:35 EST Received: by ibis (SMI-8.6/TOC-1.2C) id RAA11377; Fri, 28 Mar 1997 17:40:41 -0500 Date: Fri, 28 Mar 1997 17:40:41 -0500 Message-Id: <199703282240.RAA11377@ibis> From: "David R. Karger" To: 6042-forum Subject: grading *** EOOH *** Return-Path: Date: Fri, 28 Mar 1997 17:40:41 -0500 From: "David R. Karger" To: 6042-forum Subject: grading As some of you may recall, there were some problems regarding the grading of the early problem sets---confusion among the graders about whether optional problems were counted toward grades or not. At the time, I asked you to hold on to your problem sets so that we could straighten things out later. Now's a good time, since you've just done a quiz and won't need to review the psets for a while. Please bring _all_ of your graded problem sets to tutorial on monday. We will check them against grades and fix the inconsistencies. -David Karger  1,, Mail-from: From karger@theory.lcs.mit.edu Mon Apr 3 13:36:56 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA10212; Mon, 31 Mar 97 18:39:54 EST Received: by ibis (SMI-8.6/TOC-1.2C) id SAA16306; Mon, 31 Mar 1997 18:36:56 -0500 Date: Mon, 31 Mar 1997 18:36:56 -0500 Message-Id: <199703312336.SAA16306@ibis> From: "David R. Karger" To: 6042-forum Subject: problem sets *** EOOH *** Return-Path: Date: Mon, 31 Mar 1997 18:36:56 -0500 From: "David R. Karger" To: 6042-forum Subject: problem sets Just a reminder. Please deliver to us (in class tomorrow if possilbe) all past problem sets so that we can correct some discrepancies in the grading. We promise not to read the answers again; this is purely an issue of some inconsistent computations.  1,, Mail-from: From karger@theory.lcs.mit.edu Tue Apr 1 07:43:54 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA02008; Tue, 01 Apr 97 12:46:51 EST Received: by ibis (SMI-8.6/TOC-1.2C) id MAA18700; Tue, 1 Apr 1997 12:43:54 -0500 Date: Tue, 1 Apr 1997 12:43:54 -0500 Message-Id: <199704011743.MAA18700@ibis> From: "David R. Karger" To: 6042-forum Subject: no class *** EOOH *** Return-Path: Date: Tue, 1 Apr 1997 12:43:54 -0500 From: "David R. Karger" To: 6042-forum Subject: no class We all seem to have been granted a bit of an extension on our spring (?) break---Enjoy! Since there is no class today, the problem set will be due thursday. No late extension beyond that. The next problem set will also be handed out on thursday.  1,, Mail-from: From tiuzzol@MIT.EDU Tue Apr 1 09:14:48 1997 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA03476; Tue, 01 Apr 97 14:14:48 EST Received: from RINGWORLD.MIT.EDU by MIT.EDU with SMTP id AA18021; Tue, 1 Apr 97 14:14:34 EST Received: (from tiuzzol@localhost) by ringworld.MIT.EDU (8.6.11/8.6.11) id OAA00987 for 6042-forum@theory.lcs.mit.edu; Tue, 1 Apr 1997 14:14:48 -0500 Date: Tue, 1 Apr 1997 14:14:48 -0500 From: Terri Iuzzolino Message-Id: <199704011914.OAA00987@ringworld.MIT.EDU> To: 6042-forum@theory.lcs.mit.edu Subject: Tuesday tutorial *** EOOH *** Return-Path: Date: Tue, 1 Apr 1997 14:14:48 -0500 From: Terri Iuzzolino To: 6042-forum@theory.lcs.mit.edu Subject: Tuesday tutorial Needless to say, because of the snow, and also because Dave has been snowed out of Boston, the Tuesday 7pm tutorial tonight is cancelled. Terri  1,, Mail-from: From dimitrip@theory.lcs.mit.edu Thu Apr 3 14:35:22 1997 Return-Path: Received: from phoinix.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA26219; Thu, 03 Apr 97 19:42:15 EST Received: from phoinix.lcs.mit.edu by phoinix.lcs.mit.edu (5.65c/TOC-1.2C) id AA02932; Thu, 03 Apr 97 19:35:25 EST Message-Id: <199704040035.AA02932@phoinix.lcs.mit.edu> To: 6042-forum Subject: office hours Date: Thu, 03 Apr 97 19:35:22 -0500 From: dimitrip@theory.lcs.mit.edu *** EOOH *** Return-Path: To: 6042-forum Subject: office hours Date: Thu, 03 Apr 97 19:35:22 -0500 From: dimitrip@theory.lcs.mit.edu Hello, Next Monday I will be holding office hours 10am -12 noon. This change might become permanent. Dimitri  1,, Mail-from: From karger@theory.lcs.mit.edu Thu Apr 3 16:51:25 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA28154; Thu, 03 Apr 97 21:54:24 EST Received: by ibis (SMI-8.6/TOC-1.2C) id VAA23927; Thu, 3 Apr 1997 21:51:25 -0500 Date: Thu, 3 Apr 1997 21:51:25 -0500 Message-Id: <199704040251.VAA23927@ibis> From: "David R. Karger" To: 6042-forum Subject: more tutorials *** EOOH *** Return-Path: Date: Thu, 3 Apr 1997 21:51:25 -0500 From: "David R. Karger" To: 6042-forum Subject: more tutorials As I mentioned in class, many of you seem interested in smaller tutorials. Our kind TAs have volunteered, and I am arranging some tutorials for Monday at 4PM. How many depends on how many express an interest. If you would like to move to a M4 tutorial, please send mail to 6042-headta stating this fact.  1,, Mail-from: From karger@theory.lcs.mit.edu Fri Apr 4 02:23:32 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA05057; Fri, 04 Apr 97 07:26:31 EST Received: by ibis (SMI-8.6/TOC-1.2C) id HAA25067; Fri, 4 Apr 1997 07:23:32 -0500 Date: Fri, 4 Apr 1997 07:23:32 -0500 Message-Id: <199704041223.HAA25067@ibis> From: "David R. Karger" To: 6042-forum Subject: definitions *** EOOH *** Return-Path: Date: Fri, 4 Apr 1997 07:23:32 -0500 From: "David R. Karger" To: 6042-forum Subject: definitions You may notice that the text defines a simple path as one that uses each _edge_ at most once. We have chosen to define it as one that uses each _vertex_ at most once, and this is the definition you should use. There's a lot of disagreement about graph definitions---a path that uses each edge at most once is often called a "trail"---the only important rule is that everyone should pick a definition and stick with it. -d  1,, Mail-from: From karger@theory.lcs.mit.edu Fri Apr 4 10:07:09 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA13981; Fri, 04 Apr 97 15:10:09 EST Received: by ibis (SMI-8.6/TOC-1.2C) id PAA25715; Fri, 4 Apr 1997 15:07:09 -0500 Date: Fri, 4 Apr 1997 15:07:09 -0500 Message-Id: <199704042007.PAA25715@ibis> From: "David R. Karger" To: 6042-forum Subject: cycles and circuits *** EOOH *** Return-Path: Date: Fri, 4 Apr 1997 15:07:09 -0500 From: "David R. Karger" To: 6042-forum Subject: cycles and circuits Just a reminder. As I mentioned before spring break, the term "cycle" is used as shorthand for "simple circuit", ie one with no repeated vertices. ------- Start of forwarded message ------- To: karger@MIT.EDU Subject: question Date: Fri, 04 Apr 1997 14:59:38 EST I just have a question concerning problems 6-8. I had the impression from the book that a cycle is the same thing as a circuit...thus when question 6 asked us to show iff for circuits and cycles I had no idea what it meant... I was wondering if you can clear that up for me....thanks ------- End of forwarded message -------  1,, Mail-from: From karger@theory.lcs.mit.edu Fri Apr 4 10:57:47 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA15252; Fri, 04 Apr 97 16:00:46 EST Received: by ibis (SMI-8.6/TOC-1.2C) id PAA25795; Fri, 4 Apr 1997 15:57:47 -0500 Date: Fri, 4 Apr 1997 15:57:47 -0500 Message-Id: <199704042057.PAA25795@ibis> From: "David R. Karger" To: 6042-forum Subject: homework *** EOOH *** Return-Path: Date: Fri, 4 Apr 1997 15:57:47 -0500 From: "David R. Karger" To: 6042-forum Subject: homework A clarification based on someone's confused question. Theorem 0.1 in the homework is what you _will_ prove. It is not something you can use to prove the homework problems!  1,, Mail-from: From miccianc@theory.lcs.mit.edu Fri Apr 4 11:36:31 1997 Return-Path: Received: from lark.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA16292; Fri, 04 Apr 97 16:34:22 EST Received: by lark.lcs.mit.edu (5.65c/TOC-1.2C) id AA09029; Fri, 04 Apr 97 16:36:31 EST Date: Fri, 04 Apr 97 16:36:31 EST Message-Id: <199704042136.AA09029@lark.lcs.mit.edu> From: Daniele Micciancio To: 6042-forum Subject: Psol7 *** EOOH *** Return-Path: Date: Fri, 04 Apr 97 16:36:31 EST From: Daniele Micciancio To: 6042-forum Subject: Psol7 Solutions to problem set 7 are available on the course webpage. daniele.  1,, Mail-from: From karger@theory.lcs.mit.edu Fri Apr 4 13:04:58 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA18352; Fri, 04 Apr 97 18:07:58 EST Received: by ibis (SMI-8.6/TOC-1.2C) id SAA26324; Fri, 4 Apr 1997 18:04:58 -0500 Date: Fri, 4 Apr 1997 18:04:58 -0500 Message-Id: <199704042304.SAA26324@ibis> From: "David R. Karger" To: 6042-forum Subject: extra tutorial *** EOOH *** Return-Path: Date: Fri, 4 Apr 1997 18:04:58 -0500 From: "David R. Karger" To: 6042-forum Subject: extra tutorial Dimitri will hold an extra tutorial M at 4 in 34-302.  1,, Mail-from: From miccianc@theory.lcs.mit.edu Mon Apr 7 07:01:31 1997 Return-Path: Received: from lark.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA25343; Mon, 07 Apr 97 10:59:21 EDT Received: by lark.lcs.mit.edu (5.65c/TOC-1.2C) id AA09418; Mon, 07 Apr 97 11:01:31 EDT Date: Mon, 07 Apr 97 11:01:31 EDT Message-Id: <199704071501.AA09418@lark.lcs.mit.edu> From: Daniele Micciancio To: 6042-forum Subject: PS8 clarification *** EOOH *** Return-Path: Date: Mon, 07 Apr 97 11:01:31 EDT From: Daniele Micciancio To: 6042-forum Subject: PS8 clarification Problem set 8, problem 4. To make it work you should interpret the sentence "node of degree k" as "node with k children". Daniele.  1,, Mail-from: From karger@theory.lcs.mit.edu Mon Apr 7 07:24:36 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA25963; Mon, 07 Apr 97 11:27:48 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id LAA01539; Mon, 7 Apr 1997 11:24:36 -0400 Date: Mon, 7 Apr 1997 11:24:36 -0400 Message-Id: <199704071524.LAA01539@ibis> From: "David R. Karger" To: miccianc@theory.lcs.mit.edu Cc: 6042-forum In-Reply-To: <199704071501.AA09418@lark.lcs.mit.edu> (message from Daniele Micciancio on Mon, 07 Apr 97 11:01:31 EDT) Subject: Re: PS8 clarification *** EOOH *** Return-Path: Date: Mon, 7 Apr 1997 11:24:36 -0400 From: "David R. Karger" To: miccianc@theory.lcs.mit.edu Cc: 6042-forum In-Reply-To: <199704071501.AA09418@lark.lcs.mit.edu> (message from Daniele Micciancio on Mon, 07 Apr 97 11:01:31 EDT) Subject: Re: PS8 clarification Please disregard Daniele's message. The problem refers to a "free" tree of the kind I discussed last lecture. Since it isn't rooted, there is no notion of parents or children. So degree k means degree k.  1,, Mail-from: From tiuzzol@MIT.EDU Mon Apr 7 15:42:14 1997 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA06462; Mon, 07 Apr 97 19:42:15 EDT Received: from RINGWORLD.MIT.EDU by MIT.EDU with SMTP id AA22159; Mon, 7 Apr 97 18:41:57 EST Received: (from tiuzzol@localhost) by ringworld.MIT.EDU (8.6.11/8.6.11) id TAA24887 for 6042-forum@theory.lcs.mit.edu; Mon, 7 Apr 1997 19:42:14 -0400 Date: Mon, 7 Apr 1997 19:42:14 -0400 From: Terri Iuzzolino Message-Id: <199704072342.TAA24887@ringworld.MIT.EDU> To: 6042-forum@theory.lcs.mit.edu Subject: PS 8 *** EOOH *** Return-Path: Date: Mon, 7 Apr 1997 19:42:14 -0400 From: Terri Iuzzolino To: 6042-forum@theory.lcs.mit.edu Subject: PS 8 As you may have noticed, PS8 is due on Thursday. It's easier than past ones, so you should really finish it tonight. But in case you don't, I'll have office hours on Wednesday 10pm-midnight in NE43-3rd floor lounge. I'll answer questions individually (as opposed to the group answers we have on the boards on Monday), so please work on the pset before you come, and feel free to send TAs mail if you have questions.... Also, if you received your quiz in class last Thursday, got 7 or fewer points on problem 1 of your quiz OR if you got no points for your name (some of them were inadvertantly left blank), please bring in your quiz tomorrow at class, and give it to me at the beginning of class to regrade. I'll have finished grading it by the end. No one will lose points but you might get some. Note that if you either got your quiz handed back today, or if you received 3 or 4 points for your name, or >=8 points for problem 1, don't give me your test. Terri  1,, Mail-from: From karger@theory.lcs.mit.edu Tue Apr 8 18:06:55 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA04375; Tue, 08 Apr 97 22:10:02 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id WAA04649; Tue, 8 Apr 1997 22:06:55 -0400 Date: Tue, 8 Apr 1997 22:06:55 -0400 Message-Id: <199704090206.WAA04649@ibis> From: "David R. Karger" To: 6042-forum Subject: lecture error *** EOOH *** Return-Path: Date: Tue, 8 Apr 1997 22:06:55 -0400 From: "David R. Karger" To: 6042-forum Subject: lecture error I've discovered some "writeos" in my closed form for the value of sum (i*x^i) in class today. The correct answer is in the notes which will go out thursday; I am bringing this error to your attention so it won't creep into your homework solutions.  1,, Mail-from: From karger@theory.lcs.mit.edu Tue Apr 8 21:24:19 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA07076; Wed, 09 Apr 97 01:27:22 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id BAA04848; Wed, 9 Apr 1997 01:24:19 -0400 Date: Wed, 9 Apr 1997 01:24:19 -0400 Message-Id: <199704090524.BAA04848@ibis> From: "David R. Karger" To: 6042-forum Subject: pset 9 *** EOOH *** Return-Path: Date: Wed, 9 Apr 1997 01:24:19 -0400 From: "David R. Karger" To: 6042-forum Subject: pset 9 Handout 23, problem set 9, is now on the web. It will be handed out in class thursday.  1,, Mail-from: From dimitrip@theory.lcs.mit.edu Wed Apr 9 12:48:41 1997 Return-Path: Received: from phoinix.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA23356; Wed, 09 Apr 97 16:55:36 EDT Received: from phoinix.lcs.mit.edu by phoinix.lcs.mit.edu (5.65c/TOC-1.2C) id AA11998; Wed, 09 Apr 97 16:48:42 EDT Message-Id: <199704092048.AA11998@phoinix.lcs.mit.edu> To: 6042-forum Cc: dimitrip Subject: 4pm tutorial Date: Wed, 09 Apr 97 16:48:41 -0400 From: dimitrip@theory.lcs.mit.edu *** EOOH *** Return-Path: To: 6042-forum Cc: dimitrip Subject: 4pm tutorial Date: Wed, 09 Apr 97 16:48:41 -0400 From: dimitrip@theory.lcs.mit.edu Hello, Only one person showed up for the 4pm tutorial last Monday. Those of you who are still interested in a 4pm tutorial please send mail to dimitrip@theory.lcs. Dimitri  1,, Mail-from: From tiuzzol@MIT.EDU Wed Apr 9 14:24:12 1997 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA25059; Wed, 09 Apr 97 18:24:23 EDT Received: from RINGWORLD.MIT.EDU by MIT.EDU with SMTP id AA06539; Wed, 9 Apr 97 18:24:23 EDT Received: (from tiuzzol@localhost) by ringworld.MIT.EDU (8.6.11/8.6.11) id SAA12103 for 6042-forum@theory.lcs.mit.edu; Wed, 9 Apr 1997 18:24:12 -0400 Date: Wed, 9 Apr 1997 18:24:12 -0400 From: Terri Iuzzolino Message-Id: <199704092224.SAA12103@ringworld.MIT.EDU> To: 6042-forum@theory.lcs.mit.edu Subject: Quiz 1 regrades *** EOOH *** Return-Path: Date: Wed, 9 Apr 1997 18:24:12 -0400 From: Terri Iuzzolino To: 6042-forum@theory.lcs.mit.edu Subject: Quiz 1 regrades So, it looks like Professor Karger has decided to give some more of you a lucky break on problem 1 of the quiz. For those of you who solved the problem 1 as (1^3 + 2^3 + ... + n^3) = (1 + 1 + ... + n)^2 bring in your problems to be regraded. Please give them to me at the _beginning_ of lecture, and they'll be ready by the end. Thanks! Terri  1,, Mail-from: From karger@theory.lcs.mit.edu Wed Apr 9 20:16:58 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA03132; Thu, 10 Apr 97 00:20:01 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id AAA06741; Thu, 10 Apr 1997 00:16:58 -0400 Date: Thu, 10 Apr 1997 00:16:58 -0400 Message-Id: <199704100416.AAA06741@ibis> From: "David R. Karger" To: 6042-forum Subject: [lfrench@MIT.EDU: 6042 PS] *** EOOH *** Return-Path: Date: Thu, 10 Apr 1997 00:16:58 -0400 From: "David R. Karger" To: 6042-forum Subject: [lfrench@MIT.EDU: 6042 PS] Some answers ------- Start of forwarded message ------- To: karger@MIT.EDU Subject: 6042 PS Date: Wed, 09 Apr 1997 23:59:20 EDT First, in problem 3, can you explain the second part of the problem (how many paths...)? How many answers are we supposed to have? Since the graph is symmetric, the answer is the same for all the non-center vertices. Also, in problem 5, is the graph undirected? yes ------- End of forwarded message -------  1,, Mail-from: From karger@theory.lcs.mit.edu Wed Apr 9 20:23:42 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA03246; Thu, 10 Apr 97 00:26:46 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id AAA06758; Thu, 10 Apr 1997 00:23:42 -0400 Date: Thu, 10 Apr 1997 00:23:42 -0400 Message-Id: <199704100423.AAA06758@ibis> From: "David R. Karger" To: 6042-forum Subject: Re: problem 6 *** EOOH *** Return-Path: Date: Thu, 10 Apr 1997 00:23:42 -0400 From: "David R. Karger" To: 6042-forum Subject: Re: problem 6 Date: Thu, 10 Apr 1997 00:23:47 -0400 hope i catch you: on problem 6, what's the difference between a cycle and circuit? the book defines them as the same on page 465 As discussed in lecture and notes, I am using different definitions from the book. circut: any sequence of vertices connected by edges that ends up back at the starting vertex cycle: a circuit with no repeated vertices In other words, cycle is to circuit as simple path is to path.  1,, Mail-from: From karger@theory.lcs.mit.edu Thu Apr 10 14:32:10 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA22583; Thu, 10 Apr 97 18:35:15 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id SAA08437; Thu, 10 Apr 1997 18:32:10 -0400 Date: Thu, 10 Apr 1997 18:32:10 -0400 Message-Id: <199704102232.SAA08437@ibis> From: "David R. Karger" To: 6042-forum Subject: quiz preparations *** EOOH *** Return-Path: Date: Thu, 10 Apr 1997 18:32:10 -0400 From: "David R. Karger" To: 6042-forum Subject: quiz preparations The current plan is as follows. I will hand out a problem set next tuesday. It will also serve as a review set/practice quiz for the exam (it will be different from the quiz in that it is likely to take more than 2 hours). It will be due at the recitation which will be held Tuesday night, the day before the exam. At that recitation, solutions to the set will be handed out and the TAs will go over the solutions and answer general questions. There will be no homework due the following Tuesday. Tuesday before the exam is patriot's day as well as the second seder night of passover. If this or other issues such as travel prevent you from attending the review session or handing in the problem set on time, send mail to 6042-headta. Send the mail EARLY so that alternate arrangements can be made. Also, if you have any major objections to the plan as currently given, send mail directly to me. -David Karger  1,, Mail-from: From karger@theory.lcs.mit.edu Fri Apr 11 04:55:06 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA02296; Fri, 11 Apr 97 08:58:11 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id IAA09979; Fri, 11 Apr 1997 08:55:06 -0400 Date: Fri, 11 Apr 1997 08:55:06 -0400 Message-Id: <199704111255.IAA09979@ibis> From: "David R. Karger" To: 6042-forum Subject: tutorials *** EOOH *** Return-Path: Date: Fri, 11 Apr 1997 08:55:06 -0400 From: "David R. Karger" To: 6042-forum Subject: tutorials Based on our discussion in class, I propose that we had an extra tutorial at each of 1,2, and 3PM on Monday. This will only work, of course, if some people or groups are willing to move to the new tutorial (which will be led by a different TA). If you are willing to move, send mail with your tutorial time and TA (in the following example format: 1 Gupta for a 1PM with David Gupta). If we get enough positive responses, we will schedule the extra tutorials. -David Karger  1,, Mail-from: From karger@theory.lcs.mit.edu Fri Apr 11 09:30:41 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA07671; Fri, 11 Apr 97 13:33:45 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id NAA10198; Fri, 11 Apr 1997 13:30:41 -0400 Date: Fri, 11 Apr 1997 13:30:41 -0400 Message-Id: <199704111730.NAA10198@ibis> From: "David R. Karger" To: 6042-forum Subject: Tutorial changes *** EOOH *** Return-Path: Date: Fri, 11 Apr 1997 13:30:41 -0400 From: "David R. Karger" To: 6042-forum Subject: Tutorial changes I left out on my last mail: if you can change tutorials, send your info to 6042-headta.  1,, Mail-from: From dimitrip@theory.lcs.mit.edu Sun Apr 13 12:00:03 1997 Return-Path: Received: from peacock.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA07203; Sun, 13 Apr 97 15:59:05 EDT Received: from peacock.lcs.mit.edu by peacock.lcs.mit.edu (5.65c/TOC-1.2C) id AA19509; Sun, 13 Apr 97 16:00:04 EDT Message-Id: <199704132000.AA19509@peacock.lcs.mit.edu> To: 6042-forum Cc: 6042-teachers Subject: extra tutorial Date: Sun, 13 Apr 97 16:00:03 -0400 From: dimitrip@theory.lcs.mit.edu *** EOOH *** Return-Path: To: 6042-forum Cc: 6042-teachers Subject: extra tutorial Date: Sun, 13 Apr 97 16:00:03 -0400 From: dimitrip@theory.lcs.mit.edu Hello, The Monday 4pm tutorial has been cancelled. Dimitri  1,, Mail-from: From gupta@theory.lcs.mit.edu Sun Apr 13 15:48:55 1997 Return-Path: Received: from owl.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA10065; Sun, 13 Apr 97 19:51:04 EDT From: gupta@theory.lcs.mit.edu (David Gupta) Received: by owl.lcs.mit.edu (5.65c/TOC-1.2C) id AA03710; Sun, 13 Apr 97 19:48:55 EDT Date: Sun, 13 Apr 97 19:48:55 EDT Message-Id: <199704132348.AA03710@owl.lcs.mit.edu> To: 6042-forum Subject: old problem sets *** EOOH *** Return-Path: From: gupta@theory.lcs.mit.edu (David Gupta) Date: Sun, 13 Apr 97 19:48:55 EDT To: 6042-forum Subject: old problem sets Hello all, Please remember to bring any old problem sets that you still haven't given back for re-totalling to tutorial on Monday. David G.  1,, Mail-from: From gupta@theory.lcs.mit.edu Sun Apr 13 15:50:57 1997 Return-Path: Received: from owl.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA10111; Sun, 13 Apr 97 19:53:06 EDT From: gupta@theory.lcs.mit.edu (David Gupta) Received: by owl.lcs.mit.edu (5.65c/TOC-1.2C) id AA03714; Sun, 13 Apr 97 19:50:57 EDT Date: Sun, 13 Apr 97 19:50:57 EDT Message-Id: <199704132350.AA03714@owl.lcs.mit.edu> To: 6042-forum Subject: revised lecture 14 notes *** EOOH *** Return-Path: From: gupta@theory.lcs.mit.edu (David Gupta) Date: Sun, 13 Apr 97 19:50:57 EDT To: 6042-forum Subject: revised lecture 14 notes Hello all, The version of the lecture notes for lecture 14 is slightly revised from what was handed out in recitation. In particular it contains a few more definitions in its final section. (This section wasn't in the version handed out in recitation). David G.  1,, Mail-from: From karger@theory.lcs.mit.edu Sun Apr 13 16:56:53 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA11115; Sun, 13 Apr 97 21:00:00 EDT From: karger@theory.lcs.mit.edu (David R. Karger) Received: by ibis (SMI-8.6/TOC-1.2C) id UAA16166; Sun, 13 Apr 1997 20:56:53 -0400 Date: Sun, 13 Apr 1997 20:56:53 -0400 Message-Id: <199704140056.UAA16166@ibis> To: 6042-forum Subject: typo on problem 1 *** EOOH *** Return-Path: From: karger@theory.lcs.mit.edu (David R. Karger) Date: Sun, 13 Apr 1997 20:56:53 -0400 To: 6042-forum Subject: typo on problem 1 The problem set due tuesday has a typo that makes problem 1(b) impossible. The correction: there are 22 teams, not 21. You might want to think about why 21 teams makes 1(b) impossible...  1,, Mail-from: From karger@theory.lcs.mit.edu Sun Apr 13 17:16:41 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA11420; Sun, 13 Apr 97 21:19:48 EDT From: karger@theory.lcs.mit.edu (David R. Karger) Received: by ibis (SMI-8.6/TOC-1.2C) id VAA16222; Sun, 13 Apr 1997 21:16:41 -0400 Date: Sun, 13 Apr 1997 21:16:41 -0400 Message-Id: <199704140116.VAA16222@ibis> To: 6042-forum Subject: notes 16 *** EOOH *** Return-Path: From: karger@theory.lcs.mit.edu (David R. Karger) Date: Sun, 13 Apr 1997 21:16:41 -0400 To: 6042-forum Subject: notes 16 a draft of notes 16 on recurrences is on the web. A corrected version will be handed out in class, but the draft is there in case you want to peek at the material on recurrences. That material is covered fully in the book, though.  1,, Mail-from: From karger@theory.lcs.mit.edu Sun Apr 13 21:58:42 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA14638; Mon, 14 Apr 97 02:01:49 EDT From: karger@theory.lcs.mit.edu (David R. Karger) Received: by ibis (SMI-8.6/TOC-1.2C) id BAA17140; Mon, 14 Apr 1997 01:58:42 -0400 Date: Mon, 14 Apr 1997 01:58:42 -0400 Message-Id: <199704140558.BAA17140@ibis> To: 6042-forum Subject: makeup quiz *** EOOH *** Return-Path: From: karger@theory.lcs.mit.edu (David R. Karger) Date: Mon, 14 Apr 1997 01:58:42 -0400 To: 6042-forum Subject: makeup quiz Just a reminder: if your schedule (eg passover) prevents you from being ready for the quiz on wednsday evening, make sure to contact 6042-headta so that we can arrange a makeup exam time.  1,, Mail-from: From karger@theory.lcs.mit.edu Mon Apr 14 06:32:43 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA21835; Mon, 14 Apr 97 10:35:51 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id KAA18457; Mon, 14 Apr 1997 10:32:43 -0400 Date: Mon, 14 Apr 1997 10:32:43 -0400 Message-Id: <199704141432.KAA18457@ibis> From: "David R. Karger" To: 6042-forum Subject: PS 9 *** EOOH *** Return-Path: Date: Mon, 14 Apr 1997 10:32:43 -0400 From: "David R. Karger" To: 6042-forum Subject: PS 9 ------- Start of forwarded message ------- Date: Sun, 13 Apr 1997 16:12:10 -0400 To: "David R. Karger" Subject: PS 9 Are we assuming in problem 10 that n is a power of two? Or are we treating T(n/2) as T([n/2])? ------- End of forwarded message ------- For simplicity, you may assume $n$ is a power of 2.  1,, Mail-from: From karger@theory.lcs.mit.edu Mon Apr 14 06:35:22 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA22148; Mon, 14 Apr 97 10:38:30 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id KAA18463; Mon, 14 Apr 1997 10:35:22 -0400 Date: Mon, 14 Apr 1997 10:35:22 -0400 Message-Id: <199704141435.KAA18463@ibis> From: "David R. Karger" To: 6042-forum Subject: pset 9 *** EOOH *** Return-Path: Date: Mon, 14 Apr 1997 10:35:22 -0400 From: "David R. Karger" To: 6042-forum Subject: pset 9 ------- Start of forwarded message ------- Date: Mon, 14 Apr 1997 00:30:00 -0400 To: karger@theory.lcs.mit.edu (David R. Karger) Subject: Re: typo on problem 1 There is a very simple solution where all the teams are simply paired up and only play each other, in which case both parts of the question are trivial. Is that an acceptable solution, since it fully proves the possibility of scheduling the games? Thanks, ------- End of forwarded message ------- Note that as stated, problem 1 does not allow you to specify the 14 teams a team has to play. It only allows you to specify when/where the games are played.  1,, Mail-from: From karger@theory.lcs.mit.edu Mon Apr 14 06:53:32 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA22804; Mon, 14 Apr 97 10:56:44 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id KAA18512; Mon, 14 Apr 1997 10:53:32 -0400 Date: Mon, 14 Apr 1997 10:53:32 -0400 Message-Id: <199704141453.KAA18512@ibis> From: "David R. Karger" To: 6042-forum Subject: [achakra@MIT.EDU: Problem 1] *** EOOH *** Return-Path: Date: Mon, 14 Apr 1997 10:53:32 -0400 From: "David R. Karger" To: 6042-forum Subject: [achakra@MIT.EDU: Problem 1] ------- Start of forwarded message ------- Date: Mon, 14 Apr 1997 10:54:09 -0400 To: karger@theory.lcs.mit.edu Subject: Problem 1 Do we assume 21 teams for Problem 1a and 22 teams for Problem 1b? Or do we assume 22 teams for both parts? ------- End of forwarded message ------- You can assume 22 teams for both parts (though for part a, it doesn't matter).  1,, Mail-from: From karger@theory.lcs.mit.edu Tue Apr 15 17:33:46 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA19676; Tue, 15 Apr 97 21:36:54 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id VAA22504; Tue, 15 Apr 1997 21:33:46 -0400 Date: Tue, 15 Apr 1997 21:33:46 -0400 Message-Id: <199704160133.VAA22504@ibis> From: "David R. Karger" To: 6042-forum Subject: revised plan *** EOOH *** Return-Path: Date: Tue, 15 Apr 1997 21:33:46 -0400 From: "David R. Karger" To: 6042-forum Subject: revised plan For those of you not in class today, I made a small change in the plan I posted: the practice exam is NOT graded. You don't have to turn it in. It will be gone over in the review section. Instread, there will be a graded pset handed out this thursday, due april 29.  1,, Mail-from: From karger@theory.lcs.mit.edu Tue Apr 15 17:35:17 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA19722; Tue, 15 Apr 97 21:38:24 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id VAA22508; Tue, 15 Apr 1997 21:35:17 -0400 Date: Tue, 15 Apr 1997 21:35:17 -0400 Message-Id: <199704160135.VAA22508@ibis> From: "David R. Karger" To: 6042-forum Subject: review sections *** EOOH *** Return-Path: Date: Tue, 15 Apr 1997 21:35:17 -0400 From: "David R. Karger" To: 6042-forum Subject: review sections Review sections will be held in 3-270 on 4/22 from 5-7 and from 7-9. They will cover the review exam and any questions it generates.  1,, Mail-from: From karger@theory.lcs.mit.edu Tue Apr 15 17:36:32 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA19761; Tue, 15 Apr 97 21:39:40 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id VAA22510; Tue, 15 Apr 1997 21:36:32 -0400 Date: Tue, 15 Apr 1997 21:36:32 -0400 Message-Id: <199704160136.VAA22510@ibis> From: "David R. Karger" To: 6042-forum Subject: drop day *** EOOH *** Return-Path: Date: Tue, 15 Apr 1997 21:36:32 -0400 From: "David R. Karger" To: 6042-forum Subject: drop day If any of you are thinking of dropping this course but are waiting out your quiz 2 grade, please let 6042-headta know so that we can set up an "early warning system" to make sure that you get your info in time.  1,, Mail-from: From alexv@theory.lcs.mit.edu Thu Apr 17 04:38:47 1997 Return-Path: Received: from owl.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA25912; Thu, 17 Apr 97 08:40:58 EDT From: alexv@theory.lcs.mit.edu (Alex Vasilescu) Received: by owl.lcs.mit.edu (5.65c/TOC-1.2C) id AA06045; Thu, 17 Apr 97 08:38:47 EDT Date: Thu, 17 Apr 97 08:38:47 EDT Message-Id: <199704171238.AA06045@owl.lcs.mit.edu> To: 6042-forum *** EOOH *** Return-Path: From: alexv@theory.lcs.mit.edu (Alex Vasilescu) Date: Thu, 17 Apr 97 08:38:47 EDT To: 6042-forum I will not be holding office hours this Friday 4-6. I will hold office hours on Wednesday 10:30am -- 12:30 pm in NE43-308. Good luck studying! -- Alex  1,, Mail-from: From gupta@theory.lcs.mit.edu Thu Apr 17 16:10:35 1997 Return-Path: Received: from owl.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA24099; Thu, 17 Apr 97 20:12:46 EDT From: gupta@theory.lcs.mit.edu (David Gupta) Received: by owl.lcs.mit.edu (5.65c/TOC-1.2C) id AA06586; Thu, 17 Apr 97 20:10:35 EDT Date: Thu, 17 Apr 97 20:10:35 EDT Message-Id: <199704180010.AA06586@owl.lcs.mit.edu> To: 6042-forum Subject: recitations tomorrow *** EOOH *** Return-Path: From: gupta@theory.lcs.mit.edu (David Gupta) Date: Thu, 17 Apr 97 20:10:35 EDT To: 6042-forum Subject: recitations tomorrow Hello all, I'm covering Alex's recitations (still in the usual rooms) tomorrow. Daniele's 3pm recitation is meeting in 34-301 with Alex's. Also, there are a number of things being handed out in recitation this week. David G.  1,, Mail-from: From karger@theory.lcs.mit.edu Thu Apr 17 18:04:58 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA26933; Thu, 17 Apr 97 22:08:07 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id WAA27881; Thu, 17 Apr 1997 22:04:58 -0400 Date: Thu, 17 Apr 1997 22:04:58 -0400 Message-Id: <199704180204.WAA27881@ibis> From: "David R. Karger" To: 6042-forum Subject: quiz coverage *** EOOH *** Return-Path: Date: Thu, 17 Apr 1997 22:04:58 -0400 From: "David R. Karger" To: 6042-forum Subject: quiz coverage I was asked to send mail about what the quiz covers. Coverage begins at lecture 10---functions and their applications to counting and pigeonhole---and continues fully through lecture 17 (rules for counting) with some light coverage of binomial coefficients as well. Of course, though no question will focus exclusively on material from quiz 1, some of the questions will involve inductions, proofs of algorithm correctness, and so forth. Good luck studying!  1,, Mail-from: From miccianc@theory.lcs.mit.edu Fri Apr 18 08:34:21 1997 Return-Path: Received: from lark.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA17893; Fri, 18 Apr 97 12:32:04 EDT Received: by lark.lcs.mit.edu (5.65c/TOC-1.2C) id AA11221; Fri, 18 Apr 97 12:34:21 EDT Date: Fri, 18 Apr 97 12:34:21 EDT Message-Id: <199704181634.AA11221@lark.lcs.mit.edu> From: Daniele Micciancio To: 6042-forum Subject: *** EOOH *** Return-Path: Date: Fri, 18 Apr 97 12:34:21 EDT From: Daniele Micciancio To: 6042-forum Subject: problem set 9 solutions will be posted on the webpage today by 7pm. daniele.  1,, Mail-from: From tiuzzol@MIT.EDU Fri Apr 18 10:17:16 1997 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA25076; Fri, 18 Apr 97 14:17:17 EDT Received: from M38-370-12.MIT.EDU by MIT.EDU with SMTP id AA03962; Fri, 18 Apr 97 14:17:18 EDT From: tiuzzol@MIT.EDU Received: by m38-370-12.MIT.EDU (5.x/4.7) id AA08933; Fri, 18 Apr 1997 14:17:16 -0400 Date: Fri, 18 Apr 1997 14:17:16 -0400 Message-Id: <9704181817.AA08933@m38-370-12.MIT.EDU> To: 6042-forum@theory.lcs.mit.edu Subject: Tests, handouts, and test review etc. information *** EOOH *** Return-Path: From: tiuzzol@MIT.EDU Date: Fri, 18 Apr 1997 14:17:16 -0400 To: 6042-forum@theory.lcs.mit.edu Subject: Tests, handouts, and test review etc. information A couple of things: There will be office hours this upcoming week on Monday from 4-6 (Dave) and 7-9pm (Terri) Tuesday from 10am to 2pm (Daniele and Dimitri) Wednesday from 10:30am to 12:30noon (Alex) all in the NE43-308/conference room/lounge area of Tech Square. If the lobby door is locked, knock loudly. There will be two quiz reviews on Tuesday, 4/22 in 3-270 5-7 (Daniele) and from 7-9 (Terri). Problem set 9 solutions will be on the web by tonight. Problem set 10 was handed out in class yesterday, and is due the week after next. Some Tutorial solutions (probably 6, 8, and 9) will be on the web by 5pm tonight. Have a good weekend! Terri  1,, Mail-from: From karger@theory.lcs.mit.edu Fri Apr 18 14:01:30 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA09918; Fri, 18 Apr 97 18:04:41 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id SAA29523; Fri, 18 Apr 1997 18:01:30 -0400 Date: Fri, 18 Apr 1997 18:01:30 -0400 Message-Id: <199704182201.SAA29523@ibis> From: "David R. Karger" To: 6042-forum Subject: grade audit *** EOOH *** Return-Path: Date: Fri, 18 Apr 1997 18:01:30 -0400 From: "David R. Karger" To: 6042-forum Subject: grade audit This message is for those of you who HAVE NOT yet turned in your old problem sets for an "audit." We need everyone to turn them in, because a software system bug which we recently identified has caused certain grades to be erased. Without your problem sets, we cannot verify that we have all of your scores, so you may be surprised by the class grade that you get! So if you have not yet done so, please bring your old problem sets to the quiz so that we can fix up our records.  1,, Mail-from: From karger@theory.lcs.mit.edu Fri Apr 18 14:02:59 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA09978; Fri, 18 Apr 97 18:06:10 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id SAA29525; Fri, 18 Apr 1997 18:02:59 -0400 Date: Fri, 18 Apr 1997 18:02:59 -0400 Message-Id: <199704182202.SAA29525@ibis> From: "David R. Karger" To: 6042-forum Subject: grade audit *** EOOH *** Return-Path: Date: Fri, 18 Apr 1997 18:02:59 -0400 From: "David R. Karger" To: 6042-forum Subject: grade audit If you have already turned in your old problem sets for audit, and did not pick them up in class or recitation, then you will have another chance to get them at the review sections next tuesday. You will know the sets were audited because there will be a little dot on the top corner.  1,, Mail-from: From gupta@theory.lcs.mit.edu Sun Apr 20 16:00:28 1997 Return-Path: Received: from owl.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA04453; Sun, 20 Apr 97 20:02:39 EDT From: gupta@theory.lcs.mit.edu (David Gupta) Received: by owl.lcs.mit.edu (5.65c/TOC-1.2C) id AA00668; Sun, 20 Apr 97 20:00:28 EDT Date: Sun, 20 Apr 97 20:00:28 EDT Message-Id: <199704210000.AA00668@owl.lcs.mit.edu> To: 6042-forum Subject: reminder *** EOOH *** Return-Path: From: gupta@theory.lcs.mit.edu (David Gupta) Date: Sun, 20 Apr 97 20:00:28 EDT To: 6042-forum Subject: reminder Hello all, Please remember that there are no tutorials this week. David G.  1,, Mail-from: From karger@theory.lcs.mit.edu Mon Apr 21 08:54:14 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA07615; Mon, 21 Apr 97 12:57:27 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id MAA04701; Mon, 21 Apr 1997 12:54:14 -0400 Date: Mon, 21 Apr 1997 12:54:14 -0400 Message-Id: <199704211654.MAA04701@ibis> From: "David R. Karger" To: 6042-forum Subject: review set solutions *** EOOH *** Return-Path: Date: Mon, 21 Apr 1997 12:54:14 -0400 From: "David R. Karger" To: 6042-forum Subject: review set solutions For those of you who want to go over them early, I have placed a draft of the review set solutions on the course web page. This draft will be completed and gone over during the review session tomorrow night.  1,, Mail-from: From karger@theory.lcs.mit.edu Mon Apr 21 09:36:21 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA10923; Mon, 21 Apr 97 13:39:32 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id NAA04738; Mon, 21 Apr 1997 13:36:21 -0400 Date: Mon, 21 Apr 1997 13:36:21 -0400 Message-Id: <199704211736.NAA04738@ibis> From: "David R. Karger" To: 6042-forum Subject: exam *** EOOH *** Return-Path: Date: Mon, 21 Apr 1997 13:36:21 -0400 From: "David R. Karger" To: 6042-forum Subject: exam The upcoming exam operates under the same restrictions as the previous exam: closed book 1 crib sheet calculators, but none running programs  1,, Mail-from: From tiuzzol@MIT.EDU Wed Apr 23 13:47:33 1997 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA23914; Wed, 23 Apr 97 17:47:35 EDT Received: from BILL-THE-CAT.MIT.EDU by MIT.EDU with SMTP id AA14392; Wed, 23 Apr 97 17:47:35 EDT From: tiuzzol@MIT.EDU Received: by bill-the-cat.MIT.EDU (5.x/4.7) id AA01990; Wed, 23 Apr 1997 17:47:33 -0400 Date: Wed, 23 Apr 1997 17:47:33 -0400 Message-Id: <9704232147.AA01990@bill-the-cat.MIT.EDU> Content-Type: text Apparently-To: 6042-forum@theory.lcs.mit.edu *** EOOH *** Return-Path: From: tiuzzol@MIT.EDU Date: Wed, 23 Apr 1997 17:47:33 -0400 Content-Type: text Since a lot of you have been asking, the test is tonight (Wednesday) from 7-9pm in 3-270 and 3-370 (same places as last time) Good luck! Terri  0, unseen,, *** EOOH *** Mail-from: From karger@theory.lcs.mit.edu Thu May 1 14:27:12 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA04203; Thu, 01 May 97 18:30:34 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id SAA26636; Thu, 1 May 1997 18:27:12 -0400 Date: Thu, 1 May 1997 18:27:12 -0400 Message-Id: <199705012227.SAA26636@ibis> From: "David R. Karger" To: 6042-forum Subject: grades In our ongoing attempt to resolve our 6.042 grades problem, we are instituting the following procedure. When you are in posession of both the strips that we give you (with the grades we think you have) and your problem sets, bring both the strips and the problems sets to your tutorial. Your TA will verify any errors, take the strips, and update the spreadsheet. Hopefully this will finally resolve the problem. Thanks, David Karger  0, unseen,, *** EOOH *** Mail-from: From tiuzzol@MIT.EDU Fri May 9 22:53:14 1997 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA22925; Sat, 10 May 97 02:53:17 EDT Received: from M2-032-13.MIT.EDU by MIT.EDU with SMTP id AA21484; Sat, 10 May 97 02:53:16 EDT From: tiuzzol@MIT.EDU Received: by m2-032-13.MIT.EDU (5.x/4.7) id AA25477; Sat, 10 May 1997 02:53:14 -0400 Date: Sat, 10 May 1997 02:53:14 -0400 Message-Id: <9705100653.AA25477@m2-032-13.MIT.EDU> To: 6042-forum@theory.lcs.mit.edu Subject: Grades sheets and statistics Here are the statistics for the numbers you have on your grade sheet. These numbers actually apply to the next set of sheets you'll receive in tutorial on Monday. Please check these sheets over, and again, if there are any corrections, let us know. Hopefully everything should be correct though. Overall-Score Quiz 2 Quiz 1 Tutorials Pset Total ------------------------------------------------------------------- Perfect 100.0 120 104 100 100 Average 72.5 90 62 73 79 Median 74.2 90 63 73 84 Std Dev 10.1 12.7 14.8 13.5 17 Terri PS: I do not know what will be an A and what will be a B.  0, unseen,, *** EOOH *** Mail-from: From miccianc@theory.lcs.mit.edu Sat May 10 11:28:31 1997 Return-Path: Received: from lark.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA28720; Sat, 10 May 97 15:26:02 EDT Received: by lark.lcs.mit.edu (5.65c/TOC-1.2C) id AA14117; Sat, 10 May 97 15:28:31 EDT Date: Sat, 10 May 97 15:28:31 EDT Message-Id: <199705101928.AA14117@lark.lcs.mit.edu> From: Daniele Micciancio To: 6042-forum Subject: I won't hold office hours this monday because I'll be out of town. Dimitri will hold office hours on Monday from 10 to 12 instead of the usual time. Daniele.  0, unseen,, *** EOOH *** Mail-from: From karger@theory.lcs.mit.edu Tue May 13 13:22:02 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA01327; Tue, 13 May 97 17:25:33 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id RAA22294; Tue, 13 May 1997 17:22:02 -0400 Date: Tue, 13 May 1997 17:22:02 -0400 Message-Id: <199705132122.RAA22294@ibis> From: "David R. Karger" To: 6042-forum Subject: anonymous pset 8 I have a pset 8 with no name. Done on graph paper in black ink. Any claimants?  0, unseen,, *** EOOH *** Mail-from: From karger@theory.lcs.mit.edu Thu May 15 13:37:44 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA16153; Thu, 15 May 97 17:41:15 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id RAA28644; Thu, 15 May 1997 17:37:44 -0400 Date: Thu, 15 May 1997 17:37:44 -0400 Message-Id: <199705152137.RAA28644@ibis> From: "David R. Karger" To: 6042-forum I plan to verify your grades for psets 10 and 11 by mailing them to (only) you. Please let me know if you are concerned about having these two grades going out in the mail. -David Karger  0, unseen,, *** EOOH *** Mail-from: From karger@theory.lcs.mit.edu Thu May 15 14:17:58 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA16813; Thu, 15 May 97 18:21:31 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id SAA28666; Thu, 15 May 1997 18:17:58 -0400 Date: Thu, 15 May 1997 18:17:58 -0400 Message-Id: <199705152217.SAA28666@ibis> From: "David R. Karger" To: 6042-forum Subject: correction Before I get deluged with mail, let me clarify: please send mail only if you DO NOT want your grades on 10/11 emailed to you -David  0, unseen,, *** EOOH *** Mail-from: From karger@theory.lcs.mit.edu Thu May 15 14:22:53 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA16894; Thu, 15 May 97 18:26:25 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id SAA28668; Thu, 15 May 1997 18:22:53 -0400 Date: Thu, 15 May 1997 18:22:53 -0400 Message-Id: <199705152222.SAA28668@ibis> From: "David R. Karger" To: 6042-forum Subject: lecture correction In tpyical form, I finished the last lecture with an error. In discussing the proof of the Chernoff bound on random variable X, I applied the markov inequality to e^X. Instead it should be applied to c^X, where c is the constant in the theorem. Check the notes... -David  0, unseen,, *** EOOH *** Mail-from: From dimitrip@theory.lcs.mit.edu Thu May 15 15:20:56 1997 Return-Path: Received: from phoinix.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA17974; Thu, 15 May 97 19:28:15 EDT Received: from phoinix.lcs.mit.edu by phoinix.lcs.mit.edu (5.65c/TOC-1.2C) id AA02278; Thu, 15 May 97 19:20:57 EDT Message-Id: <199705152320.AA02278@phoinix.lcs.mit.edu> To: 6042-forum Cc: dimitrip Subject: office hours Date: Thu, 15 May 97 19:20:56 -0400 From: dimitrip@theory.lcs.mit.edu Hello, I will hold office hours on Monday 12 noon to 2pm. If you have corrections for your last grade strip, that's the time to do it. If you have not received your grade strip (and you are in my tutorial sections), come prepared. That is, bring all your problem sets & quizes so that if there are any mistakes we can correct them on the spot. If you have not received your grade strip and you cannot make it on Monday 12-2, send me mail NOW, because I will become unavailable from Monday afternoon to Friday morning. Cheers, Dimitri  0, unseen,, *** EOOH *** Mail-from: From karger@theory.lcs.mit.edu Thu May 15 16:17:51 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA18775; Thu, 15 May 97 20:21:24 EDT From: karger@theory.lcs.mit.edu (David R. Karger) Received: by ibis (SMI-8.6/TOC-1.2C) id UAA28846; Thu, 15 May 1997 20:17:51 -0400 Date: Thu, 15 May 1997 20:17:51 -0400 Message-Id: <199705160017.UAA28846@ibis> To: 6042-forum Subject: survey As I announced in class, there is a new handout (#37) that I would greatly appreciate your filling out. I am taking part in an overhaul of 6.042 this summer and your input will help us do a better job. Just bring the survey to the final. Thanks, David Karger  0, unseen,, *** EOOH *** Mail-from: From karger@theory.lcs.mit.edu Fri May 16 06:02:21 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA28052; Fri, 16 May 97 10:05:54 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id KAA03422; Fri, 16 May 1997 10:02:21 -0400 Date: Fri, 16 May 1997 10:02:21 -0400 Message-Id: <199705161402.KAA03422@ibis> From: "David R. Karger" To: 6042-forum In-Reply-To: <199705160813.AA24320@theory.lcs.mit.edu> (alexv@theory.lcs.mit.edu) Subject: Re: office hours Actually, as I announced in class yesterday, my office hours will be from 1-3.  0, unseen,, *** EOOH *** Mail-from: From karger@theory.lcs.mit.edu Sun May 18 05:45:30 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA25100; Sun, 18 May 97 09:49:05 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id JAA16994; Sun, 18 May 1997 09:45:30 -0400 Date: Sun, 18 May 1997 09:45:30 -0400 Message-Id: <199705181345.JAA16994@ibis> From: "David R. Karger" To: 6042-forum Subject: problems for practicing expectations I have received a couple of requests for problems to practice expectation concepts. I have placed a problem set covering this material and solutions to it on the class web page as handouts 39 and 40. -David Karger  0, unseen,, *** EOOH *** Mail-from: From karger@theory.lcs.mit.edu Sun May 18 05:59:33 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA25218; Sun, 18 May 97 10:03:08 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id JAA17823; Sun, 18 May 1997 09:59:33 -0400 Date: Sun, 18 May 1997 09:59:33 -0400 Message-Id: <199705181359.JAA17823@ibis> From: "David R. Karger" To: 6042-forum Subject: notes 25 I have placed the lecture notes for lecture 25 (deviations from the mean) on the class web page.  0, unseen,, *** EOOH *** Mail-from: From karger@theory.lcs.mit.edu Sun May 18 12:01:10 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA28314; Sun, 18 May 97 16:04:44 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id QAA29655; Sun, 18 May 1997 16:01:10 -0400 Date: Sun, 18 May 1997 16:01:10 -0400 Message-Id: <199705182001.QAA29655@ibis> From: "David R. Karger" To: 6042-forum Subject: practice final questions ------- Start of forwarded message ------- Date: Sun, 18 May 1997 12:37:29 -0400 To: "David R. Karger" Subject: Questions on practice exam Dear Professor Karger, I'm trying to do the practice exam (Handout 36), and i'm having problems with: Problem 2 b. T(n) = T(n/2) + T(n/4) + and T(1) = 1 doesn't seem to give enough base cases. When i'm trying to calculate T(2), whould i assume that T(2/4) = 0 ? It is standard in such cases to assume T(2)=1 as well. This works because changing T(2) to something else only changes the answer by a constant factor, which disappears in the O-notation. Problem 3 b. How many pairs do 17 people form? When we say pairs, each person can "pair up" with only one other right? 17 people form 17-choose-2 = 136 pairs. we are considering all possible pair here. Thanks for your time, ------- End of forwarded message -------  0, unseen,, *** EOOH *** Mail-from: From miccianc@theory.lcs.mit.edu Sun May 18 12:36:16 1997 Return-Path: Received: from lark.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA28600; Sun, 18 May 97 16:33:42 EDT Received: by lark.lcs.mit.edu (5.65c/TOC-1.2C) id AA14732; Sun, 18 May 97 16:36:16 EDT Date: Sun, 18 May 97 16:36:16 EDT Message-Id: <199705182036.AA14732@lark.lcs.mit.edu> From: Daniele Micciancio To: 6042-forum Subject: office hours I will hold office hours on Tuesday 10-12 instead of Monday this week. Daniele  1,, Mail-from: From miccianc@theory.lcs.mit.edu Mon May 19 09:20:20 1997 Return-Path: Received: from lark.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA12732; Mon, 19 May 97 13:17:45 EDT Received: by lark.lcs.mit.edu (5.65c/TOC-1.2C) id AA14897; Mon, 19 May 97 13:20:20 EDT Date: Mon, 19 May 97 13:20:20 EDT Message-Id: <199705191720.AA14897@lark.lcs.mit.edu> From: Daniele Micciancio To: 6042-forum Subject: *** EOOH *** Return-Path: Date: Mon, 19 May 97 13:20:20 EDT From: Daniele Micciancio To: 6042-forum Subject: I have been asked to move my office hours to Thursday night at 7pm, as many students are expected to come at that time. I'll be in my office anyway Tuesday morning from 10 to 11 if any of you want to come. Daniele From tiuzzol@MIT.EDU Tue May 20 08:53:39 1997 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA05162; Tue, 20 May 97 12:53:41 EDT Received: from RINGWORLD.MIT.EDU by MIT.EDU with SMTP id AA28990; Tue, 20 May 97 12:53:40 EDT Received: (from tiuzzol@localhost) by ringworld.MIT.EDU (8.6.11/8.6.11) id MAA20788 for 6042-forum@theory.lcs.mit.edu; Tue, 20 May 1997 12:53:39 -0400 Date: Tue, 20 May 1997 12:53:39 -0400 From: Terri Iuzzolino Message-Id: <199705201653.MAA20788@ringworld.MIT.EDU> To: 6042-forum@theory.lcs.mit.edu Subject: office hours I will have office hours from 5pm to 11pm on Thursday night in Tech Square (NE43-3rd floor lounge). Terri PS: A draft of PS12 solutions is on the web From gupta@theory.lcs.mit.edu Tue May 20 15:11:35 1997 Return-Path: Received: from owl.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA13539; Tue, 20 May 97 19:14:02 EDT From: gupta@theory.lcs.mit.edu (David Gupta) Received: by owl.lcs.mit.edu (5.65c/TOC-1.2C) id AA05622; Tue, 20 May 97 19:11:35 EDT Date: Tue, 20 May 97 19:11:35 EDT Message-Id: <199705202311.AA05622@owl.lcs.mit.edu> To: 6042-forum Subject: office hours Hello all, My office hours this week will be 5-7pm Wednesday in the 3rd floor lounge of LCS. There should be someone holding office hours every day through Thursday, and these provide a good opportunity for people to bring in their slips and old homework so we can get grades corrected. David G. From gupta@theory.lcs.mit.edu Tue May 20 15:23:29 1997 Return-Path: Received: from owl.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA13730; Tue, 20 May 97 19:25:55 EDT From: gupta@theory.lcs.mit.edu (David Gupta) Received: by owl.lcs.mit.edu (5.65c/TOC-1.2C) id AA05652; Tue, 20 May 97 19:23:29 EDT Date: Tue, 20 May 97 19:23:29 EDT Message-Id: <199705202323.AA05652@owl.lcs.mit.edu> To: 6042-forum Subject: oops Hello all, I may have misled some people on problem 1.e. on the practice quiz at the Sunday review session. I neglected to mention two of the important things that one must first establish before trying to prove that a relation is a bijection. Namely, one must establish that it is a function and that it is defined (as a function) on the entire set that you want to be its domain. Then you can establish that the function is surjective and injective. Proving all four things makes the argument symmetric, as it should be. David G. From karger@theory.lcs.mit.edu Tue May 20 18:56:14 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA16657; Tue, 20 May 97 22:59:50 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id WAA04832; Tue, 20 May 1997 22:56:14 -0400 Date: Tue, 20 May 1997 22:56:14 -0400 Message-Id: <199705210256.WAA04832@ibis> From: "David R. Karger" To: 6042-forum In-Reply-To: <199705202343.TAA01035@hope.mit.edu> (message from Srikant Sarda on Tue, 20 May 1997 19:43:37 EDT) Subject: Re: final exam You can bring 3 double sided crib sheets to the final exam. But don't kill yourselves trying to build them. More effective to use the time studying. From: Srikant Sarda Date: Tue, 20 May 1997 19:43:37 EDT How many sheets of notes can we have for the final exam? Thanks Srikant From karger@theory.lcs.mit.edu Thu May 22 07:31:47 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA24350; Thu, 22 May 97 11:35:17 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id LAA16109; Thu, 22 May 1997 11:31:47 -0400 Date: Thu, 22 May 1997 11:31:47 -0400 Message-Id: <199705221531.LAA16109@ibis> From: "David R. Karger" To: 6042-forum Cc: gupta, miccianc, dimitrip, alexv, tiuzzol@mit.edu Just a reminder to all of you to make sure we have your grades right by checking the slips we gave you (which have all our information through pset 9 or so) and the email that we recently sent or shortly will be sending (for psets 9-11). If you find any bugs, it is your responsibility to straighten them out before the final exam. Good luck tomorrow. -David Karger From tiuzzol@theory.lcs.mit.edu Thu May 22 10:18:03 1997 Return-Path: Received: from peacock.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA28669; Thu, 22 May 97 14:16:33 EDT From: tiuzzol@theory.lcs.mit.edu (Terri Iuzzolino) Received: by peacock.lcs.mit.edu (5.65c/TOC-1.2C) id AA20703; Thu, 22 May 97 14:18:03 EDT Date: Thu, 22 May 97 14:18:03 EDT Message-Id: <199705221818.AA20703@peacock.lcs.mit.edu> To: 6042-forum@theory.lcs.mit.edu Subject: Tutorial solutions Tutorial solutions for Problem 1 on Tutorial 10, Tutorials 11, and 12 are on the web. I'm sorry I didn't manage to finish Tutorial 10. I hope the rest are useful. Terri From karger@theory.lcs.mit.edu Thu May 22 21:45:25 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA11876; Fri, 23 May 97 01:48:58 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id BAA11963; Fri, 23 May 1997 01:45:25 -0400 Date: Fri, 23 May 1997 01:45:25 -0400 Message-Id: <199705230545.BAA11963@ibis> From: "David R. Karger" To: 6042-forum Subject: grade checks We will be grading 6042 finals all of tomorrow afternoon in NE43 3rd floor. If you have not yet come by to correct your grades, that would be a good time. -David Karger From karger@theory.lcs.mit.edu Wed May 28 15:26:23 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA11659; Wed, 28 May 97 19:30:14 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id TAA08646; Wed, 28 May 1997 19:26:23 -0400 Date: Wed, 28 May 1997 19:26:23 -0400 Message-Id: <199705282326.TAA08646@ibis> From: "David R. Karger" To: 6042-forum Subject: grades Grades are now avilable for 6.042. You can get your grade in several ways: 1) Call my course secretary at 253 6098. This is the preferred remote method. 2) If phoning won't work, email your tutorial instructor. They may or may not have time to check and reply. I will not have time to respond before next week. 3) Come in to my office and pick up your final and grade. If you do this, please either bring a survey, fill one out while you are here, or be prepared to tell me that you already dropped one off at the final exam. Statistics for the final: median 120/200 mean 112/200 stdev 18.2 The median grade in the class was a B. -David Karger From be@theory.lcs.mit.edu Thu May 29 07:25:04 1997 Return-Path: Received: from swift.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA21901; Thu, 29 May 97 11:28:17 EDT From: be@theory.lcs.mit.edu (Be Blackburn) Received: by swift.lcs.mit.edu (5.65c/TOC-1.2C) id AA00646; Thu, 29 May 97 11:25:04 EDT Date: Thu, 29 May 97 11:25:04 EDT Message-Id: <199705291525.AA00646@swift.lcs.mit.edu> To: 6042-forum Subject: GRADES on Web SIS?? Hi, as per MIT policy- grades are given out ONLY to the person receiving them. Grades are NOT available by EMAIL. Anne Hunter tells me you can access YOUR grade on ``Web SIS''. Anyone know the exact Web address or way you do that?? thanks, Be From aidan@NOTHING.MIT.EDU Thu May 29 07:42:20 1997 Return-Path: Received: from NOTHING.MIT.EDU by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA22178; Thu, 29 May 97 11:41:51 EDT Received: (from aidan@localhost) by NOTHING.MIT.EDU (8.8.5/8.8.5) id LAA26778; Thu, 29 May 1997 11:42:20 -0400 From: "Aidan N.R. Low" Message-Id: <199705291542.LAA26778@NOTHING.MIT.EDU> To: be@theory.lcs.mit.edu (Be Blackburn) Cc: 6042-forum@theory.lcs.mit.edu Subject: Re: GRADES on Web SIS?? In-Reply-To: Your message of "Thu, 29 May 1997 11:25:04 EDT." <199705291525.AA00646@swift.lcs.mit.edu> Date: Thu, 29 May 1997 11:42:20 EDT Go to http://student.mit.edu. You'll need to be using Netscape (athena, mac, or windows) to do the whole rigamarole (sp?) about getting a digital certificate. It actually works pretty well. Aidan aidan@mit.edu http://www.mit.edu:8001/people/aidan/home.html From be@theory.lcs.mit.edu Thu May 29 08:24:23 1997 Return-Path: Received: from swift.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA23237; Thu, 29 May 97 12:27:36 EDT From: be@theory.lcs.mit.edu (Be Blackburn) Received: by swift.lcs.mit.edu (5.65c/TOC-1.2C) id AA00689; Thu, 29 May 97 12:24:23 EDT Date: Thu, 29 May 97 12:24:23 EDT Message-Id: <199705291624.AA00689@swift.lcs.mit.edu> To: 6042-forum Subject: yes, you can get YOUR 6.042 GRADE on Web SIS The WebSIS address is: http://student.mit.edu One needs to fetch a certificate first... Instructions and links are available on the main page. I would suggest that you recommend people use their Athena accounts to do this, as Netscape needs somewhere to store the certificate, and one's personal machine may not be the best bet. If Athena is used, one should use the US version of Netscape (start with the command netscape-US), because it has more powerful encryption capabilities. From karger@theory.lcs.mit.edu Mon Jun 2 08:19:47 1997 Return-Path: Received: from ibis (ibis.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA28345; Mon, 02 Jun 97 12:23:34 EDT Received: by ibis (SMI-8.6/TOC-1.2C) id MAA05326; Mon, 2 Jun 1997 12:19:47 -0400 Date: Mon, 2 Jun 1997 12:19:47 -0400 Message-Id: <199706021619.MAA05326@ibis> From: "David R. Karger" To: 6042-forum Subject: reporting error Someone pointed out a reporting error r.e. the final. The stdev was 36, not 18.