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,, Summary-line: 26-Feb jee@MIT.EDU [15] #Testing...1..2..3... Mail-from: From jee@MIT.EDU Thu Feb 26 11:37:36 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA12056; Thu, 26 Feb 98 16:39:14 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA09912; Thu, 26 Feb 98 16:38:00 EST Received: from W20-575-6.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA17907; Thu, 26 Feb 98 16:37:36 EST Sender: jee@MIT.EDU Message-Id: <34F5E09E.3C980F6D@MIT.EDU> Date: Thu, 26 Feb 1998 16:37:36 -0500 From: Roshan Gupta Organization: Massachusetts Institute of Technology X-Mailer: Mozilla 4.04 [en] (X11; I; SunOS 5.5.1 sun4m) Mime-Version: 1.0 To: 6042-help@theory.lcs.mit.edu Subject: Testing...1..2..3... Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit *** EOOH *** Sender: jee@MIT.EDU Date: Thu, 26 Feb 1998 16:37:36 -0500 From: Roshan Gupta Organization: Massachusetts Institute of Technology X-Mailer: Mozilla 4.04 [en] (X11; I; SunOS 5.5.1 sun4m) To: 6042-help@theory.lcs.mit.edu Subject: Testing...1..2..3... Here is a quick question: how do you prove that a rational number times and irrational number is irrational? My first instinct is to use a proof by contradiction, that is to prove that a ratoinal times an irrational number is rational. Unfortunately, I can't seem to figure that one out either. Thanks.  1,, Summary-line: 26-Feb to: jee@MIT.EDU [30] #Re: Testing...1..2..3... Mail-from: From meyer@theory.lcs.mit.edu Thu Feb 26 11:55:08 1998 Return-Path: Received: from stork.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA12294; Thu, 26 Feb 98 16:54:47 EST Received: by stork.lcs.mit.edu (5.65c/TOC-1.2C) id AA15662; Thu, 26 Feb 98 16:55:08 EST Date: Thu, 26 Feb 98 16:55:08 EST Message-Id: <199802262155.AA15662@stork.lcs.mit.edu> From: "Albert R. Meyer" To: jee@MIT.EDU Cc: 6042-help@theory.lcs.mit.edu In-Reply-To: <34F5E09E.3C980F6D@MIT.EDU> (message from Roshan Gupta on Thu, 26 Feb 1998 16:37:36 -0500) Subject: Re: Testing...1..2..3... Reply-To: 6042-meyer@theory.lcs.mit.edu *** EOOH *** Date: Thu, 26 Feb 98 16:55:08 EST From: "Albert R. Meyer" To: jee@MIT.EDU Cc: 6042-help@theory.lcs.mit.edu In-Reply-To: <34F5E09E.3C980F6D@MIT.EDU> (message from Roshan Gupta on Thu, 26 Feb 1998 16:37:36 -0500) Subject: Re: Testing...1..2..3... Reply-To: 6042-meyer@theory.lcs.mit.edu Sender: jee@MIT.EDU Date: Thu, 26 Feb 1998 16:37:36 -0500 From: Roshan Gupta Organization: Massachusetts Institute of Technology X-Mailer: Mozilla 4.04 [en] (X11; I; SunOS 5.5.1 sun4m) Here is a quick question: how do you prove that a rational number times and irrational number is irrational? My first instinct is to use a proof by contradiction, that is to prove that a ratoinal times an irrational number is rational. Unfortunately, I can't seem to figure that one out either. Thanks. Yes, suppose for contradiction that (n/m)x = k/l where n,m,k,l are nonnegative integers and x is a real number. Now prove that x is rational. Regards, A.  1,, Summary-line: 26-Feb luca@theory.lcs.mit.edu [39] #Re: Testing...1..2..3... Mail-from: From luca@theory.lcs.mit.edu Thu Feb 26 11:51:55 1998 Return-Path: Received: from ostrich (ostrich.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA12293; Thu, 26 Feb 98 16:54:47 EST Sender: luca@theory.lcs.mit.edu Message-Id: <34F5E3FB.62319AC4@theory.lcs.mit.edu> Date: Thu, 26 Feb 1998 16:51:55 -0500 From: Luca Trevisan X-Mailer: Mozilla 3.01Gold (X11; I; SunOS 4.1.4 sun4m) Mime-Version: 1.0 To: Roshan Gupta Cc: 6042-help@theory.lcs.mit.edu Subject: Re: Testing...1..2..3... References: <34F5E09E.3C980F6D@MIT.EDU> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit *** EOOH *** Sender: luca@theory.lcs.mit.edu Date: Thu, 26 Feb 1998 16:51:55 -0500 From: Luca Trevisan X-Mailer: Mozilla 3.01Gold (X11; I; SunOS 4.1.4 sun4m) To: Roshan Gupta Cc: 6042-help@theory.lcs.mit.edu Subject: Re: Testing...1..2..3... References: <34F5E09E.3C980F6D@MIT.EDU> Roshan Gupta wrote: > > Here is a quick question: how do you prove that a rational number times > and irrational number is irrational? My first instinct is to use a > proof by contradiction, that is to prove that a ratoinal times an > irrational number is rational. Unfortunately, I can't seem to figure > that one out either. Thanks. the proof by contradiction goes this way (you use the fact that a rational number divided by a non-zero rational number is rational): assume by contradiction that r is a non-zero rational, x is irrational, and r times x is rational. let r' = rx. then you have x = r'/r which is well-defined since r is non-zero. now, r'/r is rational, so x is rational and you reach a contradiction. QED observe that you have to assume that r is non-zero, since zero (that is rational) times an irrational number gives zero (rational). Best --Luca  1,, Summary-line: 26-Feb to: flattop@MIT.EDU [32] #Re: ps#4 Mail-from: From meyer@theory.lcs.mit.edu Thu Feb 26 12:10:26 1998 Return-Path: Received: from stork.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA12509; Thu, 26 Feb 98 17:10:05 EST Received: by stork.lcs.mit.edu (5.65c/TOC-1.2C) id AA15736; Thu, 26 Feb 98 17:10:26 EST Date: Thu, 26 Feb 98 17:10:26 EST Message-Id: <199802262210.AA15736@stork.lcs.mit.edu> From: "Albert R. Meyer" To: flattop@MIT.EDU In-Reply-To: <34F48CD6.392D@MIT.EDU> (flattop@MIT.EDU) Subject: Re: ps#4 Cc: 6042-help *** EOOH *** Date: Thu, 26 Feb 98 17:10:26 EST From: "Albert R. Meyer" To: flattop@MIT.EDU In-Reply-To: <34F48CD6.392D@MIT.EDU> (flattop@MIT.EDU) Subject: Re: ps#4 Cc: 6042-help Your offer of office hours is a nice one. You can announce it by emailing to 6042-students@theory.lcs.mit.edu. Also, put announcement on the web page under "News and Reminders". Regards, A. Sender: flattop@MIT.EDU Date: Wed, 25 Feb 1998 16:27:50 -0500 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Prof. Meyer, I'm thinking about having myself available in the Student Center Sunday night and Monday night to help people with ps#4. I'll e-mail out the other helpers if they want to join me. Is there a mailing list for all of the 6.042 students? I'll probably tell them the time and place Friday. What do you think of this? When will the solutions be available? jack  1,, Summary-line: 26-Feb to: 6042-help [49] #[jee@MIT.EDU: Re: Testing...1..2..3...] Mail-from: From meyer@theory.lcs.mit.edu Thu Feb 26 12:17:18 1998 Return-Path: Received: from stork.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA12630; Thu, 26 Feb 98 17:16:57 EST Received: by stork.lcs.mit.edu (5.65c/TOC-1.2C) id AA15758; Thu, 26 Feb 98 17:17:18 EST Date: Thu, 26 Feb 98 17:17:18 EST Message-Id: <199802262217.AA15758@stork.lcs.mit.edu> From: "Albert R. Meyer" To: 6042-help Subject: [jee@MIT.EDU: Re: Testing...1..2..3...] *** EOOH *** Date: Thu, 26 Feb 98 17:17:18 EST From: "Albert R. Meyer" To: 6042-help Subject: [jee@MIT.EDU: Re: Testing...1..2..3...] ------- Start of forwarded message ------- To: 6042-meyer@theory.lcs.mit.edu Subject: Re: Testing...1..2..3... In-Reply-To: Your message of "Thu, 26 Feb 1998 16:55:08 EST." <199802262155.AA15662@stork.lcs.mit.edu> Date: Thu, 26 Feb 1998 17:14:22 EST From: Roshan Gupta Thanks, I get it. x = (k/l) * (n/m) = (k*l)/(l*n) which is rational. X is defined as irrational, so that's the contradiction. Thanks again for the (really) fast reply. I have another quick question...how do you do problem 3 on the problem set? Sorry, I thought I would try. Roshan Gupta - ---------------------------------------------------------------------------- Sender: jee@MIT.EDU Date: Thu, 26 Feb 1998 16:37:36 -0500 From: Roshan Gupta Organization: Massachusetts Institute of Technology X-Mailer: Mozilla 4.04 [en] (X11; I; SunOS 5.5.1 sun4m) Here is a quick question: how do you prove that a rational number times and irrational number is irrational? My first instinct is to use a proof by contradiction, that is to prove that a ratoinal times an irrational number is rational. Unfortunately, I can't seem to figure that one out either. Thanks. Yes, suppose for contradiction that (n/m)x = k/l where n,m,k,l are nonnegative integers and x is a real number. Now prove that x is rational. Regards, A. ------- End of forwarded message -------  1,, Summary-line: 28-Feb seajaspe@MIT.EDU [17] #Problem 2 Mail-from: From seajaspe@MIT.EDU Sat Feb 28 03:54:07 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA00534; Sat, 28 Feb 98 08:54:43 EST Received: from PO7.MIT.EDU by MIT.EDU with SMTP id AA06942; Sat, 28 Feb 98 08:54:10 EST Received: from SUTHO.MIT.EDU by po7.MIT.EDU (5.61/4.7) id AA15203; Sat, 28 Feb 98 08:53:46 EST Message-Id: <34F816FF.7BF969A0@mit.edu> Date: Sat, 28 Feb 1998 08:54:07 -0500 From: Sean Sutherland X-Mailer: Mozilla 4.04 [en] (Win95; I) Mime-Version: 1.0 To: 6042-help@theory.lcs.mit.edu Subject: Problem 2 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit *** EOOH *** Date: Sat, 28 Feb 1998 08:54:07 -0500 From: Sean Sutherland X-Mailer: Mozilla 4.04 [en] (Win95; I) To: 6042-help@theory.lcs.mit.edu Subject: Problem 2 I have a question as regards to the receptacle. If in line 3 of the problem you state that "the receptacle can be used to store an unlimited amount of water" why is there a condition namely 2 which saids "pour from the receptacle to a bucket until the bucket is full or the receptacle is empty". That can't happen based on argument above. How do I deal with this? Sean seajaspe@mit.edu  1,, Summary-line: 28-Feb to: seajaspe@MIT.EDU [31] #Re: Problem 2 Mail-from: From meyer@theory.lcs.mit.edu Sat Feb 28 07:34:10 1998 Return-Path: Received: from stork.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA01587; Sat, 28 Feb 98 12:33:48 EST Received: by stork.lcs.mit.edu (5.65c/TOC-1.2C) id AA18717; Sat, 28 Feb 98 12:34:10 EST Date: Sat, 28 Feb 98 12:34:10 EST Message-Id: <199802281734.AA18717@stork.lcs.mit.edu> From: "Albert R. Meyer" To: seajaspe@MIT.EDU Cc: 6042-help@theory.lcs.mit.edu In-Reply-To: <34F816FF.7BF969A0@mit.edu> (message from Sean Sutherland on Sat, 28 Feb 1998 08:54:07 -0500) Subject: Re: Problem 2 Reply-To: 6042-meyer@theory.lcs.mit.edu *** EOOH *** Date: Sat, 28 Feb 98 12:34:10 EST From: "Albert R. Meyer" To: seajaspe@MIT.EDU Cc: 6042-help@theory.lcs.mit.edu In-Reply-To: <34F816FF.7BF969A0@mit.edu> (message from Sean Sutherland on Sat, 28 Feb 1998 08:54:07 -0500) Subject: Re: Problem 2 Reply-To: 6042-meyer@theory.lcs.mit.edu The receptable CAN hold a lot of water, but at any given moment between pourings, it might only be filled with a little bit -- or even be empty as it is at the start. Regards, A. Date: Sat, 28 Feb 1998 08:54:07 -0500 From: Sean Sutherland X-Mailer: Mozilla 4.04 [en] (Win95; I) I have a question as regards to the receptacle. If in line 3 of the problem you state that "the receptacle can be used to store an unlimited amount of water" why is there a condition namely 2 which saids "pour from the receptacle to a bucket until the bucket is full or the receptacle is empty". That can't happen based on argument above. How do I deal with this? Sean seajaspe@mit.edu  1,, Summary-line: 28-Feb to: flattop@MIT.EDU [74] #ps4 solns Mail-from: From meyer@theory.lcs.mit.edu Sat Feb 28 17:29:00 1998 Return-Path: Received: from stork.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA04418; Sat, 28 Feb 98 22:28:38 EST Received: by stork.lcs.mit.edu (5.65c/TOC-1.2C) id AA19246; Sat, 28 Feb 98 22:29:00 EST Date: Sat, 28 Feb 98 22:29:00 EST Message-Id: <199803010329.AA19246@stork.lcs.mit.edu> From: "Albert R. Meyer" To: flattop@MIT.EDU Cc: 6042-help In-Reply-To: <34F8C3F3.27E0@MIT.EDU> (flattop@MIT.EDU) Subject: ps4 solns Reply-To: 6042-meyer@theory.lcs.mit.edu *** EOOH *** Date: Sat, 28 Feb 98 22:29:00 EST From: "Albert R. Meyer" To: flattop@MIT.EDU Cc: 6042-help In-Reply-To: <34F8C3F3.27E0@MIT.EDU> (flattop@MIT.EDU) Subject: ps4 solns Reply-To: 6042-meyer@theory.lcs.mit.edu I looked at Stas' incomplete ps4 draft solution. Except for obvious minor typos, solns to 1--3(a) are fine. Soln to 3(b) doesn't yet have a proof that M(S) is decreasing, but that's pretty clear by cases: if the new move is bounded, then by def it does not change xmin or ymin, and it decreases the number of bounded pts -- since the move itself was bounded and can't be reused. If it's not bounded, then it decreases at least one of xmin and ymin. Of course xmin and ymin can never increase. Soln to 3(c): the first player starts with (1,1). Then the second player, whatever he picks, say (0,n) for some n, the first player will respond with (n,0). By symmetry, the first player will always have a move whenever the second player had a move, except when the second player picks (0,0) and loses. If the first player plays any other first move, the second player can win by choosing (1,1) -- except if the first player chooses (1,0) or (0,1), in which case (1,1) is disallowed, but the second wins by playing (0,1) or (1,0). soln 4(a): one soln is to arrange preferences so each woman is the first-choice of exactly one man, and she is his first choice. It's easy to see that when a man and a woman have each other as first choice, they will be a rogue couple unless they are married. another soln is to have all the men rank the women in the same order, and all the woman rank the men in the same order. Then first-choice man must marry first choice woman, after which 2nd choice man must marrry 2nd choice woman, etc. 4(bcd) follow by exactly the reasoning in the notes for the case of an equal number of men and women. 4(e) M1 accepts only W1, M2 accepts only W2, W1 accepts only M2, W2 accepts only M1. No mutually acceptable marriage is possible. 4(f) I'll leave this for Stas to explain. 4(g) We're looking for a brief statement, not a long proof. The brief statement is that, "Exactly the same reasoning which worked for the morning-afternoon-evening protocol applies to show that the one-at-a-time protocol yields a stable marriage set with bachelors of only of the excess sex. Moreover, exactly the reasoning in the notes which shows that the morning-afternoon-evening protocol yields the unique man-optimal matching, also applies to the one-at-a-time protocol, so it yields this same matching." BTW, there's another argument for uniqueness of the one-at-a-time matching which doesn't appeal to man-optimality, but is based on the claim that the order in which simultaneously possible crossings-out are performed doesn't matter. The argument uses the Lemma: If at some point, woman W1 can tell man M1 to cross her off his list, and at the same time woman W2 can tell man M2 to cross her off, then if either of these is the crossout which occurs, it will still be possible to do the other one next. I doubt that anyone will come up with this argument, so I won't finish spelling it out, but if you see anyone with reasoning along the line of this lemma, don't assume they're off the track. Regards, A.  1,, Summary-line: 1-Mar cstan@MIT.EDU [15] #Problem Set 4 Mail-from: From cstan@MIT.EDU Sun Mar 1 11:42:11 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA08298; Sun, 01 Mar 98 16:48:00 EST Received: from PO7.MIT.EDU by MIT.EDU with SMTP id AA21143; Sun, 1 Mar 98 16:47:26 EST Received: from ANG-MO-KIO.MIT.EDU by po7.MIT.EDU (5.61/4.7) id AA27730; Sun, 1 Mar 98 16:47:03 EST Message-Id: <34F9D633.76C5@mit.edu> Date: Sun, 01 Mar 1998 16:42:11 -0500 From: ChoonsiangTan Reply-To: cstan@MIT.EDU Organization: MIT X-Mailer: Mozilla 3.01 (Win95; I) Mime-Version: 1.0 To: 6042-help@theory.lcs.mit.edu Subject: Problem Set 4 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit *** EOOH *** Date: Sun, 01 Mar 1998 16:42:11 -0500 From: ChoonsiangTan Reply-To: cstan@MIT.EDU Organization: MIT X-Mailer: Mozilla 3.01 (Win95; I) To: 6042-help@theory.lcs.mit.edu Subject: Problem Set 4 Hi, What is question 3 (a) asking when it asks us to prove that the subset has a least element? Choonsiang  1,, Summary-line: 1-Mar stasio@MIT.EDU [12] #Re: Problem Set 4 Mail-from: From stasio@mit.edu Sun Mar 1 11:49:01 1998 Return-Path: Received: from enigma.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA08331; Sun, 01 Mar 98 16:49:59 EST Received: (from stasio@localhost) by enigma.LCS.MIT.EDU (8.7.5/8.6.12) id QAA12353; Sun, 1 Mar 1998 16:49:01 -0500 (EST) Date: Sun, 1 Mar 1998 16:49:01 -0500 (EST) Message-Id: <199803012149.QAA12353@enigma.LCS.MIT.EDU> From: Stanislaw Jarecki To: cstan@MIT.EDU Cc: 6042-help@theory.lcs.mit.edu In-Reply-To: <34F9D633.76C5@mit.edu> (message from ChoonsiangTan on Sun, 01 Mar 1998 16:42:11 -0500) Subject: Re: Problem Set 4 *** EOOH *** Date: Sun, 1 Mar 1998 16:49:01 -0500 (EST) From: Stanislaw Jarecki To: cstan@MIT.EDU Cc: 6042-help@theory.lcs.mit.edu In-Reply-To: <34F9D633.76C5@mit.edu> (message from ChoonsiangTan on Sun, 01 Mar 1998 16:42:11 -0500) Subject: Re: Problem Set 4 the question asks you if a subset has a least element *in this ordering*. Not every ordering of a set has this property.  1,, Summary-line: 1-Mar asomani@MIT.EDU [17] # Mail-from: From asomani@MIT.EDU Sun Mar 1 18:45:59 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA10707; Sun, 01 Mar 98 23:46:58 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA02507; Sun, 1 Mar 98 23:46:00 EST Received: from THE-KID.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA23195; Sun, 1 Mar 98 23:45:59 EST Date: Sun, 1 Mar 98 23:45:59 EST Message-Id: <9803020445.AA23195@MIT.MIT.EDU> X-Sender: asomani@po8.mit.edu X-Mailer: Windows Eudora Pro Version 2.1.2 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" To: 6042-help@theory.lcs.mit.edu From: Ashutosh Somani Subject: *** EOOH *** Date: Sun, 1 Mar 98 23:45:59 EST X-Sender: asomani@po8.mit.edu X-Mailer: Windows Eudora Pro Version 2.1.2 To: 6042-help@theory.lcs.mit.edu From: Ashutosh Somani Subject: I had a question regarding problem 4 parts e and f. What does it mean by "suppose that no person is unacceptable to more than one person of the opposite sex." How could a person be unacceptable anyone...in the protocol you ONLY rank people who are acceptable right? Thanks. Ashutosh Somani asomani@mit.edu  0, unseen,, Summary-line: 1-Mar flattop@MIT.EDU [38] #Re: *** EOOH *** Mail-from: From flattop@MIT.EDU Sun Mar 1 18:53:50 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA10793; Sun, 01 Mar 98 23:54:50 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA03527; Sun, 1 Mar 98 23:53:52 EST Received: from W20-575-90.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA23677; Sun, 1 Mar 98 23:53:51 EST Sender: flattop@MIT.EDU Message-Id: <34FA3B5E.7E2A@MIT.EDU> Date: Sun, 01 Mar 1998 23:53:50 -0500 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Mime-Version: 1.0 To: Ashutosh Somani Cc: 6042-help@theory.lcs.mit.edu Subject: Re: References: <9803020445.AA23195@MIT.MIT.EDU> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit I had a question regarding problem 4 parts e and f. What does it mean by "suppose that no person is unacceptable to more than one person of the opposite sex." How could a person be unacceptable anyone...in the protocol you ONLY rank people who are acceptable right? Thanks. Ashutosh Somani asomani@mit.edu --------------------------------------------- That's what it means, To be unacceptable is not to be ranked. So in other words, let say there are n people in the opposite sex, at least n-1 of them must rank you. jack  0, unseen,, Summary-line: 2-Mar mli@MIT.EDU [29] #6.042 PS4, #2 *** EOOH *** Mail-from: From mli@MIT.EDU Mon Mar 2 08:20:51 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA17576; Mon, 02 Mar 98 13:21:52 EST Received: from MASS-TOOLPIKE.MIT.EDU by MIT.EDU with SMTP id AA03638; Mon, 2 Mar 98 13:21:18 EST Received: by mass-toolpike.MIT.EDU (8.8.7/4.7) id NAA14627; Mon, 2 Mar 1998 13:20:52 -0500 (EST) Message-Id: <199803021820.NAA14627@mass-toolpike.MIT.EDU> To: 6042-help@theory.lcs.mit.edu Subject: 6.042 PS4, #2 Date: Mon, 02 Mar 1998 13:20:51 EST From: Michael W Li Hi, for problem 2, what is the purpose of the drain? in something like move #5 where it says: pour from A to B until either A is empty of B is full, whichever happens first, is this to say that if B becomes full, the excess water in A is thrown down the drain? or does it stay in A? so if A is filled with water capacity a, and B is empty, and A is poured into B, and we assume that a > b, when B becomes full, is there a-b left over in bucket A? or does that go down the drain? mike  0, unseen,, Summary-line: 2-Mar stasio@mit.edu [23] #ps4 solutions *** EOOH *** Mail-from: From stasio@mit.edu Mon Mar 2 08:22:40 1998 Return-Path: Received: from enigma.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA17717; Mon, 02 Mar 98 13:23:38 EST Received: (from stasio@localhost) by enigma.LCS.MIT.EDU (8.7.5/8.6.12) id NAA14369; Mon, 2 Mar 1998 13:22:40 -0500 (EST) Date: Mon, 2 Mar 1998 13:22:40 -0500 (EST) Message-Id: <199803021822.NAA14369@enigma.LCS.MIT.EDU> From: Stanislaw Jarecki To: 6042-help@theory.lcs.mit.edu Subject: ps4 solutions Hey helpers, i put the new ps4 solutions on our staffonly: 1. They dont have 4g 2. The 4f is done for the problem as I revised it (it is clear that the old statement was not true, but it is not clear whether we will cancel the problem or brodcast the fix. but just in case: it's there) stas  0, unseen,, Summary-line: 2-Mar flints@MIT.EDU [39] #PS#4 Q 4.e *** EOOH *** Mail-from: From flints@MIT.EDU Mon Mar 2 10:42:24 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA19911; Mon, 02 Mar 98 15:43:25 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA22135; Mon, 2 Mar 98 15:42:50 EST Received: from M2-032-5.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA09430; Mon, 2 Mar 98 15:42:24 EST Sender: flints@MIT.EDU Message-Id: <34FB19B0.571F@MIT.EDU> Date: Mon, 02 Mar 1998 15:42:24 -0500 From: Petra S Chong Organization: Massachusetts Institute of Technology X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Mime-Version: 1.0 To: 6042-help@theory.lcs.mit.edu Cc: flints@MIT.EDU Subject: PS#4 Q 4.e Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit I do not understand this part of the question; I would like to clarify what the exact situation described is. 1. Are we to show that every stable marriage set leaves two bachelors of each sex, if there are arbitrary (non-equal) numbers of men and women? 2. If we are, I don't know how to start; I've been looking at this all weekend. The hint given says to find a situation involving exactly two men and women; I took this to mean the situation where there were ONLY two men and two women. In this case, I can find an arrangement where there is NO marriage set; but I don't see how I can extend this to arbitrary numbers of men and women. I can't find an invariant, and I can't find a derived variable that seems to lead anywhere. Thanks petra  0, unseen,, Summary-line: 2-Mar to: flints@MIT.EDU [54] #Re: PS#4 Q 4.e *** EOOH *** Mail-from: From meyer@theory.lcs.mit.edu Mon Mar 2 11:09:39 1998 Return-Path: Received: from stork.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA20343; Mon, 02 Mar 98 16:09:16 EST Received: by stork.lcs.mit.edu (5.65c/TOC-1.2C) id AA20899; Mon, 02 Mar 98 16:09:39 EST Date: Mon, 02 Mar 98 16:09:39 EST Message-Id: <199803022109.AA20899@stork.lcs.mit.edu> From: "Albert R. Meyer" To: flints@MIT.EDU Cc: 6042-help@theory.lcs.mit.edu In-Reply-To: <34FB19B0.571F@MIT.EDU> (message from Petra S Chong on Mon, 02 Mar 1998 15:42:24 -0500) Subject: Re: PS#4 Q 4.e Reply-To: 6042-meyer@theory.lcs.mit.edu It's OK to pick a "situation," that is, set of men and women and their preferences, in which there are equal numbers of men and women. You could also pick a situation with unequal numbers. You only have to pick one situation. If you do pick a situation w/2 men and 2 women as the hint suggests, the stable marriage set will necessarily be empty, but that's allowed. Regards, A. Sender: flints@MIT.EDU Date: Mon, 02 Mar 1998 15:42:24 -0500 From: Petra S Chong Organization: Massachusetts Institute of Technology X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Cc: flints@MIT.EDU I do not understand this part of the question; I would like to clarify what the exact situation described is. 1. Are we to show that every stable marriage set leaves two bachelors of each sex, if there are arbitrary (non-equal) numbers of men and women? 2. If we are, I don't know how to start; I've been looking at this all weekend. The hint given says to find a situation involving exactly two men and women; I took this to mean the situation where there were ONLY two men and two women. In this case, I can find an arrangement where there is NO marriage set; but I don't see how I can extend this to arbitrary numbers of men and women. I can't find an invariant, and I can't find a derived variable that seems to lead anywhere. Thanks petra  0, unseen,, Summary-line: 2-Mar flattop@MIT.EDU [58] #Re: 6.042 PS4, #2 *** EOOH *** Mail-from: From flattop@MIT.EDU Mon Mar 2 11:17:59 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA20534; Mon, 02 Mar 98 16:19:05 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA14295; Mon, 2 Mar 98 16:18:07 EST Received: from W20-575-12.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA16476; Mon, 2 Mar 98 16:18:04 EST Sender: flattop@MIT.EDU Message-Id: <34FB2207.146F@MIT.EDU> Date: Mon, 02 Mar 1998 16:17:59 -0500 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Mime-Version: 1.0 To: Michael W Li Cc: 6042-help@theory.lcs.mit.edu Subject: Re: 6.042 PS4, #2 References: <199803021820.NAA14627@mass-toolpike.MIT.EDU> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit I'm not sure if anyone answered your question: Purpose of the drain is to empty either Bucket A or B. In move 5: you have the option of keeping the excess water in A or pour it in the drain. you cannot assume a>b. If A is filled with capacity a, and B is empty. If you pour A into B: if a>b --> A will have excess water, B will be full if a A will be empty, B will be partially full if a=b, then A is empty, B is full You can do whatever you want with the excess water: keep it or pour in drain. Hope this helps jack Michael W Li wrote: > > Hi, > > for problem 2, what is the purpose of the drain? > in something like move #5 where it says: pour from A to B until either > A is empty of B is full, whichever happens first, > is this to say that if B becomes full, the excess water in > A is thrown down the drain? or does it stay in A? > > so if A is filled with water capacity a, and B is empty, > and A is poured into B, and we assume that a > b, when > B becomes full, is there a-b left over in bucket A? > or does that go down the drain? > > mike  0, unseen,, Summary-line: 2-Mar to: 6042-help [52] #[meyer@theory.lcs.mit.edu: Re: 6.042 pset4, prob3b: correction to example] *** EOOH *** Mail-from: From meyer@theory.lcs.mit.edu Mon Mar 2 11:28:17 1998 Return-Path: Received: from stork.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA20704; Mon, 02 Mar 98 16:27:54 EST Received: by stork.lcs.mit.edu (5.65c/TOC-1.2C) id AA20964; Mon, 02 Mar 98 16:28:17 EST Date: Mon, 02 Mar 98 16:28:17 EST Message-Id: <199803022128.AA20964@stork.lcs.mit.edu> From: "Albert R. Meyer" To: 6042-help Subject: [meyer@theory.lcs.mit.edu: Re: 6.042 pset4, prob3b: correction to example] FYI: ------- Start of forwarded message ------- Date: Mon, 2 Mar 1998 16:20:34 -0500 From: "Albert R. Meyer" To: low@MIT.EDU In-reply-to: <2.2.32.19980302192938.006e183c@po7.mit.edu> (message from Low Tzer Hung on Mon, 02 Mar 1998 14:29:38 -0500) Subject: Re: 6.042 pset4, prob3b: correction to example reply-to: 6042-meyer In addition to 5. & 6., prob 2(c) won't let you use 2. or 3. either. Regards, A. X-Sender: low@po7.mit.edu (Unverified) X-Mailer: Windows Eudora Pro Version 2.2 (32) Date: Mon, 02 Mar 1998 14:29:38 -0500 From: Low Tzer Hung Is there a mistake in question 2, since I can do 2b) without using 5 and 6. This makes 2c) trivial. thanks Low Tzer Hung At 05:44 PM 3/1/98 EST, you wrote: >In the example given in PSet4, Prob 3b: the set of bounded moves >should be > {(1,1),(1,2),(2,1), (0,3), (0,2),(0,1),(0,0),(1,0),(2,0),(3,0)}. >(The last 7 points above, with a 0 coordinate, were omitted in the >original handout.) And the unbounded moves in the example are the points >with at least one zero-coordinate, except the 7 above. > >Regards, A. > ------- End of forwarded message -------  0, unseen,, Summary-line: 2-Mar to: flints@MIT.EDU [41] #Re: PS#4 Q 4.e *** EOOH *** Mail-from: From meyer@theory.lcs.mit.edu Mon Mar 2 14:31:38 1998 Return-Path: Received: from stork.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA23268; Mon, 02 Mar 98 19:31:15 EST Received: by stork.lcs.mit.edu (5.65c/TOC-1.2C) id AA21108; Mon, 02 Mar 98 19:31:38 EST Date: Mon, 02 Mar 98 19:31:38 EST Message-Id: <199803030031.AA21108@stork.lcs.mit.edu> From: "Albert R. Meyer" To: flints@MIT.EDU In-Reply-To: <199803022156.QAA27999@quickstation-50-1.MIT.EDU> (message from Petra Chong on Mon, 02 Mar 1998 16:56:46 EST) Subject: Re: PS#4 Q 4.e Cc: 6042-help Reply-To: 6042-meyer@theory.lcs.mit.edu It could be that one woman finds NO man acceptable, but all the other woman accepted all the other men. This still satisfies the condition that each man is unacceptable to at most one woman. Regards, A. Date: Mon, 02 Mar 1998 16:56:46 EST From: Petra Chong I have another question; this time about question 4 part f. I have taken note of the correction in the question. I would like to clarify one specification: If N is the number of men and women: Is the situation such that each man likes ONLY N-1 women, and every women likes ONLY N - 1 men? thanks petra  1,, Summary-line: 2-Mar mphil14@MIT.EDU [31] #PS #4 Mail-from: From mphil14@MIT.EDU Mon Mar 2 16:11:06 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA24444; Mon, 02 Mar 98 21:12:07 EST Received: from NO-KNIFE.MIT.EDU by MIT.EDU with SMTP id AA18582; Mon, 2 Mar 98 21:11:33 EST Received: by no-knife.MIT.EDU (8.8.7/4.7) id VAA19228; Mon, 2 Mar 1998 21:11:07 -0500 (EST) Message-Id: <199803030211.VAA19228@no-knife.MIT.EDU> To: 6042-help@theory.lcs.mit.edu Subject: PS #4 Date: Mon, 02 Mar 1998 21:11:06 EST From: Mark Phillip *** EOOH *** To: 6042-help@theory.lcs.mit.edu Subject: PS #4 Date: Mon, 02 Mar 1998 21:11:06 EST From: Mark Phillip Hi, I'm having problems with 2c and 4b. For 4b, I totally understand the protocol and the rest of question 4, but I don't exactly see how I can model the states and the transitions. For 2c I honestly don't even understand the question. Any help you could give me would be great. THanks...-mark Mark Phillip Phi Sigma Kappa Boston MA, 02215 REEFPRODUCTIONS.mit.edu web.mit.edu/mphil14/www "near...far.....NEAR....FAR!!!"  0, unseen,, Summary-line: 2-Mar to: mphil14@MIT.EDU [50] #Re: PS #4 *** EOOH *** Mail-from: From meyer@theory.lcs.mit.edu Mon Mar 2 16:29:51 1998 Return-Path: Received: from stork.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA24600; Mon, 02 Mar 98 21:29:28 EST Received: by stork.lcs.mit.edu (5.65c/TOC-1.2C) id AA21206; Mon, 02 Mar 98 21:29:51 EST Date: Mon, 02 Mar 98 21:29:51 EST Message-Id: <199803030229.AA21206@stork.lcs.mit.edu> From: "Albert R. Meyer" To: mphil14@MIT.EDU Cc: 6042-help@theory.lcs.mit.edu In-Reply-To: <199803030211.VAA19228@no-knife.MIT.EDU> (message from Mark Phillip on Mon, 02 Mar 1998 21:11:06 EST) Subject: Re: PS #4 Reply-To: 6042-meyer@theory.lcs.mit.edu You should be able to answer 4b, if you understand how to model the protocol from lecture as a state machine. This was described in lecture and in the Handout 17 notes. If you are still stuck after that, ask for more 6042-help. For 2c, remember the 3cent 5cent postage problem? You couldn't make up ALL amounts of postage, only all amounts >= 8. With stamps (or buckets) 9, 12 you can make up all amounts divisible by gcd(9,12)=3, provided the amount is >= 18, but you can't make 3, 6, or 15. The problem asks you to show that this kind of thing is what always happens. Regards, A. Date: Mon, 02 Mar 1998 21:11:06 EST From: Mark Phillip Hi, I'm having problems with 2c and 4b. For 4b, I totally understand the protocol and the rest of question 4, but I don't exactly see how I can model the states and the transitions. For 2c I honestly don't even understand the question. Any help you could give me would be great. THanks...-mark Mark Phillip Phi Sigma Kappa Boston MA, 02215 REEFPRODUCTIONS.mit.edu web.mit.edu/mphil14/www "near...far.....NEAR....FAR!!!"  0, unseen,, Summary-line: 2-Mar aileen@MIT.EDU [38] #question 4 *** EOOH *** Mail-from: From aileen@MIT.EDU Mon Mar 2 16:39:47 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA24778; Mon, 02 Mar 98 21:40:48 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA01969; Mon, 2 Mar 98 21:39:50 EST Received: from KWAIBAO.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA26462; Mon, 2 Mar 98 21:39:49 EST Message-Id: <3.0.1.32.19980302213947.0069a4a0@po7.mit.edu> X-Sender: aileen@po7.mit.edu X-Mailer: Windows Eudora Pro Version 3.0.1 (32) Date: Mon, 02 Mar 1998 21:39:47 -0500 To: 6042-help@theory.lcs.mit.edu From: Aileen Tang Subject: question 4 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Hi, Question 4 defines the terminating condition as "the first afternoon when every man who proposed to a woman that morning ends up engaged to her in teh afternoon." Is this any different from the terminating condition specified in lecture when "no changes occur"? Thanks, Aileen @=) _________________________________________________________________________ Aileen Tang '99 MM MM IIIIIIII TTTTTTTT Massachusetts Institute of Technology MM MM ~~ II TT 320 Memorial Drive Rm 704 M M M M @@ II TT Cambridge, MA 02139 M MM M C II TT http://kwaibao.mit.edu/ MM MM MM V IIIII TT _________________________________________________________________________  0, unseen,, Summary-line: 2-Mar mli@MIT.EDU [22] ##2b *** EOOH *** Mail-from: From mli@MIT.EDU Mon Mar 2 16:59:40 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA24895; Mon, 02 Mar 98 22:00:40 EST Received: from MASS-TOOLPIKE.MIT.EDU by MIT.EDU with SMTP id AA26296; Mon, 2 Mar 98 22:00:05 EST Received: by mass-toolpike.MIT.EDU (8.8.7/4.7) id VAA02454; Mon, 2 Mar 1998 21:59:40 -0500 (EST) Message-Id: <199803030259.VAA02454@mass-toolpike.MIT.EDU> To: 6.042-help@theory.lcs.mit.edu Subject: #2b Date: Mon, 02 Mar 1998 21:59:40 EST From: Michael W Li can you explain Lemma 0.2 in Problem Set 4 solutions 97 problem #5? I been staring for a while at it to get insight into problem #2 on the set but I don't understand where they get m and n. thanks, Mike Li  0, unseen,, Summary-line: 2-Mar to: aileen@MIT.EDU [48] #Re: question 4 *** EOOH *** Mail-from: From meyer@theory.lcs.mit.edu Mon Mar 2 18:09:05 1998 Return-Path: Received: from stork.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA25823; Mon, 02 Mar 98 23:08:42 EST Received: by stork.lcs.mit.edu (5.65c/TOC-1.2C) id AA21250; Mon, 02 Mar 98 23:09:05 EST Date: Mon, 02 Mar 98 23:09:05 EST Message-Id: <199803030409.AA21250@stork.lcs.mit.edu> From: "Albert R. Meyer" To: aileen@MIT.EDU Cc: 6042-help@theory.lcs.mit.edu In-Reply-To: <3.0.1.32.19980302213947.0069a4a0@po7.mit.edu> (message from Aileen Tang on Mon, 02 Mar 1998 21:39:47 -0500) Subject: Re: question 4 Reply-To: 6042-meyer@theory.lcs.mit.edu They are indeed equivalent, but if you intend to use this fact, you should prove it. Regards, A. X-Sender: aileen@po7.mit.edu X-Mailer: Windows Eudora Pro Version 3.0.1 (32) Date: Mon, 02 Mar 1998 21:39:47 -0500 From: Aileen Tang Hi, Question 4 defines the terminating condition as "the first afternoon when every man who proposed to a woman that morning ends up engaged to her in teh afternoon." Is this any different from the terminating condition specified in lecture when "no changes occur"? Thanks, Aileen @=) _________________________________________________________________________ Aileen Tang '99 MM MM IIIIIIII TTTTTTTT Massachusetts Institute of Technology MM MM ~~ II TT 320 Memorial Drive Rm 704 M M M M @@ II TT Cambridge, MA 02139 M MM M C II TT http://kwaibao.mit.edu/ MM MM MM V IIIII TT _________________________________________________________________________  0, unseen,, Summary-line: 2-Mar to: mli@MIT.EDU [36] #Re: #2b *** EOOH *** Mail-from: From meyer@theory.lcs.mit.edu Mon Mar 2 18:27:09 1998 Return-Path: Received: from stork.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA25970; Mon, 02 Mar 98 23:26:46 EST Received: by stork.lcs.mit.edu (5.65c/TOC-1.2C) id AA21285; Mon, 02 Mar 98 23:27:09 EST Date: Mon, 02 Mar 98 23:27:09 EST Message-Id: <199803030427.AA21285@stork.lcs.mit.edu> From: "Albert R. Meyer" To: mli@MIT.EDU In-Reply-To: <199803030259.VAA02454@mass-toolpike.MIT.EDU> (message from Michael W Li on Mon, 02 Mar 1998 21:59:40 EST) Subject: Re: #2b Cc: 6042-help Reply-To: 6042-meyer@theory.lcs.mit.edu Oh, you mean SPRING 97! Yes, m and n are cleverly chosen, but there isn't any need for you to know how someone figured them out. Our pset 4, prob 2 can be solved directly from the fact that gcd(a,b) = xa+yb for some integers x,y. Regards, A. Date: Mon, 02 Mar 1998 21:59:40 EST From: Michael W Li can you explain Lemma 0.2 in Problem Set 4 solutions 97 problem #5? I been staring for a while at it to get insight into problem #2 on the set but I don't understand where they get m and n. thanks, Mike Li  0, unseen,, Summary-line: 2-Mar ahuang@MIT.EDU [23] #Problem Set 4 *** EOOH *** Mail-from: From ahuang@MIT.EDU Mon Mar 2 18:30:53 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA26022; Mon, 02 Mar 98 23:31:52 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA12564; Mon, 2 Mar 98 23:31:18 EST Received: from THAILAND.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA05671; Mon, 2 Mar 98 23:30:53 EST Date: Mon, 2 Mar 98 23:30:53 EST Message-Id: <9803030430.AA05671@MIT.MIT.EDU> X-Sender: ahuang@po8.mit.edu X-Mailer: Windows Eudora Pro Version 2.1.2 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" To: 6042-help@theory.lcs.mit.edu From: Angus Huang Subject: Problem Set 4 I was just wondering how we should go about proving Problem 2c (what method sould we use). Thanks for your help. Angus Huang  0, unseen,, Summary-line: 2-Mar to: ahuang@MIT.EDU [31] #Re: Problem Set 4 *** EOOH *** Mail-from: From meyer@theory.lcs.mit.edu Mon Mar 2 18:50:44 1998 Return-Path: Received: from stork.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA26187; Mon, 02 Mar 98 23:50:21 EST Received: by stork.lcs.mit.edu (5.65c/TOC-1.2C) id AA21322; Mon, 02 Mar 98 23:50:44 EST Date: Mon, 02 Mar 98 23:50:44 EST Message-Id: <199803030450.AA21322@stork.lcs.mit.edu> From: "Albert R. Meyer" To: ahuang@MIT.EDU In-Reply-To: <9803030430.AA05671@MIT.MIT.EDU> (message from Angus Huang on Mon, 2 Mar 98 23:30:53 EST) Subject: Re: Problem Set 4 Reply-To: 6042-meyer@theory.lcs.mit.edu Cc: 6042-help describe a procedure for increasing the amount of water in the receptacle by gcd(a,b), providing there is enough water in the receptacle. Date: Mon, 2 Mar 98 23:30:53 EST X-Sender: ahuang@po8.mit.edu X-Mailer: Windows Eudora Pro Version 2.1.2 From: Angus Huang I was just wondering how we should go about proving Problem 2c (what method sould we use). Thanks for your help. Angus Huang  0, unseen,, Summary-line: 3-Mar ez=40mit.edu=3E?=@MIT.EDU [20] # *** EOOH *** Mail-from: From jslopez@MIT.EDU Mon Mar 2 19:04:23 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA26325; Tue, 03 Mar 98 00:05:21 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA17895; Tue, 3 Mar 98 00:04:48 EST Received: from JSLOPEZ.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA08097; Tue, 3 Mar 98 00:04:23 EST Message-Id: <2.2.32.19980303050423.006ba99c@po10.mit.edu> X-Sender: jslopez@po10.mit.edu X-Mailer: Windows Eudora Pro Version 2.2 (32) Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Tue, 03 Mar 1998 00:04:23 -0500 To: 6042-help@theory.lcs.mit.edu From: =?iso-8859-1?Q?=22Javier_S._L=F3pez=22_=3Cjslopez=40mit.edu=3E?=@MIT.EDU Subject: What the N^3 means?  0, unseen,, Summary-line: 3-Mar flattop@MIT.EDU [84] #Re: *** EOOH *** Mail-from: From flattop@MIT.EDU Mon Mar 2 19:40:50 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA26507; Tue, 03 Mar 98 00:41:51 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA01990; Tue, 3 Mar 98 00:40:53 EST Received: from W20-575-22.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA11794; Tue, 3 Mar 98 00:40:52 EST Sender: flattop@MIT.EDU Message-Id: <34FB97E2.6EE3@MIT.EDU> Date: Tue, 03 Mar 1998 00:40:50 -0500 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Mime-Version: 1.0 To: "Javier S. Lspez @MIT.EDU" Cc: 6042-help@theory.lcs.mit.edu Subject: Re: References: <2.2.32.19980303050423.006ba99c@po10.mit.edu> Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit It means a triple (a, b, c) N^2 is (a, b) N is just a "Javier S. Lspez" @MIT.EDU wrote: > > What the N^3 means? -- MIT Class of 2000 http://web.mit.edu/flattop/www/From meyer@theory.lcs.mit.edu Fri Mar 6 01:11:14 1998 Return-Path: Received: from stork.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA07147; Fri, 06 Mar 98 06:10:49 EST Received: by stork.lcs.mit.edu (5.65c/TOC-1.2C) id AA04717; Fri, 06 Mar 98 06:11:14 EST Date: Fri, 06 Mar 98 06:11:14 EST Message-Id: <199803061111.AA04717@stork.lcs.mit.edu> From: "Albert R. Meyer" To: gtewari@MIT.EDU In-Reply-To: <199803060434.XAA09766@M66-080-3.MIT.EDU> (message from Gaurav Tewari on Thu, 05 Mar 1998 23:34:18 EST) Subject: Re: Prob. set 5 Cc: 6042-help Reply-To: 6042-meyer@theory.lcs.mit.edu Date: Thu, 05 Mar 1998 23:34:18 EST From: Gaurav Tewari Hello Prof. Meyer, Couple of quick clarifications about PS5: 1). In Prob. 1 do the Meng students start paying back 5 years after starting Meng or 5 years after finishing it (ie, 10 years after starting)? Its not clear what "Wait five years" means. EITHER INTERPRETATION IS FINE, although it seems preety clear to me (I didn't write this problem) that the intended interpretation is that the loan should be paid back 5 years after starting, viz., immediately after finishing the program. 2). Prob. 8: Did you mean for the lower limit of the summation to be i = 0 rather than 1?....It would make the differentiation a lot easier because : (a) there would be 'n' rather than (n-1) terms in the sum, and (b) would make the first term 1 rather than 'x'--with 'x' the differetiation is very hairy LOOK AGAIN and you'll see it obviously makes no difference if the sum starts at i= 0 or i = 1. Also are we to assume that Abs(x) < 1 ? (Condition for convergence) NO. It's a finite sum, so convergence is not an issue. Thanks very much, Gaurav P.S. A better address for email about psets is 6042-help@theory.lcs.mit.edu. You're welcome to use 6042-meyer@theory.lcs.mit.edu when you really want my personal attention.  0, unseen,, Summary-line: 6-Mar mroh@MIT.EDU [35] #team problem 2a *** EOOH *** Mail-from: From mroh@MIT.EDU Fri Mar 6 04:29:08 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA08465; Fri, 06 Mar 98 09:30:11 EST Received: from EXODUS.MIT.EDU by MIT.EDU with SMTP id AA18414; Fri, 6 Mar 98 09:29:11 EST From: mroh@MIT.EDU Received: by exodus.MIT.EDU (8.6.10/4.7) id JAA10828; Fri, 6 Mar 1998 09:29:10 -0500 Message-Id: <199803061429.JAA10828@exodus.MIT.EDU> To: 6042-meyer@theory.lcs Cc: 6042-help@theory.lcs Subject: team problem 2a Date: Fri, 06 Mar 1998 09:29:08 EST Albert, I'm curious about 2a. If I read the question right, then f(n)=0 for even n, and g(n)=0 for odd n. Therefore we could even have f(n) = (n mod 2), g(n) = (n+1 mod 2), and we'd satisfy the problem, right? Just wanted to run this by you before I present it in class. I'm confused because of the reference to f(n) being n times the size of g(n) for odd n, even though g(n) is 0, not 1. (I suppose we could add 1 to both f(n) and g(n) for clarity, though.) Mark ----------- Mark Roh, mroh@mit.edu (617) 497-4876  0, unseen,, Summary-line: 6-Mar mroh@MIT.EDU [32] #Re: team problem 2a *** EOOH *** Mail-from: From mroh@MIT.EDU Fri Mar 6 04:56:50 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA08722; Fri, 06 Mar 98 09:57:54 EST Received: from EXODUS.MIT.EDU by MIT.EDU with SMTP id AA26644; Fri, 6 Mar 98 09:56:54 EST From: mroh@MIT.EDU Received: by exodus.MIT.EDU (8.6.10/4.7) id JAA10903; Fri, 6 Mar 1998 09:56:52 -0500 Message-Id: <199803061456.JAA10903@exodus.MIT.EDU> To: 6042-help@theory.lcs Subject: Re: team problem 2a In-Reply-To: Your message of "Fri, 06 Mar 1998 09:38:15 EST." <199803061438.JAA14275@Kings-College.MIT.edu> Date: Fri, 06 Mar 1998 09:56:50 EST Clarification: When I suggested added 1 to both f and g, I meant f and g as stated in the sol'n, not my 0/1 f and g. Adding 1 to the printed sol'n would allow us to say that f and g are n (technically n+1) times each other for appropriately chosen n, so that we're not multiplying n and 0 to get 0. Sorry about all the email. Mark ----------- Mark Roh, mroh@mit.edu (617) 497-4876  0, unseen,, Summary-line: 6-Mar flattop@MIT.EDU [29] #hours *** EOOH *** Mail-from: From flattop@MIT.EDU Fri Mar 6 09:21:53 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA12102; Fri, 06 Mar 98 14:22:57 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA15739; Fri, 6 Mar 98 14:21:55 EST Received: from M38-370-11.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA09843; Fri, 6 Mar 98 14:21:54 EST Sender: flattop@MIT.EDU Message-Id: <35004CD1.7CE5@MIT.EDU> Date: Fri, 06 Mar 1998 14:21:53 -0500 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Mime-Version: 1.0 To: 6.042-help@theory.lcs.mit.edu Subject: hours Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit I'll be logged on Sunday from 9:00 to 12 midnight Sunday Monday 9-11 Wes Chao will be logged on from 11-2a.m. jack p.s. Wes, tell me if that's the correct time that you want to work. I'll probably be logged on from 11-2 also  0, unseen,, Summary-line: 6-Mar to: flattop@MIT.EDU [20] #Re: hours *** EOOH *** Mail-from: From meyer@theory.lcs.mit.edu Fri Mar 6 11:03:01 1998 Return-Path: Received: from stork.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA13400; Fri, 06 Mar 98 16:02:36 EST Received: by stork.lcs.mit.edu (5.65c/TOC-1.2C) id AA05253; Fri, 06 Mar 98 16:03:01 EST Date: Fri, 06 Mar 98 16:03:01 EST Message-Id: <199803062103.AA05253@stork.lcs.mit.edu> From: "Albert R. Meyer" To: flattop@MIT.EDU Cc: 6.042-help@theory.lcs.mit.edu In-Reply-To: <35004CD1.7CE5@MIT.EDU> (flattop@MIT.EDU) Subject: Re: hours Reply-To: 6042-meyer@theory.lcs.mit.edu FYI: 6042-staff also receives all email to 6042-students, so no need to send a separate message to staff. Regards, A.  0, unseen,, Summary-line: 7-Mar ssadoway@MIT.EDU [36] #Problem Set 5 Question 1 *** EOOH *** Mail-from: From ssadoway@MIT.EDU Sat Mar 7 17:21:40 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA07748; Sat, 07 Mar 98 22:22:52 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA27168; Sat, 7 Mar 98 22:21:51 EST Received: from SILENT-BOB.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA24771; Sat, 7 Mar 98 22:21:49 EST Message-Id: <3.0.2.32.19980307222140.007d9c60@hesiod> X-Sender: ssadoway@hesiod X-Mailer: QUALCOMM Windows Eudora Pro Version 3.0.2 (32) Date: Sat, 07 Mar 1998 22:21:40 -0500 To: 6042-help@theory.lcs.mit.edu From: Steve *Silent Bob* Sadoway Subject: Problem Set 5 Question 1 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" This is kind of a dumb question, but I just want to make sure. In problem #1, it says that he'll pay you 23100 for 5 years... Then to pay him back, one waits 5 years and then pays x for 10 years. Does this mean that one waits for 5 years after he's finished paying, or wait until 5 years from now? I say the latter here, but I'm not 100% sure... Just trying to clarify this. Thanks in advance... -->Steve ~~~~~~~~~~~~~~~~~~~~~~~~~Steven Sadoway~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ E-mail: ssadoway@mit.edu | Homepage: http://web.mit.edu/ssadoway/www/ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ "We were talking 'bout something, seems like was funny, then Steven got quiet - I think Steven was mad. Maybe he wasn't mad, but we felt very strange, in the moment, but the moment was passed and forgotten about." --Ben Folds Five, "Steven's Last Night In Town" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  0, unseen,, Summary-line: 7-Mar mroh@MIT.EDU [28] #Re: Problem Set 5 Question 1 *** EOOH *** Mail-from: From mroh@MIT.EDU Sat Mar 7 17:41:45 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA07796; Sat, 07 Mar 98 22:42:36 EST Received: from EXODUS.MIT.EDU by MIT.EDU with SMTP id AA28896; Sat, 7 Mar 98 22:41:36 EST From: mroh@MIT.EDU Received: by exodus.MIT.EDU (8.6.10/4.7) id WAA13729; Sat, 7 Mar 1998 22:41:48 -0500 Message-Id: <199803080341.WAA13729@exodus.MIT.EDU> To: Steve *Silent Bob* Sadoway Cc: 6042-help@theory.lcs Subject: Re: Problem Set 5 Question 1 In-Reply-To: Your message of "Sat, 07 Mar 1998 22:21:40 EST." <3.0.2.32.19980307222140.007d9c60@hesiod> Date: Sat, 07 Mar 1998 22:41:45 EST Steve, payments begin five years from today, just as you suspected. Thanks for asking! Mark ----------- Mark Roh, mroh@mit.edu (617) 497-4876  0, unseen,, Summary-line: 9-Mar aileen@MIT.EDU [35] #question #2 *** EOOH *** Mail-from: From aileen@MIT.EDU Sun Mar 8 20:31:40 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA14621; Mon, 09 Mar 98 01:32:43 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA20644; Mon, 9 Mar 98 01:31:42 EST Received: from KWAIBAO.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA11040; Mon, 9 Mar 98 01:31:40 EST Message-Id: <3.0.1.32.19980309013140.006a94d8@po7.mit.edu> X-Sender: aileen@po7.mit.edu X-Mailer: Windows Eudora Pro Version 3.0.1 (32) Date: Mon, 09 Mar 1998 01:31:40 -0500 To: 6.042-help@theory.lcs.mit.edu From: Aileen Tang Subject: question #2 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" On problem 2, which property of Hn should we use? Hn=ln(n) or |Hn-ln(n)-gamma| <= |1/2n + 1/12n^2 + 1/120n^4| and express the closed form in terms of an inequality? Thanks, Aileen _________________________________________________________________________ Aileen Tang MM MM IIIIIIII TTTTTTTT Massachusetts Institute of Technology MM MM ~~ II TT 320 Memorial Drive Rm 704 M M M M @@ II TT Cambridge, MA 02139 M MM M C II TT http://kwaibao.mit.edu/ MM MM MM V IIIII TT _________________________________________________________________________  0, unseen,, Summary-line: 9-Mar mroh@MIT.EDU [31] #Re: question #2 *** EOOH *** Mail-from: From mroh@MIT.EDU Sun Mar 8 22:05:04 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA15035; Mon, 09 Mar 98 03:05:44 EST Received: from EXODUS.MIT.EDU by MIT.EDU with SMTP id AA29449; Mon, 9 Mar 98 03:05:11 EST From: mroh@MIT.EDU Received: by exodus.MIT.EDU (8.6.10/4.7) id DAA15192; Mon, 9 Mar 1998 03:05:05 -0500 Message-Id: <199803090805.DAA15192@exodus.MIT.EDU> To: Aileen Tang Cc: 6042-help@theory.lcs Subject: Re: question #2 In-Reply-To: Your message of "Mon, 09 Mar 1998 01:31:40 EST." <3.0.1.32.19980309013140.006a94d8@po7.mit.edu> Date: Mon, 09 Mar 1998 03:05:04 EST Aileen, you shouldn't have to use any special formulas for estimating Hn. Try evaluating the summation for n=1, 2, 3, 4 and see if you can conjecture (and prove by induction) what the closed form solution is. The hint given in the problem may be useful also. Thanks for the email! Mark ----------- Mark Roh, mroh@mit.edu (617) 497-4876  0, unseen,, Summary-line: 9-Mar ez=40mit.edu=3E?=@MIT.EDU [27] # *** EOOH *** Mail-from: From jslopez@MIT.EDU Mon Mar 9 09:07:31 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA04335; Mon, 09 Mar 98 14:08:34 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA12328; Mon, 9 Mar 98 14:08:01 EST Received: from JSLOPEZ.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA04021; Mon, 9 Mar 98 14:07:29 EST Message-Id: <2.2.32.19980309190731.00673f94@po10.mit.edu> X-Sender: jslopez@po10.mit.edu X-Mailer: Windows Eudora Pro Version 2.2 (32) Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Mon, 09 Mar 1998 14:07:31 -0500 To: 6042-help@theory.lcs.mit.edu From: =?iso-8859-1?Q?=22Javier_S._L=F3pez=22_=3Cjslopez=40mit.edu=3E?=@MIT.EDU Subject: Hello, Why in the Lecture 8: Lecture Notes the use p = 8; instead of p = .08 since is 8%. Thank you, Javier  1,, Summary-line: 9-Mar mroh@MIT.EDU [27] #Re: Mail-from: From mroh@MIT.EDU Mon Mar 9 09:11:49 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA04387; Mon, 09 Mar 98 14:12:26 EST Received: from EXODUS.MIT.EDU by MIT.EDU with SMTP id AA13722; Mon, 9 Mar 98 14:11:53 EST From: mroh@MIT.EDU Received: by exodus.MIT.EDU (8.6.10/4.7) id OAA16237; Mon, 9 Mar 1998 14:11:51 -0500 Message-Id: <199803091911.OAA16237@exodus.MIT.EDU> To: jslopez@MIT.EDU Cc: 6042-help@theory.lcs Subject: Re: In-Reply-To: Your message of "Mon, 09 Mar 1998 14:07:31 EST." <2.2.32.19980309190731.00673f94@po10.mit.edu> Date: Mon, 09 Mar 1998 14:11:49 EST *** EOOH *** From: mroh@MIT.EDU To: jslopez@MIT.EDU Cc: 6042-help@theory.lcs Subject: Re: In-Reply-To: Your message of "Mon, 09 Mar 1998 14:07:31 EST." <2.2.32.19980309190731.00673f94@po10.mit.edu> Date: Mon, 09 Mar 1998 14:11:49 EST Javier, you're right: p= .08. Sorry about the typo. Mark ----------- Mark Roh, mroh@mit.edu (617) 497-4876  0, unseen,, Summary-line: 9-Mar ez=40mit.edu=3E?=@MIT.EDU [27] # *** EOOH *** Mail-from: From jslopez@MIT.EDU Mon Mar 9 13:45:44 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA09533; Mon, 09 Mar 98 18:46:46 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA10304; Mon, 9 Mar 98 18:45:45 EST Received: from JSLOPEZ.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA27046; Mon, 9 Mar 98 18:45:42 EST Message-Id: <2.2.32.19980309234544.0067ecc4@po10.mit.edu> X-Sender: jslopez@po10.mit.edu X-Mailer: Windows Eudora Pro Version 2.2 (32) Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Mon, 09 Mar 1998 18:45:44 -0500 To: 6042-help@theory.lcs.mit.edu From: =?iso-8859-1?Q?=22Javier_S._L=F3pez=22_=3Cjslopez=40mit.edu=3E?=@MIT.EDU Subject: Hello, I am wondering is someone could explain me how to do problem 3. I tried to use ln and integrate, but it results in a mess. Thank you, Javier  0, unseen,, Summary-line: 9-Mar mroh@MIT.EDU [31] #prob 3 *** EOOH *** Mail-from: From mroh@MIT.EDU Mon Mar 9 14:11:18 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA09664; Mon, 09 Mar 98 19:12:22 EST Received: from M38-370-12.MIT.EDU by MIT.EDU with SMTP id AA15929; Mon, 9 Mar 98 19:11:20 EST Received: by m38-370-12.MIT.EDU (SMI-8.6/4.7) id TAA15006; Mon, 9 Mar 1998 19:11:19 -0500 Message-Id: <199803100011.TAA15006@m38-370-12.MIT.EDU> To: jslopez@MIT.EDU Cc: 6042-help@theory.lcs Subject: prob 3 In-Reply-To: Your message of "Mon, 09 Mar 1998 18:45:44 EST." <2.2.32.19980309234544.0067ecc4@po10.mit.edu> Date: Mon, 09 Mar 1998 19:11:18 EST From: "Mark C. Roh" Javier, you've got the right idea in taking logs, but I don't think that the integral method is the right way to go for this problem. Why don't you see if you can simplify the sum you get upon taking logs? Since we're dealing with powers of 2 and 4, you might try taking log to a different base than e. Mark ----------- Mark Roh, mroh@mit.edu (617) 497-4876  0, unseen,, Summary-line: 9-Mar ez=40mit.edu=3E?=@MIT.EDU [25] # *** EOOH *** Mail-from: From jslopez@MIT.EDU Mon Mar 9 14:40:46 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA09875; Mon, 09 Mar 98 19:41:48 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA24732; Mon, 9 Mar 98 19:41:15 EST Received: from JSLOPEZ.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA01971; Mon, 9 Mar 98 19:40:44 EST Message-Id: <2.2.32.19980310004046.006dc470@po10.mit.edu> X-Sender: jslopez@po10.mit.edu X-Mailer: Windows Eudora Pro Version 2.2 (32) Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Mon, 09 Mar 1998 19:40:46 -0500 To: 6042-help@theory.lcs.mit.edu From: =?iso-8859-1?Q?=22Javier_S._L=F3pez=22_=3Cjslopez=40mit.edu=3E?=@MIT.EDU Subject: hello again, For problem number 4, how can I get around the i=1, and j=1, to use the definition for iand j=0. Javier  0, unseen,, Summary-line: 9-Mar asomani@MIT.EDU [24] #PS#5 problem #7 *** EOOH *** Mail-from: From asomani@MIT.EDU Mon Mar 9 14:44:05 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA09910; Mon, 09 Mar 98 19:45:10 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA22486; Mon, 9 Mar 98 19:44:08 EST Received: from THE-KID.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA02280; Mon, 9 Mar 98 19:44:05 EST Date: Mon, 9 Mar 98 19:44:05 EST Message-Id: <9803100044.AA02280@MIT.MIT.EDU> X-Sender: asomani@po8.mit.edu X-Mailer: Windows Eudora Pro Version 2.1.2 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" To: 6042-help@theory.lcs.mit.edu From: Ashutosh Somani Subject: PS#5 problem #7 Hi, I believe that the statement given in problem number 7 is true but how does one go about proving something like that? Thanks. Ashutosh Somani asomani@mit.edu  0, unseen,, Summary-line: 9-Mar flattop@MIT.EDU [46] #Re: *** EOOH *** Mail-from: From flattop@MIT.EDU Mon Mar 9 14:55:13 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA09995; Mon, 09 Mar 98 19:56:18 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA25274; Mon, 9 Mar 98 19:55:16 EST Received: from W20-575-7.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA03188; Mon, 9 Mar 98 19:55:14 EST Sender: flattop@MIT.EDU Message-Id: <35048F71.6B0D@MIT.EDU> Date: Mon, 09 Mar 1998 19:55:13 -0500 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Mime-Version: 1.0 To: "Javier S. Lspez @MIT.EDU" Cc: 6042-help@theory.lcs.mit.edu Subject: Re: References: <2.2.32.19980310004046.006dc470@po10.mit.edu> Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit hint: sum from n=1 to infinity of x^i equals sum from n=0 to infinity of x^(i+1) Then now you can apply the formula Hope this helps. jack "Javier S. Lspez" @MIT.EDU wrote: > > hello again, > For problem number 4, > how can I get around the > i=1, and j=1, to use the definition > for iand j=0. > Javier -- MIT Class of 2000 http://web.mit.edu/flattop/www/  0, unseen,, Summary-line: 9-Mar flattop@MIT.EDU [42] #Re: PS#5 problem #7 *** EOOH *** Mail-from: From flattop@MIT.EDU Mon Mar 9 15:00:52 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA10051; Mon, 09 Mar 98 20:01:56 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA26575; Mon, 9 Mar 98 20:00:54 EST Received: from W20-575-7.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA03628; Mon, 9 Mar 98 20:00:52 EST Sender: flattop@MIT.EDU Message-Id: <350490C4.64A7@MIT.EDU> Date: Mon, 09 Mar 1998 20:00:52 -0500 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Mime-Version: 1.0 To: Ashutosh Somani Cc: 6042-help@theory.lcs.mit.edu Subject: Re: PS#5 problem #7 References: <9803100044.AA02280@MIT.MIT.EDU> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Hi Ashutosh, Start with what you know from the if statement: "If f(n) = theta(n)" definition of theta is there exists 3 number a, b, and c all greater than 0 such that for all n>c, a*n <= f(n) <= b*n hope this will help you get started, jack Ashutosh Somani wrote: > > Hi, I believe that the statement given in problem number 7 is true but how > does one go about proving something like that? Thanks. > > Ashutosh Somani > asomani@mit.edu  0, unseen,, Summary-line: 9-Mar jjkim@MIT.EDU [19] # *** EOOH *** Mail-from: From jjkim@MIT.EDU Mon Mar 9 15:13:12 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA10129; Mon, 09 Mar 98 20:14:16 EST Received: from W20-575-70.MIT.EDU by MIT.EDU with SMTP id AA01639; Mon, 9 Mar 98 20:13:42 EST Received: by w20-575-70.MIT.EDU (940816.SGI.8.6.9/4.7) id UAA01772; Mon, 9 Mar 1998 20:13:12 -0500 Message-Id: <199803100113.UAA01772@w20-575-70.MIT.EDU> To: 6042-help@theory.lcs Date: Mon, 09 Mar 1998 20:13:12 EST From: Janice J Kim is the following an example of a closed form solution? 2^(2n!+n) -janice  0, unseen,, Summary-line: 9-Mar flattop@MIT.EDU [37] #Re: *** EOOH *** Mail-from: From flattop@MIT.EDU Mon Mar 9 15:16:56 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA10166; Mon, 09 Mar 98 20:18:13 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA29649; Mon, 9 Mar 98 20:17:07 EST Received: from W20-575-7.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA04926; Mon, 9 Mar 98 20:16:59 EST Sender: flattop@MIT.EDU Message-Id: <35049488.4196@MIT.EDU> Date: Mon, 09 Mar 1998 20:16:56 -0500 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Mime-Version: 1.0 To: Janice J Kim Cc: 6042-help@theory.lcs Subject: Re: References: <199803100113.UAA01772@w20-575-70.MIT.EDU> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Janice, It's a closed form solution, but this answer does not look familiar to any of the qustions???? jack Janice J Kim wrote: > > is the following an example of a closed form > solution? > > 2^(2n!+n) > > -janice  0, unseen,, Summary-line: 9-Mar flattop@MIT.EDU [70] #Re: PS#5 problem #7 *** EOOH *** Mail-from: From flattop@MIT.EDU Mon Mar 9 15:21:47 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA10219; Mon, 09 Mar 98 20:23:15 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA00754; Mon, 9 Mar 98 20:21:58 EST Received: from W20-575-7.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA05343; Mon, 9 Mar 98 20:21:52 EST Sender: flattop@MIT.EDU Message-Id: <350495AB.756A@MIT.EDU> Date: Mon, 09 Mar 1998 20:21:47 -0500 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Mime-Version: 1.0 To: Ashutosh Somani Cc: 6042-help@theory.lcs.mit.edu Subject: Re: PS#5 problem #7 References: <9803100115.AA04798@MIT.MIT.EDU> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit you have to prove that a*n^2 <= sum of f(i) (i=1 to i=n) <= b*n^2 because this is the definition of the theta bounds. jack Ashutosh Somani wrote: > > Hi again, > Well then if I can show that for 3 numbers a, b, and c all greater > than 0 such that for all n>c, > (a*n+a*n^2) <= sum of f(i) (i=1 to i=n) <= (b*n + b*n^2) > this is true, have I proven that the statement holds? > > Ashutosh Somani > asomani@mit.edu > > At 08:00 PM 3/9/98 -0500, you wrote: > >Hi Ashutosh, > > > >Start with what you know from the if statement: > > "If f(n) = theta(n)" > >definition of theta is there exists 3 number a, b, and c all greater > >than 0 such that for all n>c, > > a*n <= f(n) <= b*n > > > >hope this will help you get started, > > > >jack > >Ashutosh Somani wrote: > >> > >> Hi, I believe that the statement given in problem number 7 is true but how > >> does one go about proving something like that? Thanks. > >> > >> Ashutosh Somani > >> asomani@mit.edu > > -- MIT Class of 2000 http://web.mit.edu/flattop/www/  0, unseen,, Summary-line: 9-Mar asomani@MIT.EDU [24] #problem 7 *** EOOH *** Mail-from: From asomani@MIT.EDU Mon Mar 9 15:50:46 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA10394; Mon, 09 Mar 98 20:51:50 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA06164; Mon, 9 Mar 98 20:50:48 EST Received: from THE-KID.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA07912; Mon, 9 Mar 98 20:50:46 EST Date: Mon, 9 Mar 98 20:50:46 EST Message-Id: <9803100150.AA07912@MIT.MIT.EDU> X-Sender: asomani@po8.mit.edu X-Mailer: Windows Eudora Pro Version 2.1.2 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" To: 6042-help@theory.lcs.mit.edu From: Ashutosh Somani Subject: problem 7 For problem 7 of ps 5, I can't decide if the statement is true or if it is false and the second part should read O(n^2). Which one is it? Thanks so much. Ashutosh Somani  0, unseen,, Summary-line: 9-Mar flattop@MIT.EDU [40] #Re: problem 7 *** EOOH *** Mail-from: From flattop@MIT.EDU Mon Mar 9 16:00:30 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA10458; Mon, 09 Mar 98 21:01:34 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA10849; Mon, 9 Mar 98 21:01:01 EST Received: from W20-575-7.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA08771; Mon, 9 Mar 98 21:00:30 EST Sender: flattop@MIT.EDU Message-Id: <35049EBE.772C@MIT.EDU> Date: Mon, 09 Mar 1998 21:00:30 -0500 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Mime-Version: 1.0 To: Ashutosh Somani Cc: 6042-help@theory.lcs.mit.edu Subject: Re: problem 7 References: <9803100150.AA07912@MIT.MIT.EDU> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Hi Ashutosh, If this statement is true, you gotta prove that it is theta(n^2). If not, then show an counterexample. If you think that it is 0(n^2), then the statement might not be true. Then show an example that has a bound of (n )or even (log n). jack Ashutosh Somani wrote: > > For problem 7 of ps 5, I can't decide if the statement is true or if it is > false and the second part should read O(n^2). Which one is it? > Thanks so much. > > Ashutosh Somani  0, unseen,, Summary-line: 9-Mar ez=40mit.edu=3E?=@MIT.EDU [26] # *** EOOH *** Mail-from: From jslopez@MIT.EDU Mon Mar 9 16:23:19 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA10590; Mon, 09 Mar 98 21:24:21 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA12420; Mon, 9 Mar 98 21:23:20 EST Received: from JSLOPEZ.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA10699; Mon, 9 Mar 98 21:23:18 EST Message-Id: <2.2.32.19980310022319.006f094c@po10.mit.edu> X-Sender: jslopez@po10.mit.edu X-Mailer: Windows Eudora Pro Version 2.2 (32) Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Mon, 09 Mar 1998 21:23:19 -0500 To: 6042-help@theory.lcs.mit.edu From: =?iso-8859-1?Q?=22Javier_S._L=F3pez=22_=3Cjslopez=40mit.edu=3E?=@MIT.EDU Subject: Hello, How we fing a theta bound in general(Problem 6) I didn't find about bounds either in the notes or the book. Thank you, Javier  0, unseen,, Summary-line: 9-Mar flattop@MIT.EDU [46] #Re: *** EOOH *** Mail-from: From flattop@MIT.EDU Mon Mar 9 16:34:31 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA10662; Mon, 09 Mar 98 21:35:34 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA18004; Mon, 9 Mar 98 21:35:02 EST Received: from W20-575-7.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA12252; Mon, 9 Mar 98 21:34:31 EST Sender: flattop@MIT.EDU Message-Id: <3504A6B6.482@MIT.EDU> Date: Mon, 09 Mar 1998 21:34:31 -0500 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Mime-Version: 1.0 To: "Javier S. Lspez @MIT.EDU" Cc: 6042-help@theory.lcs.mit.edu Subject: Re: References: <2.2.32.19980310022319.006f094c@po10.mit.edu> Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Javier, A theta bound in general is the "biggest term" without the coeficcients Example: if the equations is (n^2 + n)/2 for the sum from 1+2+3+ ... +n then the theta bound will be theta(n^2) substitute the word "theta" with the greek letter. if it is 14*e^x + 24132*x^40 +5x then it is theta(e^x) jack "Javier S. Lspez" @MIT.EDU wrote: > > Hello, > How we fing a theta bound in general(Problem 6) > > I didn't find about bounds either in the notes > or the book. > > Thank you, Javier  0, unseen,, Summary-line: 9-Mar ez=40mit.edu=3E?=@MIT.EDU [33] # *** EOOH *** Mail-from: From jslopez@MIT.EDU Mon Mar 9 17:37:38 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA11164; Mon, 09 Mar 98 22:38:45 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA27789; Mon, 9 Mar 98 22:37:39 EST Received: from JSLOPEZ.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA19246; Mon, 9 Mar 98 22:37:32 EST Message-Id: <2.2.32.19980310033738.006dd158@po10.mit.edu> X-Sender: jslopez@po10.mit.edu X-Mailer: Windows Eudora Pro Version 2.2 (32) Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Mon, 09 Mar 1998 22:37:38 -0500 To: 6042-help@theory.lcs.mit.edu From: =?iso-8859-1?Q?=22Javier_S._L=F3pez=22_=3Cjslopez=40mit.edu=3E?=@MIT.EDU Subject: Hello, For problem 8 i figured out the close form using derivatives, but I got something extremly messy. Therefore, tough to prove. Is there any other method that work better for this problem. For problem 7, I think that it holds as long as x>1, but I don't have a clue of how to prove it. Could you give me a hint? Thank you, javier  0, unseen,, Summary-line: 9-Mar flattop@MIT.EDU [53] #Re: *** EOOH *** Mail-from: From flattop@MIT.EDU Mon Mar 9 17:47:13 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA11239; Mon, 09 Mar 98 22:48:16 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA29495; Mon, 9 Mar 98 22:47:14 EST Received: from W20-575-7.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA20031; Mon, 9 Mar 98 22:47:12 EST Sender: flattop@MIT.EDU Message-Id: <3504B7C1.68D@MIT.EDU> Date: Mon, 09 Mar 1998 22:47:13 -0500 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Mime-Version: 1.0 To: "Javier S. Lspez @MIT.EDU" Cc: 6042-help@theory.lcs.mit.edu Subject: Re: References: <2.2.32.19980310033738.006dd158@po10.mit.edu> Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit #8 Using derivatives is the right idea. You should end up with some nice solution. Plug in some numbers first to make sure you solution works before you start proving it. For #7, hint to how you start the problem Start with what you know from the if statement: "If f(n) = theta(n)" definition of theta is there exists 3 number a, b, and c all greater than 0 such that for all n>c, a*n <= f(n) <= b*n jack "Javier S. Lspez" @MIT.EDU wrote: > > Hello, > For problem 8 i figured > out the close form using derivatives, > but I got something extremly messy. > Therefore, tough to prove. > Is there any other method that work > better for this problem. > > For problem 7, I think that it holds > as long as x>1, but I don't have a clue of > how to prove it. Could you give me a hint? > > Thank you, > javier  0, unseen,, Summary-line: 9-Mar jamalb@MIT.EDU [25] #pset 5 Q6 and Q9 *** EOOH *** Mail-from: From jamalb@MIT.EDU Mon Mar 9 17:55:10 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA11306; Mon, 09 Mar 98 22:56:26 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA03644; Mon, 9 Mar 98 22:55:54 EST Received: from JAMAL.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA20769; Mon, 9 Mar 98 22:55:23 EST Message-Id: <3.0.32.19980309225509.006dd5a8@po8.mit.edu> X-Sender: jamalb@po8.mit.edu X-Mailer: Windows Eudora Pro Version 3.0 (32) Date: Mon, 09 Mar 1998 22:55:10 -0500 To: 6.042-help@theory.lcs.mit.edu From: Jamal Blackwell Subject: pset 5 Q6 and Q9 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Can I have a hint as to how I can systematically find a theta bound for the sum in question 6? I understand the concept, but I am stumped as far as guessing the function... I also don't know how the integral method will help me to solve problem 9... Thanks, Jamal  0, unseen,, Summary-line: 9-Mar flattop@MIT.EDU [47] #Re: pset 5 Q6 and Q9 *** EOOH *** Mail-from: From flattop@MIT.EDU Mon Mar 9 18:06:36 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA11427; Mon, 09 Mar 98 23:07:39 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA03027; Mon, 9 Mar 98 23:06:38 EST Received: from W20-575-7.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA22053; Mon, 9 Mar 98 23:06:35 EST Sender: flattop@MIT.EDU Message-Id: <3504BC4C.6E79@MIT.EDU> Date: Mon, 09 Mar 1998 23:06:36 -0500 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Mime-Version: 1.0 To: Jamal Blackwell Cc: 6.042-help@theory.lcs.mit.edu Subject: Re: pset 5 Q6 and Q9 References: <3.0.32.19980309225509.006dd5a8@po8.mit.edu> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Jamal, Use the integral method to solve this. Hopefully this was covered in lecture last week. What fuction should you use to calculate the area under the curve of x^6? Purpose is to find a function whose area is slightly less than the summation of x^6 and one that is slightly more. Hint for #8 (not #9) : don't use the integral method. Try something else. jack Jamal Blackwell wrote: > > Can I have a hint as to how I can systematically find a theta bound for the > sum in question 6? I understand the concept, but I am stumped as far as > guessing the function... > I also don't know how the integral method will help me to solve problem 9... > > Thanks, > Jamal -- MIT Class of 2000 http://web.mit.edu/flattop/www/  0, unseen,, Summary-line: 9-Mar jjkim@MIT.EDU [27] #problem 6 *** EOOH *** Mail-from: From jjkim@MIT.EDU Mon Mar 9 18:42:02 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA11700; Mon, 09 Mar 98 23:40:51 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA08877; Mon, 9 Mar 98 23:39:50 EST Received: from JARSOFCLAY.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA25106; Mon, 9 Mar 98 23:39:48 EST Message-Id: <2.2.32.19980310044202.0068e214@po7.mit.edu> X-Sender: jjkim@po7.mit.edu X-Mailer: Windows Eudora Pro Version 2.2 (32) Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Mon, 09 Mar 1998 23:42:02 -0500 To: 6042-help@theory.lcs From: Janice Kim Subject: problem 6 I think I understand what f = theta (g) means... but could explain what a "theta bound" is? Could you give examples too? -janice  1,, Summary-line: 9-Mar flattop@MIT.EDU [52] #Re: problem 6 Mail-from: From flattop@MIT.EDU Mon Mar 9 18:44:13 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA11724; Mon, 09 Mar 98 23:45:16 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA12513; Mon, 9 Mar 98 23:44:43 EST Received: from W20-575-7.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA25444; Mon, 9 Mar 98 23:44:12 EST Sender: flattop@MIT.EDU Message-Id: <3504C51D.E3B@MIT.EDU> Date: Mon, 09 Mar 1998 23:44:13 -0500 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Mime-Version: 1.0 To: Janice Kim Cc: 6042-help@theory.lcs.mit.edu Subject: Re: problem 6 References: <2.2.32.19980310044202.0068e214@po7.mit.edu> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit *** EOOH *** Sender: flattop@MIT.EDU Date: Mon, 09 Mar 1998 23:44:13 -0500 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) To: Janice Kim Cc: 6042-help@theory.lcs.mit.edu Subject: Re: problem 6 References: <2.2.32.19980310044202.0068e214@po7.mit.edu> Janice A theta bound in general is the "biggest term" without the coeficients Example: if the equations is (n^2 + n)/2 for the sum from 1+2+3+ ... +n then the theta bound will be theta(n^2) substitute the word "theta" with the greek letter. if it is 14*e^x + 24132*x^40 +5x then it is theta(e^x) jack Janice Kim wrote: > > I think I understand what > f = theta (g) > means... > > but could explain what a "theta bound" is? > Could you give examples too? > > -janice -- MIT Class of 2000 http://web.mit.edu/flattop/www/  1,, Summary-line: 9-Mar benchun@MIT.EDU [35] #4 and 7 Mail-from: From benchun@MIT.EDU Mon Mar 9 18:45:03 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA11732; Mon, 09 Mar 98 23:46:05 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA09771; Mon, 9 Mar 98 23:45:04 EST Received: from BENCHUN.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA25517; Mon, 9 Mar 98 23:45:01 EST Message-Id: <3.0.32.19980309234502.00ab5830@po8.mit.edu> X-Sender: benchun@po8.mit.edu X-Mailer: Windows Eudora Pro Version 3.0 (32) Date: Mon, 09 Mar 1998 23:45:03 -0500 To: 6.042-help@theory.lcs.mit.edu From: b e n c h u n Subject: 4 and 7 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" *** EOOH *** X-Sender: benchun@po8.mit.edu X-Mailer: Windows Eudora Pro Version 3.0 (32) Date: Mon, 09 Mar 1998 23:45:03 -0500 To: 6.042-help@theory.lcs.mit.edu From: b e n c h u n Subject: 4 and 7 i am having trouble with problem 4 and 7. here is what i know: in problem 4, the higer-order terms approach zero in the limit as i and j go to infinity. i can't figure how to evaluate that, the sum of things that keep getting smaller and smaller and... in problem 7, i know n^6 is omega of the sum and n^7 is big O of the sum. i can't figure how to find something between those that the sum is going to be theta with. thanks for your help. . . . . . . . benchun@mit.edu http://mdma.mit.edu/  1,, Summary-line: 10-Mar cynic@mit.edu [46] #Re: 4 and 7 Mail-from: From cynic@mit.edu Mon Mar 9 19:05:46 1998 Return-Path: Received: from SCHOPENHAUER.MIT.EDU by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA11910; Tue, 10 Mar 98 00:07:06 EST Received: (from cynic@localhost) by SCHOPENHAUER.MIT.EDU (8.8.5/8.8.5) id AAA10581; Tue, 10 Mar 1998 00:05:46 -0500 From: Wesley S Chao Message-Id: <199803100505.AAA10581@SCHOPENHAUER.MIT.EDU> To: b e n c h u n Cc: 6042-help@theory.lcs.MIT.EDU Subject: Re: 4 and 7 In-Reply-To: Your message of "Mon, 09 Mar 1998 23:45:03 EST." <3.0.32.19980309234502.00ab5830@po8.mit.edu> Date: Tue, 10 Mar 1998 00:05:46 EST *** EOOH *** From: Wesley S Chao To: b e n c h u n Cc: 6042-help@theory.lcs.MIT.EDU Subject: Re: 4 and 7 In-Reply-To: Your message of "Mon, 09 Mar 1998 23:45:03 EST." <3.0.32.19980309234502.00ab5830@po8.mit.edu> Date: Tue, 10 Mar 1998 00:05:46 EST >in problem 4, the higer-order terms approach zero in the limit as i and j >go to infinity. i can't figure how to evaluate that, the sum of things that >keep getting smaller and smaller and... Remember that when we have nested summations, it's generally easier to evaluate the sum by grouping expressions with the same incremental variable together (all expressions with i together, all expressions with j together, etc.). It is often easier to find a closed form solution for those expressions, which we can then combine. >in problem 7, i know n^6 is omega of the sum and n^7 is big O of the sum. i >can't figure how to find something between those that the sum is going to >be theta with. First things first. I think you've got the asymptotic expressions backwards; if n^6 is omega of the sum, then n^6 grows as fast or faster than the sum, and if n^7 is O of the sum, then n^7 grows as fast or slower than the sum. These statements conflict, since n^7 grows strictly faster than n^6. Second, if you know that one thing is omega (I assume you mean big omega), of f(n), and something else is big O of f(n), then it is possible that f(n) is theta of either thing. That is to say, big O and big omega leave open the possibility that the two functions grow with the same speed. Hope that helps. Wes.  1,, Summary-line: 10-Mar to: 6042-help [53] #n! Mail-from: From meyer@theory.lcs.mit.edu Mon Mar 9 19:08:34 1998 Return-Path: Received: from stork.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA11929; Tue, 10 Mar 98 00:08:06 EST Received: by stork.lcs.mit.edu (5.65c/TOC-1.2C) id AA07750; Tue, 10 Mar 98 00:08:34 EST Date: Tue, 10 Mar 98 00:08:34 EST Message-Id: <199803100508.AA07750@stork.lcs.mit.edu> From: "Albert R. Meyer" To: 6042-help In-Reply-To: <35049488.4196@MIT.EDU> (flattop@MIT.EDU) Subject: n! Reply-To: 6042-meyer@theory.lcs.mit.edu *** EOOH *** Date: Tue, 10 Mar 98 00:08:34 EST From: "Albert R. Meyer" To: 6042-help In-Reply-To: <35049488.4196@MIT.EDU> (flattop@MIT.EDU) Subject: n! Reply-To: 6042-meyer@theory.lcs.mit.edu To: flattop@MIT.EDU Cc: jjkim@MIT.EDU NO, the expression (n!) doesn't count as a "closed form." It's just an abbreviation for (Pi_{i=1}^n i), and we don't want our closed forms to have sums or products or whatever running over indices. But (n!) can be an informative answer, and if it really can't be simplified away, its presence indicates that there isn't a closed form of the answer. The best we can do with (n!) is assymptotically approximate it with the closed form given by Sterling's formula. Regards, A. Sender: flattop@MIT.EDU Date: Mon, 09 Mar 1998 20:16:56 -0500 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Cc: 6042-help@theory.lcs References: <199803100113.UAA01772@w20-575-70.MIT.EDU> Janice, It's a closed form solution, but this answer does not look familiar to any of the qustions???? jack Janice J Kim wrote: > > is the following an example of a closed form > solution? > > 2^(2n!+n) > > -janice ------- End of forwarded message -------  1,, Summary-line: 10-Mar jjkim@MIT.EDU [31] #Problem 6 Mail-from: From jjkim@MIT.EDU Mon Mar 9 19:21:34 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA12123; Tue, 10 Mar 98 00:20:24 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA15081; Tue, 10 Mar 98 00:19:22 EST Received: from JARSOFCLAY.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA28022; Tue, 10 Mar 98 00:19:20 EST Message-Id: <2.2.32.19980310052134.0068a638@po7.mit.edu> X-Sender: jjkim@po7.mit.edu X-Mailer: Windows Eudora Pro Version 2.2 (32) Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Tue, 10 Mar 1998 00:21:34 -0500 To: 6042-help@theory.lcs.mit.edu From: Janice Kim Subject: Problem 6 *** EOOH *** X-Sender: jjkim@po7.mit.edu X-Mailer: Windows Eudora Pro Version 2.2 (32) Date: Tue, 10 Mar 1998 00:21:34 -0500 To: 6042-help@theory.lcs.mit.edu From: Janice Kim Subject: Problem 6 Can we use the integral method to find the theta bound for number 6? so, would k^7 be the uper bound by this method? -janice ------------------------------------------------------- Janice Juyeon Kim 410 Memorial Drive Cambridge, MA 02139 e-mail : jjkim@mit.edu web : http://www.mit.edu/people/jjkim/Welcome.html -------------------------------------------------------  1,, Summary-line: 10-Mar cynic@mit.edu [35] #Re: Problem 6 Mail-from: From cynic@mit.edu Mon Mar 9 19:25:21 1998 Return-Path: Received: from SCHOPENHAUER.MIT.EDU by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA12199; Tue, 10 Mar 98 00:26:35 EST Received: (from cynic@localhost) by SCHOPENHAUER.MIT.EDU (8.8.5/8.8.5) id AAA10952; Tue, 10 Mar 1998 00:25:22 -0500 From: Wesley S Chao Message-Id: <199803100525.AAA10952@SCHOPENHAUER.MIT.EDU> To: Janice Kim Cc: 6042-help@theory.lcs.MIT.EDU Subject: Re: Problem 6 In-Reply-To: Your message of "Tue, 10 Mar 1998 00:21:34 EST." <2.2.32.19980310052134.0068a638@po7.mit.edu> Date: Tue, 10 Mar 1998 00:25:21 EST *** EOOH *** From: Wesley S Chao To: Janice Kim Cc: 6042-help@theory.lcs.MIT.EDU Subject: Re: Problem 6 In-Reply-To: Your message of "Tue, 10 Mar 1998 00:21:34 EST." <2.2.32.19980310052134.0068a638@po7.mit.edu> Date: Tue, 10 Mar 1998 00:25:21 EST >Can we use the integral method to find the theta bound for number 6? Not only can you, you should. In general, when you're looking to find a theta bound, the integral method is one of the first things to try. The very process of using the integral method lends itself to the definition of a theta bound. Anyway, the short answer, again, is yes. >so, would k^7 be the uper bound by this method? Sort of. I'm betting you mean n^7, so I'll be a little anal -- k is being incremented towards n, so the expression k^7 doesn't really mean anything in the context of the question. You want to express your theta bound in n. Wes.  1,, Summary-line: 10-Mar jjkim@MIT.EDU [23] #Integral Method Mail-from: From jjkim@MIT.EDU Mon Mar 9 20:11:01 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA12533; Tue, 10 Mar 98 01:09:55 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA24650; Tue, 10 Mar 98 01:09:22 EST Received: from JARSOFCLAY.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA01741; Tue, 10 Mar 98 01:08:47 EST Message-Id: <2.2.32.19980310061101.0069c664@po7.mit.edu> X-Sender: jjkim@po7.mit.edu X-Mailer: Windows Eudora Pro Version 2.2 (32) Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Tue, 10 Mar 1998 01:11:01 -0500 To: 6042-help@theory.lcs.MIT.EDU From: Janice Kim Subject: Integral Method *** EOOH *** X-Sender: jjkim@po7.mit.edu X-Mailer: Windows Eudora Pro Version 2.2 (32) Date: Tue, 10 Mar 1998 01:11:01 -0500 To: 6042-help@theory.lcs.MIT.EDU From: Janice Kim Subject: Integral Method Is there a clear description of hte Integral method somewhere in the lecture notes, Rosen, or Nuts and Bolts? -janice  1,, Summary-line: 10-Mar cynic@mit.edu [22] #Re: Integral Method Mail-from: From cynic@mit.edu Mon Mar 9 20:16:28 1998 Return-Path: Received: from SCHOPENHAUER.MIT.EDU by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA12589; Tue, 10 Mar 98 01:17:43 EST Received: (from cynic@localhost) by SCHOPENHAUER.MIT.EDU (8.8.5/8.8.5) id BAA11389; Tue, 10 Mar 1998 01:16:29 -0500 From: Wesley S Chao Message-Id: <199803100616.BAA11389@SCHOPENHAUER.MIT.EDU> To: Janice Kim Cc: 6042-help@theory.lcs.MIT.EDU Subject: Re: Integral Method In-Reply-To: Your message of "Tue, 10 Mar 1998 01:11:01 EST." <2.2.32.19980310061101.0069c664@po7.mit.edu> Date: Tue, 10 Mar 1998 01:16:28 EST *** EOOH *** From: Wesley S Chao To: Janice Kim Cc: 6042-help@theory.lcs.MIT.EDU Subject: Re: Integral Method In-Reply-To: Your message of "Tue, 10 Mar 1998 01:11:01 EST." <2.2.32.19980310061101.0069c664@po7.mit.edu> Date: Tue, 10 Mar 1998 01:16:28 EST >Is there a clear description of hte Integral method somewhere in the lecture >notes, Rosen, or Nuts and Bolts? The best place to look would be the Fall '97 notes, a link to which ought to be on the current 6.042 website. The exact date on which the notes were presented escapes me at the moment, but if you are having trouble finding it, I can look it up for you. I do remember that there are two sets of notes, from lectures on consecutive days. One has an example of using the Integral Method on a function which is increasing, and the other has an example of using it on a function which is decreasing. There are some subtle differences between the two. Wes.  1,, Mail-from: From flattop@MIT.EDU Tue Mar 10 07:07:12 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA18458; Tue, 10 Mar 98 12:08:19 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA07195; Tue, 10 Mar 98 12:07:46 EST Received: from M12-182-5.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA00986; Tue, 10 Mar 98 12:07:11 EST Sender: flattop@MIT.EDU Message-Id: <35057340.41C6@MIT.EDU> Date: Tue, 10 Mar 1998 12:07:12 -0500 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; IRIX 5.3 IP22) Mime-Version: 1.0 To: 6042-meyer@theory.lcs.mit.edu Cc: 6042-help@theory.lcs.mit.edu Subject: Re: zephyr info References: <199803101504.AA08248@stork.lcs.mit.edu> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit *** EOOH *** Sender: flattop@MIT.EDU Date: Tue, 10 Mar 1998 12:07:12 -0500 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; IRIX 5.3 IP22) To: 6042-meyer@theory.lcs.mit.edu Cc: 6042-help@theory.lcs.mit.edu Subject: Re: zephyr info References: <199803101504.AA08248@stork.lcs.mit.edu> We'll talk more about this in our helpers meeting. Is it this Thurday at 4:30? jack Albert R. Meyer wrote: > > Do you intend to be available by zephyr as well as email during 6042-help > hours? If so, how about adding zephyr contact info to the help-info page? > > Regards, A. -- MIT Class of 2000 http://web.mit.edu/flattop/www/ From psomani@MIT.EDU Sat Mar 14 19:36:24 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA09815; Sun, 15 Mar 98 00:37:31 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA05577; Sun, 15 Mar 98 00:36:27 EST Received: from FLASH-80.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA25109; Sun, 15 Mar 98 00:36:24 EST Date: Sun, 15 Mar 98 00:36:24 EST Message-Id: <9803150536.AA25109@MIT.MIT.EDU> X-Sender: psomani@po8.mit.edu X-Mailer: Windows Eudora Pro Version 2.1.2 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" To: 6042-help@theory.lcs.mit.edu From: Paritosh Somani Subject: plug and chug I am a little confused as to how you get theta bounds for functions for which the master theorem does not apply. I know that you plug/chug or use the interations to get a pattern/sum and get a formula.....but then what? How do you get the theta bound from this? Do you approximate along some time? Also, I had a question regarding the integration method: Do you set the limits of integration from 0 to n and 0 to (n+1) OR do you keep them 0 to n for both but add a + 1 for the larger integral? this refers to probelm 15, part (a) because the answers keep the same limits of integration (1 to n) and just do +1 for the larger one. thanks Paritosh Somani From asomani@MIT.EDU Sat Mar 14 19:36:31 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA09821; Sun, 15 Mar 98 00:37:38 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA24430; Sun, 15 Mar 98 00:37:06 EST Received: from THE-KID.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA25117; Sun, 15 Mar 98 00:36:31 EST Date: Sun, 15 Mar 98 00:36:31 EST Message-Id: <9803150536.AA25117@MIT.MIT.EDU> X-Sender: asomani@po8.mit.edu X-Mailer: Windows Eudora Pro Version 2.1.2 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" To: 6042-help@theory.lcs.mit.edu From: Ashutosh Somani Subject: Hi, I had a question regarding problem 18 d) on the practice quiz...could you just give me a general explanantion of what approach they are using to solve the problem and how they accomplished it? Thanks. Ashutosh Somani From cynic@mit.edu Sun Mar 15 11:25:40 1998 Return-Path: Received: from SCHOPENHAUER.MIT.EDU by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA13134; Sun, 15 Mar 98 16:26:51 EST Received: (from cynic@localhost) by SCHOPENHAUER.MIT.EDU (8.8.5/8.8.5) id QAA27145; Sun, 15 Mar 1998 16:25:40 -0500 From: Wesley S Chao Message-Id: <199803152125.QAA27145@SCHOPENHAUER.MIT.EDU> To: 6042-help@theory.lcs.MIT.EDU Subject: Theta bounds Date: Sun, 15 Mar 1998 16:25:40 EST >I am a little confused as to how you get theta bounds for functions for >which the master theorem does not apply. Did we go over the Akra-Bazzi formula for finding theta bounds on recursive functions? It would seem that Akra-Bazzi is the natural answer to the question, but maybe we haven't covered it. It is in last term's curriculum, is why I ask... Wes. From mroh@MIT.EDU Sun Mar 15 12:05:58 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA13330; Sun, 15 Mar 98 17:07:01 EST Received: from EXODUS.MIT.EDU by MIT.EDU with SMTP id AA19883; Sun, 15 Mar 98 17:05:58 EST From: mroh@MIT.EDU Received: by exodus.MIT.EDU (8.6.10/4.7) id RAA16791; Sun, 15 Mar 1998 17:05:58 -0500 Message-Id: <199803152205.RAA16791@exodus.MIT.EDU> To: Wesley S Chao Cc: 6042-help@theory.lcs Subject: Re: Theta bounds In-Reply-To: Your message of "Sun, 15 Mar 1998 16:25:40 EST." <199803152125.QAA27145@SCHOPENHAUER.MIT.EDU> Date: Sun, 15 Mar 1998 17:05:58 EST Wes, Akra-Bazzi is not part of this semester's curriculum. Mark ----------- Mark Roh, mroh@mit.edu (617) 497-4876 From wchien@MIT.EDU Mon Mar 16 14:46:12 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA26605; Mon, 16 Mar 98 19:47:17 EST Received: from W20-575-82.MIT.EDU by MIT.EDU with SMTP id AA28314; Mon, 16 Mar 98 19:46:45 EST Received: by w20-575-82.MIT.EDU (940816.SGI.8.6.9/4.7) id TAA17043; Mon, 16 Mar 1998 19:46:12 -0500 Message-Id: <199803170046.TAA17043@w20-575-82.MIT.EDU> To: 6042-help@theory.lcs.mit.edu Subject: Re: plug and chug In-Reply-To: Your message of "Sun, 15 Mar 1998 00:36:24 EST." <9803150536.AA25109@MIT.MIT.EDU> Date: Mon, 16 Mar 1998 19:46:12 EST From: Wendy S Chien *****I sent this to Paritosh already, but i forgot to cc it to *****6042-help Hi Paritosh, Has anyone answered your question? > I am a little confused as to how you get theta bounds for functions for > which the master theorem does not apply. > I know that you plug/chug or use the interations to get a pattern/sum and > get a formula.....but then what? How do you get the theta bound from this? > Do you approximate along some time? When you use plug and chug you should get a summation of which you hopefully know the closed form (something like nlog(n) or n(n+1)/2). From there you can find the theta bounds. > Also, I had a question regarding the integration method: Do you set the > limits of integration from 0 to n and 0 to (n+1) OR do you keep them 0 to n > for both but add a + 1 for the larger integral? this refers to probelm 15, > part (a) because the answers keep the same limits of integration (1 to n) > and just do +1 for the larger one. It depends. The reason why they added a "+1" to the integral in problem 15 is because the first block in the sum is at height 1. If this is not the case, then you cannot just add 1 to the integral. As for the upper bound, it depends on what your function inside the integral is. It is usually easiest to determine the correct bounds by drawing out the summation blocks and connecting the upper left corners to get the function of one of the bounds and connecting the upper right corners of the blocks for the function that serves as the other bound. By looking at these two functions you can read off what the right bounds are. If any of this response is confusing or unclear, please email again. Wendy From wchien@MIT.EDU Mon Mar 16 14:52:20 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA26669; Mon, 16 Mar 98 19:53:45 EST Received: from W20-575-82.MIT.EDU by MIT.EDU with SMTP id AA00546; Mon, 16 Mar 98 19:53:09 EST Received: by w20-575-82.MIT.EDU (940816.SGI.8.6.9/4.7) id TAA17057; Mon, 16 Mar 1998 19:52:20 -0500 Message-Id: <199803170052.TAA17057@w20-575-82.MIT.EDU> To: Ashutosh Somani Cc: 6042-help@theory.lcs.mit.edu Subject: Re: In-Reply-To: Your message of "Sun, 15 Mar 1998 00:36:31 EST." <9803150536.AA25117@MIT.MIT.EDU> Date: Mon, 16 Mar 1998 19:52:20 EST From: Wendy S Chien Hi Ashutosh, > I had a question regarding problem 18 d) on the practice > quiz...could you just give me a general explanantion of what approach they > are using to solve the problem and how they accomplished it? Thanks. They are using the Guess and Verify (aka substitution) method. They make a guess as to what they think the bound is and then they use induction to prove it. They guess theta(n) probably because the g(n) term is n and it seems like it would dominate the recurrence (there would be more work due to n than the T(n/4) and T(n/2)). Wendy From akl@MIT.EDU Mon Mar 16 16:44:52 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA27350; Mon, 16 Mar 98 21:47:24 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA10856; Mon, 16 Mar 98 21:46:51 EST Received: from AKL.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA29224; Mon, 16 Mar 98 21:46:15 EST Message-Id: <9803170246.AA29224@MIT.MIT.EDU> X-Sender: akl@po9.mit.edu X-Mailer: QUALCOMM Windows Eudora Pro Version 4.0 Demo Date: Mon, 16 Mar 1998 21:44:52 -0500 To: 6042-help@theory.lcs.mit.edu From: "Aimee K. Lee" Subject: clarification Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" hi, do i need to know boolean assigments and divide-and-conquer recurrences for the test? thanks. aimee lee *********************************************** Aimee K. Lee <>< 320 Memorial Drive Cambridge, MA 02139 MIT class of 2001 From kylee@mit.edu Mon Mar 16 17:30:44 1998 Return-Path: Received: from KINGS-COLLEGE.MIT.EDU by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA27702; Mon, 16 Mar 98 22:31:51 EST Received: (from kylee@localhost) by Kings-College.MIT.edu (8.8.5/8.8.5) id WAA28175; Mon, 16 Mar 1998 22:30:45 -0500 Message-Id: <199803170330.WAA28175@Kings-College.MIT.edu> To: "Aimee K. Lee" Cc: 6042-help@theory.lcs.mit.edu Subject: Re: clarification In-Reply-To: Your message of "Mon, 16 Mar 1998 21:44:52 EST." <9803170246.AA29224@MIT.MIT.EDU> Date: Mon, 16 Mar 1998 22:30:44 EST From: Edmond Kayi Lee >do i need to know boolean assigments and divide-and-conquer >recurrences for the test? Divide and conquer recurrence is difinitely covered. You should be familiar with the Master Theorem and Plug and Chuck method, and know how to derive a recurrence as well. Boolean assignment is not formally taught as a topic. But it is a concept that may appear and not too hard to understand. Informally, given a boolean formula, e.g., (x^y)->z, where x, y, z are boolean variables, a boolean assignment is the assignment of boolean values (T/F) of the variables in the formula. For instance, the assignment x=T, y=F, z=T is one of the boolean assignments for the formula (there are other assignment for the formula.). And that's what a boolean assignment means. Formally speaking, a boolean assignment is a function which maps the set of boolean variables in a boolean formula to the set {T, F}. So this is what it means, let me know if you have more questions. Edmond From meyer@theory.lcs.mit.edu Mon Mar 16 17:33:00 1998 Return-Path: Received: from stork.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA27708; Mon, 16 Mar 98 22:32:28 EST Received: by stork.lcs.mit.edu (5.65c/TOC-1.2C) id AA13550; Mon, 16 Mar 98 22:33:00 EST Date: Mon, 16 Mar 98 22:33:00 EST Message-Id: <199803170333.AA13550@stork.lcs.mit.edu> From: "Albert R. Meyer" To: akl@MIT.EDU Cc: 6042-help@theory.lcs.mit.edu In-Reply-To: <9803170246.AA29224@MIT.MIT.EDU> (akl@MIT.EDU) Subject: Re: clarification Reply-To: 6042-meyer@theory.lcs.mit.edu Divide and Conquer: YES Boolean assignments: NO Regards, A. X-Sender: akl@po9.mit.edu X-Mailer: QUALCOMM Windows Eudora Pro Version 4.0 Demo Date: Mon, 16 Mar 1998 21:44:52 -0500 From: "Aimee K. Lee" hi, do i need to know boolean assigments and divide-and-conquer recurrences for the test? thanks. aimee lee *********************************************** Aimee K. Lee <>< 320 Memorial Drive Cambridge, MA 02139 MIT class of 2001 From jjkim@KOA.MIT.EDU Tue Mar 17 20:09:52 1998 Return-Path: Received: from KOA.MIT.EDU by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA13655; Wed, 18 Mar 98 01:10:58 EST Received: (from jjkim@localhost) by KOA.MIT.EDU (8.8.5/8.8.5) id BAA13694; Wed, 18 Mar 1998 01:09:52 -0500 From: Janice J Kim Message-Id: <199803180609.BAA13694@KOA.MIT.EDU> To: 6042-help@theory.lcs.mit.edu Subject: practice prob 9c Date: Wed, 18 Mar 1998 01:09:52 EST hello... in the solution for practice problem 9c, they use the term odd cycle. Could you define odd cycle and and explain why it cannot be bipartite. Also, could you explain why a graph colored with two colors must be bipartite. thanks :) -janice From kylee@MIT.EDU Tue Mar 17 20:27:31 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA13843; Wed, 18 Mar 98 01:28:36 EST Received: from W20-575-65.MIT.EDU by MIT.EDU with SMTP id AA02278; Wed, 18 Mar 98 01:27:32 EST Received: by w20-575-65.MIT.EDU (940816.SGI.8.6.9/4.7) id BAA09483; Wed, 18 Mar 1998 01:27:31 -0500 Message-Id: <199803180627.BAA09483@w20-575-65.MIT.EDU> To: Janice J Kim Cc: 6042-help@theory.lcs.mit.edu Subject: Re: practice prob 9c In-Reply-To: Your message of "Wed, 18 Mar 1998 01:09:52 EST." <199803180609.BAA13694@KOA.MIT.EDU> Date: Wed, 18 Mar 1998 01:27:31 EST From: Edmond Kayi Lee An odd cycle is a cycle with odd number of vertices. If C is an odd cycle, we can number the vertices as 1,2,3,...,2n+1 along the cycle. Assume it is bipartite, then we know that vertex 1 and 2 have to be in different sets, namely A and B, since they are adjacent. Then you should see that (and we can use induction to prove that) all odd numbers have to be in set A and even numbers have to be in set B. So we have both vertices 2n+1 and 1 in set A. But they are adjacent, and it contradicts that all vertices in set A are not adjacent. So C cannot be bipartite. If a graph is 2 colorable, then the vertices of the graph can be divided into 2 sets according to their colors, namely A and B. By definition of coloring, nodes with same color are not adjacent to each other, so every node in set A is not adjacent to each other. Similarly, every node in set B is not adjacent to each other. This satisfies the defintion of being a bipartite graph. Let me know if you still have questions. Edmond From jslee@BBN.COM Wed Mar 18 11:09:04 1998 Return-Path: Received: from DIAGHILEV.BBN.COM by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA22729; Wed, 18 Mar 98 16:02:00 EST Message-Id: <199803182102.AA22729@theory.lcs.mit.edu> To: 6042-help@theory.lcs.mit.edu Subject: Practice Quiz Prob 19. Date: Wed, 18 Mar 98 16:09:04 -0500 From: jslee@BBN.COM (b). T(n) = 4T(n/3) + n. Solution shows that the summation in the big parenthesis is Theta(4/3)**log3n. Is it because a summation of geometric sequence whose "x" term is greater than 1 is Theta(L) where L is the upper bound for the index of the summation : i=L SIGMA x**i = Theta(x**L) , x< 1 ? i=0 Why is (4/3)**log(base3)n = Theta (n**(log(base3)(4/3))) ? (4/3)**log(base3)n = [ 4 * (3**(-1)) ] ** log(base3)n = (4 ** log(base3)n ) * (3**(-log(base3)n)) = (4 ** log(base3)n ) * 1/n so, why is (4 ** log(base3)n ) ??= Theta (n**(log(base3)(4/3))) From brianlin@MIT.EDU Wed Mar 18 11:01:43 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA22752; Wed, 18 Mar 98 16:02:45 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA06516; Wed, 18 Mar 98 16:01:40 EST Received: from BRIANLIN.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA07258; Wed, 18 Mar 98 16:01:35 EST Message-Id: X-Sender: brianlin@po8.mit.edu X-Mailer: QUALCOMM Windows Eudora Pro Version 4.0 Demo Date: Wed, 18 Mar 1998 16:01:43 -0500 To: 6042-help@theory.lcs.mit.edu From: Li-Kuo Lin Subject: 8b, 18d, 19ab, Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" In the inductive step of part b of 8, you said that if G(n+1) was regular then P(n+1) holds trivially, but didn't we already say that the graphs were not regular? Plus, isn't a regular graph of degree k, only k+1 colorable? For 18d, what method did you exactly use, that you were allowed to substitute alpha*n for T(n)..and why does it work, and which type of recurrences can you use it for? For 19, why couldn't you have used the master theorem to solve them, also if I was to write the recurrence as a sum... for example, "a" would be (SUM from i=0 to k) (7^i)(n/3^i)^2 how would I come to the same conclusion using this method, or is that an impossibility, can I also use the sum method for "b"? For 19 and recurrences in general, after you iterate, is it true that you can get rid of any term that doesn't have an "n" in them, even if they are multiplied by some function of n when you change to theta notation? Also in general, is it true that the theta bound of any sum is just the integral of the function being summed (with limits as the limits of the index of summation)? Thanks a bunch ---------------------------------------------------------------------------- ------------------ Li-Kuo (Brian) Lin 410 Memorial Drive Cambridge MA, 02139 (617)-225-8265 brianlin@mit.edu "The only thing that interferes with my learning is my education." -Albert Einstein / \ / / \ \ \' , / / / \ \ \ / /, _/ / / , \ _ -/ / ' / / / <, \ / / / > \ \ \` __/_ /, ) -^>> _\` \ \ \ ( / \ \ / /\ \ / / _/ / \ \ \ \ ( ( ` ( ( From kylee@MIT.EDU Wed Mar 18 11:20:53 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA23210; Wed, 18 Mar 98 16:22:15 EST Received: from W20-575-104.MIT.EDU by MIT.EDU with SMTP id AA13482; Wed, 18 Mar 98 16:21:01 EST Received: by w20-575-104.MIT.EDU (940816.SGI.8.6.9/4.7) id QAA23303; Wed, 18 Mar 1998 16:20:53 -0500 Message-Id: <199803182120.QAA23303@w20-575-104.MIT.EDU> To: jslee@BBN.COM Cc: 6042-help@theory.lcs.mit.edu Subject: Re: Practice Quiz Prob 19. In-Reply-To: Your message of "Wed, 18 Mar 1998 16:09:04 EST." <199803182102.AA22729@theory.lcs.mit.edu> Date: Wed, 18 Mar 1998 16:20:53 EST From: Edmond Kayi Lee Solution shows that the summation in the big parenthesis is Theta(4/3)**log3n. Is it because a summation of geometric sequence whose "x" term is greater than 1 is Theta(L) where L is the upper bound for the index of the summation : i=L SIGMA x**i = Theta(x**L) , x< 1 ? i=0 What you have said is a Omega bound for the summation. For Theta, we need to find an uppen bound as well. From the formula, we have i=L SIGMA x^i = (1-x^i)/(1-x) i=0 Here, x=(4/3) and L=log_3 n, so the summation becomes: (1-(4/3)^(log n))/(1-(4/3)) =3*(4/3)^(log n)-3 =Theta((4/3)^(log n)) This answers your first question. For the second question, Why is (4/3)**log(base3)n = Theta (n**(log(base3)(4/3))) ? Let k=4/3 (4/3)**log(base3)n =k^(log_3 n) =(3^(log_3 k))^(log_3 n) =(3^ ((log_3 k)(log_3 n)) ) =(3^ ((log_3 n)(log_3 k)) ) =n^(log_3 k) which is what we want. -Edmond From kylee@MIT.EDU Wed Mar 18 11:38:59 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA23463; Wed, 18 Mar 98 16:40:11 EST Received: from W20-575-104.MIT.EDU by MIT.EDU with SMTP id AA02602; Wed, 18 Mar 98 16:39:39 EST Received: by w20-575-104.MIT.EDU (940816.SGI.8.6.9/4.7) id QAA23315; Wed, 18 Mar 1998 16:38:59 -0500 Message-Id: <199803182138.QAA23315@w20-575-104.MIT.EDU> To: Li-Kuo Lin Cc: 6042-help@theory.lcs.mit.edu Subject: Re: 8b, 18d, 19ab, In-Reply-To: Your message of "Wed, 18 Mar 1998 16:01:43 EST." Date: Wed, 18 Mar 1998 16:38:59 EST From: Edmond Kayi Lee >In the inductive step of part b of 8, you said that if G(n+1) was regular >then P(n+1) holds trivially, but didn't we already say that the graphs were >not regular? Plus, isn't a regular graph of degree k, only k+1 colorable? The statement is in the form of "If A then B", where A is "G is a connected graph of n vertices and maximum node degree k that is not regular" and B is "G is k-colorable". So in the prove, if G is regular, then A is false, so "If A then B" is trivially true, even if it is only k+1 colorable. >For 18d, what method did you exactly use, that you were allowed to >substitute alpha*n for T(n)..and why does it work, and which type of >recurrences can you use it for? This is more like guessing. You assume that T(n) is linear (possibly by playing around with the recurrence). Then you prove that the recurrence is always smaller than alpha*n for some alpha, thereby proving big O. It is Omega(n) because of the term n in the recurrence. You have the recurrence T(n)=T(n/2)+T(n/4)+n >= n for all n, so it is Omega. Since it is both big O and big Omega, it is Theta of n. >For 19, why couldn't you have used the master theorem to solve them, also >if I was to write the recurrence as a sum... >for example, "a" would be (SUM from i=0 to k) (7^i)(n/3^i)^2 > >how would I come to the same conclusion using this method, or is that an >impossibility, can I also use the sum method for "b"? You can definitely use Master's Thm in Q 19. Your sum is basically the same as the one is solution, after you simplify it a little bit, you will get the same answer. part "b" is using the sum method in the solution. (I assume the sum method you mean is iteration). >For 19 and recurrences in general, after you iterate, is it true that you >can get rid of any term that doesn't have an "n" in them, even if they are >multiplied by some function of n when you change to theta notation? I am not sure what you are asking. But in all cases you have to be careful with this. For example, if I get a summation like (1+1+...+1) with n terms in it. You cannot drop those 1's because if you drop them, the sum will become 0 which is not true. This is because there are n terms inside. >Also in general, is it true that the theta bound of any sum is just the >integral of the function being summed (with limits as the limits of the >index of summation)? Not true in general. For some weird functions you can't use the integral method to bound them. Every time you use the method you better draw a picture to make sure the integrals you derive serve well as the upper bound and the lower bound of the summation. -Edmond From brianlin@MIT.EDU Wed Mar 18 11:52:42 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA23767; Wed, 18 Mar 98 16:53:45 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA23646; Wed, 18 Mar 98 16:52:40 EST Received: from BRIANLIN.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA17416; Wed, 18 Mar 98 16:52:35 EST Message-Id: <9803182152.AA17416@MIT.MIT.EDU> X-Sender: brianlin@po8.mit.edu X-Mailer: QUALCOMM Windows Eudora Pro Version 4.0 Demo Date: Wed, 18 Mar 1998 16:52:42 -0500 To: 6042-help@theory.lcs.mit.edu From: Li-Kuo Lin Subject: sums Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" is the growth of n^ (log k) where k<1 and it's the log of any base constant? so if you have n^2(n^l(log k)) is that theta n^2 ? ---------------------------------------------------------------------------- ------------------ Li-Kuo (Brian) Lin 410 Memorial Drive Cambridge MA, 02139 (617)-225-8265 brianlin@mit.edu "The only thing that interferes with my learning is my education." -Albert Einstein / \ / / \ \ \' , / / / \ \ \ / /, _/ / / , \ _ -/ / ' / / / <, \ / / / > \ \ \` __/_ /, ) -^>> _\` \ \ \ ( / \ \ / /\ \ / / _/ / \ \ \ \ ( ( ` ( ( From kylee@MIT.EDU Wed Mar 18 12:06:57 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA24026; Wed, 18 Mar 98 17:08:10 EST Received: from W20-575-104.MIT.EDU by MIT.EDU with SMTP id AA11193; Wed, 18 Mar 98 17:07:31 EST Received: by w20-575-104.MIT.EDU (940816.SGI.8.6.9/4.7) id RAA23362; Wed, 18 Mar 1998 17:06:57 -0500 Message-Id: <199803182206.RAA23362@w20-575-104.MIT.EDU> To: Li-Kuo Lin Cc: 6042-help@theory.lcs.mit.edu Subject: Re: sums In-Reply-To: Your message of "Wed, 18 Mar 1998 16:52:42 EST." <9803182152.AA17416@MIT.MIT.EDU> Date: Wed, 18 Mar 1998 17:06:57 EST From: Edmond Kayi Lee >is the growth of n^ (log k) > >where k<1 > >and it's the log of any base > >constant? I should say the growth of n^(log k) is just THETA(n^(log k)). There is nothing more we can say about it. If log k<0, then it is O(1) but not THETA(1). IF you want to give a THETA bound, the function itself is the answer. > so if you have n^2(n^l(log k)) is that theta n^2 ? Again, the function itself is the answer. -Edmond From jslee@BBN.COM Mon Mar 23 08:54:31 1998 Return-Path: Received: from DIAGHILEV.BBN.COM by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA21179; Mon, 23 Mar 98 13:44:49 EST Message-Id: <199803231844.AA21179@theory.lcs.mit.edu> To: 6042-help@theory.lcs.mit.edu Cc: mroh@mit.edu Subject: course web site Date: Mon, 23 Mar 98 13:54:31 -0500 From: jslee@BBN.COM Could someone please post the writeup for last week's recitation (Recitation 7?) on the Web site? Thank you! From meyer@theory.lcs.mit.edu Mon Mar 23 12:10:30 1998 Return-Path: Received: from stork.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA25083; Mon, 23 Mar 98 17:09:55 EST Received: by stork.lcs.mit.edu (5.65c/TOC-1.2C) id AA01837; Mon, 23 Mar 98 17:10:30 EST Date: Mon, 23 Mar 98 17:10:30 EST Message-Id: <199803232210.AA01837@stork.lcs.mit.edu> From: "Albert R. Meyer" To: jslee@BBN.COM Cc: 6042-help@theory.lcs.mit.edu, mroh@mit.edu In-Reply-To: <199803231844.AA21179@theory.lcs.mit.edu> (jslee@BBN.COM) Subject: Re: course web site Reply-To: 6042-meyer@theory.lcs.mit.edu It's been available on the web page for several days. Yours truly, Prof. Albert R. Meyer MIT Lab. for Computer Science Cc: mroh@mit.edu Date: Mon, 23 Mar 98 13:54:31 -0500 From: jslee@BBN.COM Could someone please post the writeup for last week's recitation (Recitation 7?) on the Web site? Thank you! From mphil14@MIT.EDU Mon Mar 23 16:15:13 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA29791; Mon, 23 Mar 98 21:16:21 EST Received: from SCRUBBING-BUBBLES.MIT.EDU by MIT.EDU with SMTP id AA10425; Mon, 23 Mar 98 21:15:14 EST Received: by scrubbing-bubbles.MIT.EDU (8.8.7/4.7) id VAA19864; Mon, 23 Mar 1998 21:15:13 -0500 (EST) Message-Id: <199803240215.VAA19864@scrubbing-bubbles.MIT.EDU> To: 6042-help@theory.lcs.mit.edu Subject: PS 6 Date: Mon, 23 Mar 1998 21:15:13 EST From: Mark Phillip Hi, for problem 3b) I end up with f(n)= f(n-1) + 2f(n-2) + 3(n-1). When I am setting up the characteristic equation in 3c), what do I do with the 3(n-1)? Any help would be appreciated...thanks...-mark Mark Phillip Phi Sigma Kappa Boston MA, 02215 REEFPRODUCTIONS.mit.edu web.mit.edu/mphil14/www "near...far.....NEAR....FAR!!!" From BLin922@aol.com Tue Mar 24 13:20:18 1998 Return-Path: Received: from imo15.mx.aol.com by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA18613; Tue, 24 Mar 98 18:21:32 EST Received: from BLin922@aol.com by imo15.mx.aol.com (IMOv13.ems) id RWDHa22227 for <6042-help@theory.lcs.mit.edu>; Tue, 24 Mar 1998 18:20:18 -0500 (EST) From: BLin922 Message-Id: <524b4ac6.35183fb4@aol.com> Date: Tue, 24 Mar 1998 18:20:18 EST To: 6042-help@theory.lcs.mit.edu Mime-Version: 1.0 Subject: possible error in ps6 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-Mailer: AOL 3.0 for Windows 95 sub 49 I don't know if you guys are checking this mail during spring break but I think there is an error in part b of problem 2. It asks you to find a closed form solution, given three initial conditions. however, 2 of the roots of the characteristic equations are identical, therefore I don't think there is a possible way that all three initial conditions can be satisfied. I have worked on this problem for at least 5 hours now, and have tried several methods and have come up with the same answer: I am only able to satisfy two initial conditions, 0, and 16, but after that, my series does satisfy the recurrence. If there is an error, please reply to this e-mail or post it on the web, or could you give me a hint if it is in fact possible? Brian Lin (Li-kuo) brianlin@mit.edu From flattop@MIT.EDU Tue Mar 24 13:34:16 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA18836; Tue, 24 Mar 98 18:35:27 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA15742; Tue, 24 Mar 98 18:34:55 EST Received: from M1-142-1.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA15209; Tue, 24 Mar 98 18:34:13 EST Sender: flattop@MIT.EDU Message-Id: <351842F8.559@MIT.EDU> Date: Tue, 24 Mar 1998 18:34:16 -0500 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Mime-Version: 1.0 To: BLin922 Cc: 6042-help@theory.lcs.mit.edu Subject: Re: possible error in ps6 References: <524b4ac6.35183fb4@aol.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Hi Brian, That was the intent of the problem. If two of the roots are the same, you do this: (let say it a double root of 5) A*5^n + B*n*5^n Do you remember this from lecture? This is similar to what you would do in 18.03. Hope this helped. jack BLin922 wrote: > > I don't know if you guys are checking this mail during spring break but I > think there is an error in part b of problem 2. It asks you to find a closed > form solution, given three initial conditions. however, 2 of the roots of the > characteristic equations are identical, therefore I don't think there is a > possible way that all three initial conditions can be satisfied. I have > worked on this problem for at least 5 hours now, and have tried several > methods and have come up with the same answer: I am only able to satisfy two > initial conditions, 0, and 16, but after that, my series does satisfy the > recurrence. If there is an error, please reply to this e-mail or post it on > the web, or could you give me a hint if it is in fact possible? > > Brian Lin > (Li-kuo) > brianlin@mit.edu -- MIT Class of 2000 http://web.mit.edu/flattop/www/ From cynic@mit.edu Wed Mar 25 10:12:54 1998 Return-Path: Received: from SCHOPENHAUER.MIT.EDU by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA22575; Wed, 25 Mar 98 15:14:10 EST Received: (from cynic@localhost) by SCHOPENHAUER.MIT.EDU (8.8.5/8.8.5) id PAA20257; Wed, 25 Mar 1998 15:12:54 -0500 From: Wesley S Chao Message-Id: <199803252012.PAA20257@SCHOPENHAUER.MIT.EDU> To: Mark Phillip Cc: 6042-help@theory.lcs.mit.edu Subject: Re: PS 6 In-Reply-To: Your message of "Mon, 23 Mar 1998 21:15:13 EST." <199803240215.VAA19864@scrubbing-bubbles.MIT.EDU> Date: Wed, 25 Mar 1998 15:12:54 EST > for problem 3b) I end up with f(n)= f(n-1) + 2f(n-2) + 3(n-1). When I am se >tting up the characteristic equation in 3c) what do I do with the 3(n-1)? Any >help would be appreciated...thanks...-mark Has your question been answered yet? It seems a little old, but if not... When we solve recurrences, we want to try and get a closed form; in doing so, we want to find the characteristic equation, *but*, the characteristic equation is only useful is solving for the *homogenous* solution (think differential equations). For a simple recurrence, like, say, Fibonacci numbers, the homogenous solution is the total solution. But in the case of problem 3, there is a particular solution. Your equation, properly rearranged, should look like this: f(n) - f(n-1) - 2f(n-2) = 3(n-1). Then you can set the right hand side to 0 and solve as you would normally for the homogenous solution. After that, you can solve for the particular solution just as you would for differential equations (guess a form with undetermined coefficients, then solve for the coefficients). Oh, and as a final note, check your equation for 3b. According to the copy of the problem set I have, 3(n-3) physicists become professors, not 3(n-1). Hope this is helpful. Wes. From psomani@MIT.EDU Mon Apr 2 17:13:33 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA04123; Mon, 30 Mar 98 22:14:50 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA01641; Mon, 30 Mar 98 22:13:41 EST Received: from FLASH-80.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA20278; Mon, 30 Mar 98 22:13:33 EST Date: Mon, 30 Mar 98 22:13:33 EST Message-Id: <9803310313.AA20278@MIT.MIT.EDU> X-Sender: psomani@po8.mit.edu X-Mailer: Windows Eudora Pro Version 2.1.2 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" To: 6042-help@theory.lcs.mit.edu From: Paritosh Somani Subject: #6 Hi, I have no clue as to approaching question 6 on the problem set. How would one use the hint? How do you prove that a string is countable? Thanks, Paritosh From flattop@MIT.EDU Mon Apr 2 17:26:06 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA04234; Mon, 30 Mar 98 22:27:18 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA04382; Mon, 30 Mar 98 22:26:47 EST Received: from W20-575-25.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA21382; Mon, 30 Mar 98 22:26:00 EST Sender: flattop@MIT.EDU Message-Id: <3520624E.5867@MIT.EDU> Date: Mon, 30 Mar 1998 22:26:06 -0500 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Mime-Version: 1.0 To: Paritosh Somani Cc: 6042-help@theory.lcs.mit.edu Subject: Re: #6 References: <9803310313.AA20278@MIT.MIT.EDU> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Hi The definition of countable is to be able to list the set. Even though the set might be infinite, if you find a way to list that set such that all the elements are listed, then it is countable. For example, the set of natural numbers in countable because you can list them: { 0, 1, 2, 3, 4, 5, 6, 7 ... } So the hint tells you to find a way to list these infinite binary strings, which is the harder part. Hope this sort of helps jack Paritosh Somani wrote: > > Hi, > > I have no clue as to approaching question 6 on the problem set. > How would one use the hint? > How do you prove that a string is countable? > Thanks, > Paritosh -- MIT Class of 2000 http://web.mit.edu/flattop/www/ From asomani@MIT.EDU Mon Apr 2 17:30:08 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA04301; Mon, 30 Mar 98 22:31:29 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA04502; Mon, 30 Mar 98 22:30:15 EST Received: from THE-KID.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA21743; Mon, 30 Mar 98 22:30:08 EST Date: Mon, 30 Mar 98 22:30:08 EST Message-Id: <9803310330.AA21743@MIT.MIT.EDU> X-Sender: asomani@po8.mit.edu X-Mailer: Windows Eudora Pro Version 2.1.2 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" To: 6.042-help@theory.lcs.mit.edu From: Ashutosh Somani Subject: PS #6 Problem 5 Hi, I had a question about problem 5 part a)....Can we assume that sin x is defined over all x (so it would fail the horizontal line test) or do we assume it is defined from -pi/2 to pi/2?? Thanks, Ashutosh Somani asomani@mit.edu From flattop@MIT.EDU Mon Apr 2 17:34:37 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA04363; Mon, 30 Mar 98 22:35:49 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA05224; Mon, 30 Mar 98 22:34:39 EST Received: from W20-575-25.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA22079; Mon, 30 Mar 98 22:34:32 EST Sender: flattop@MIT.EDU Message-Id: <3520644D.650B@MIT.EDU> Date: Mon, 30 Mar 1998 22:34:37 -0500 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Mime-Version: 1.0 To: Ashutosh Somani Cc: 6.042-help@theory.lcs.mit.edu Subject: Re: PS #6 Problem 5 References: <9803310330.AA21743@MIT.MIT.EDU> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Hi, sin x IS defined over all x I think that you are confused regarding sine and inverse sine Hope this helps. jack Ashutosh Somani wrote: > > Hi, > I had a question about problem 5 part a)....Can we assume that sin x > is defined over all x (so it would fail the horizontal line test) or do we > assume it is defined from -pi/2 to pi/2?? > > Thanks, > > Ashutosh Somani > asomani@mit.edu From jjkim@MIT.EDU Mon Apr 2 18:46:31 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA04967; Mon, 30 Mar 98 23:46:37 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA16835; Mon, 30 Mar 98 23:45:27 EST Received: from JARSOFCLAY.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA28236; Mon, 30 Mar 98 23:45:20 EST Message-Id: <2.2.32.19980331044631.00682b8c@po7.mit.edu> X-Sender: jjkim@po7.mit.edu X-Mailer: Windows Eudora Pro Version 2.2 (32) Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Mon, 30 Mar 1998 23:46:31 -0500 To: 6042-help@theory.lcs.mit.edu From: Janice Kim Subject: pset6, problem 5a hello... i have a question on number 5a. f(x)= sin x I can see that this is not an injection because both f(2pi) and f(0) equal the same thing... but 2pi does not equal 0. Then, from this can we conclude that it is not a bijection? (rosen says that a bijection is one-to-one and onto) Also, can we conclude that it is not a surjection because f(x) never equals 2? I'm trying to relate my thinking to the examples on page 62 and 63 in Rosen. There, i think rosen says that f(x) = x^2 is neither a injection or surjection. Is my reasoning correct? I guess what's confusing me is that f(x) = sin x can be a surjection between the range (-1,1), right? and f(x) = sin x can be an bijection within a certain range because it has an inverse between a certain range... is that right? do we have to include this in our homework write-up? hrmm.... :( -janice ------------------------------------------------------- Janice Juyeon Kim 410 Memorial Drive Cambridge, MA 02139 e-mail : jjkim@mit.edu web : http://www.mit.edu/people/jjkim/Welcome.html ------------------------------------------------------- From cynic@mit.edu Mon Apr 2 19:05:30 1998 Return-Path: Received: from SCHOPENHAUER.MIT.EDU by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA05224; Tue, 31 Mar 98 00:06:49 EST Received: (from cynic@localhost) by SCHOPENHAUER.MIT.EDU (8.8.5/8.8.5) id AAA28059; Tue, 31 Mar 1998 00:05:32 -0500 From: Wesley S Chao Message-Id: <199803310505.AAA28059@SCHOPENHAUER.MIT.EDU> To: Janice Kim Cc: 6042-help@theory.lcs.mit.edu Subject: Re: pset6, problem 5a In-Reply-To: Your message of "Mon, 30 Mar 1998 23:46:31 EST." <2.2.32.19980331044631.00682b8c@po7.mit.edu> Date: Tue, 31 Mar 1998 00:05:30 EST >I can see that this is not an injection because both >f(2pi) and f(0) equal the same thing... but 2pi does not equal 0. >Then, from this can we conclude that it is not a bijection? >(rosen says that a bijection is one-to-one and onto) Yes, we can. As long as we can prove rigorously that a function is either not an injection or not a surjection, we can simply state something to the effect of, "since it is not an injection/surjection, it is not a bijection by definition". >Also, can we conclude that it is not a surjection because f(x) never equals 2? Yes, again. >There, i think rosen says that f(x) = x^2 is neither a injection or surjection Also correct. (Are you sure you need to be sending mail here? :) >Is my reasoning correct? Yes. >I guess what's confusing me is that > f(x) = sin x >can be a surjection between the range (-1,1), right? Ah, yes. In general, you can make any function a surjection, IF you define the domain and range to fit the function. For instance, mapping the reals to the numbers between -1 and 1, inclusive, is a surjection for sin x. We can construct a similar example for making sin x an injection. >can be an bijection within a certain range because it has an inverse between >a certain range... is that right? Yep, something like mapping the numbers between -pi/2 and pi/2 to the numbers between -1 and 1, would make sin x a bijection. >do we have to include this in our homework write-up? Since the question specifically states mapping numbers from the reals to the reals, no. You can simply say, "the function is not an injection and surjection defined over the given range." Wes. From ecoder@MIT.EDU Mon Apr 2 22:13:50 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA06787; Tue, 31 Mar 98 03:15:38 EST Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA13791; Tue, 31 Mar 98 03:14:29 EST Received: from INSANITY.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA11426; Tue, 31 Mar 98 03:14:21 EST Message-Id: <3.0.32.19980331031349.0084dc10@po7.mit.edu> X-Sender: ecoder@po7.mit.edu X-Mailer: Windows Eudora Pro Version 3.0 (32) Date: Tue, 31 Mar 1998 03:13:50 -0500 To: 6042-help@theory.lcs From: Eugene Vaynshteyn Subject: 6.042 questions Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Hello, I know this is extremely late-notice, but I would appreciate any help you can offer before lecture time tomorrow (Tuesday). On Problem 4b, I have no idea how to deal with the n^(1/3) term in the recurrence. It seems that we have only dealt with constant multiples of n in the past. And I don't really know how to approach problem 7; the book does not talk about that stuff and the examples in the lecture notes are not very similar to the problem -- so I would appreciate any help. Thanks a lot and sorry for asking this so late. Eugene From cynic@mit.edu Tue Apr 3 07:41:26 1998 Return-Path: Received: from SCHOPENHAUER.MIT.EDU by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA13952; Tue, 31 Mar 98 12:42:38 EST Received: (from cynic@localhost) by SCHOPENHAUER.MIT.EDU (8.8.5/8.8.5) id MAA02747; Tue, 31 Mar 1998 12:41:26 -0500 From: Wesley S Chao Message-Id: <199803311741.MAA02747@SCHOPENHAUER.MIT.EDU> To: 6042-help@theory.lcs.mit.edu Subject: Re: 6.042 questions In-Reply-To: Your message of "Tue, 31 Mar 1998 03:13:50 EST." <3.0.32.19980331031349.0084dc10@po7.mit.edu> Date: Tue, 31 Mar 1998 12:41:26 EST >I know this is extremely late-notice, but I would appreciate any help you >can offer before lecture time tomorrow (Tuesday). Hopefully, you'll have checked your mail after noon on Tuesday... >On Problem 4b, I have no idea how to deal with the n^(1/3) term in the >recurrence. It seems that we have only dealt with constant multiples of n >in the past. Yes, this is true. We can't solve recurrences with an n^1/3 term as is, so what we have to do is implement a change of variables. Define a new variable m, such that n = 2^m. Rearrange the equation with that. Then you should have something of the form f(2^m) = a(2^m/b) + g(m), where g(m) involves 2^m. Define a new function S(m) = f(2^m) to get S(m) in a form you can solve via Master Method. Substitute back in the relation n = 2^m, and you should be done. Side note #1: When you do the master method on S(m), you will almost definitely have to deal with g(m) having an exponential term (i.e., 2^m). This is case #3 for Master Method. >And I don't really know how to approach problem 7; the book does not talk >about that stuff and the examples in the lecture notes are not very similar >to the problem -- so I would appreciate any help. We want to prove this by diagonalization. The idea behind diagonalization is that we arrange a proof by contradiction: first, assume we can list whatever it is we are trying to list. Then, create a new element which is different in some regard from every element already in the list. (When we do this with numbers, we often make the new number different in every digit, so that the ith digit is different from the ith number. When we draw this out, we get a diagonal list of different numbers; hence, the name diagonalization.) Prove that this element should be in the list, because it satisfies whatever requirements the other elements satisfy. Then, show that this element is not in the list, which ought to be easy, because it should differ from the ith element in some way, if you have done the diagonalization right. >Thanks a lot and sorry for asking this so late. Hope this gets to you on time. Wes. From 152412@eXvCFg.com Wed Apr 1 09:57:02 1998 Return-Path: <152412@eXvCFg.com> Received: from mail.man.net by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA03731; Wed, 01 Apr 98 16:55:44 EST Received: (from smap@localhost) by mail.man.net (8.8.6/8.8.6) id PAA29913 for <6042-help@theory.lcs.mit.edu>; Wed, 1 Apr 1998 15:57:02 -0600 Date: Wed, 1 Apr 1998 15:57:02 -0600 From: 152412@eXvCFg.com Message-Id: <199804012157.PAA29913@mail.man.net> Received: from unknown(206.168.234.64) by mail.man.net via smap (V1.3) id sma008445; Wed Apr 1 15:56:32 1998 To: 6042-help@theory.lcs.mit.edu Subject: Affordable High Performance Web Hosting Now when you sign up for web hosting with http://www.PerformanceServices.net you get free site submission to over 620 search engines.* http://www.PerformanceServices.net provides high speed virtual websitehosting services for $40.00 per month including the following: - Microsoft Front Page Server extensions - Support for Active Server Pages & Microsoft Visual InterDev - Free site submission to over 620 search engines* - Comprehensive monthly web site statistics - Choice of primary server country - 5 inbound E-Mail boxes with E-Mail forwarding & autoresponders - FTP access with one username and password - Microsoft Access 97 - Microsoft SQL Server 6.5 - Microsoft Index Server - Microsoft Transaction Server - Microsoft Distributed Transaction Coordinator - CGI program support - PERL program support - Complete daily backups - One DNS mapping for your domain name - Access to raw history files - ISAPI support - 20 MB of disk storage - Complete user configurable Active Server Page shopping cart - coming 04-30-98 - Free SSL Certificate from The Digital Certificates Verification Authority - coming 04-30-98 - CyberCash - coming 05-24-98 (extra charges may apply) - Volcano Chat - coming 05-15-98 - True Speech - coming 05-25-98 (extra charges may apply) - Real Audio & Streaming Video - coming 05-31-98(extra charges will apply) This is a limited time offer so come to http://www.PerformanceServices.net and sign up today! Thank you. * Clients must prepay the first six months of service to qualify for one time free site submission From asomani@MIT.EDU Mon Apr 6 16:39:49 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA29956; Mon, 06 Apr 98 20:41:10 EDT Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA24713; Mon, 6 Apr 98 20:40:41 EDT Received: from THE-KID.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA12013; Mon, 6 Apr 98 20:39:49 EDT Date: Mon, 6 Apr 98 20:39:49 EDT Message-Id: <9804070039.AA12013@MIT.MIT.EDU> X-Sender: asomani@po8.mit.edu X-Mailer: Windows Eudora Pro Version 2.1.2 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" To: 6.042-help@theory.lcs.mit.edu From: Ashutosh Somani Subject: I had a question regarding the formula for palcing r indistinguishable balls into n distinguishable bins. Is it r-1 choose n-1 or is it r+n-1 choose r ? Thanks. Ashutosh Somani From flattop@MIT.EDU Mon Apr 6 16:49:18 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA29998; Mon, 06 Apr 98 20:50:34 EDT Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA24184; Mon, 6 Apr 98 20:49:22 EDT Received: from TEST-SPARC4.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA13031; Mon, 6 Apr 98 20:49:13 EDT Sender: flattop@MIT.EDU Message-Id: <3529780E.4B9A@MIT.EDU> Date: Mon, 06 Apr 1998 20:49:18 -0400 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Mime-Version: 1.0 To: Ashutosh Somani Cc: 6.042-help@theory.lcs.mit.edu Subject: Re: Problem #4 References: <9804070039.AA12013@MIT.MIT.EDU> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Hi, It's the second one, r+n-1 choose r. jack Ashutosh Somani wrote: > > I had a question regarding the formula for palcing r indistinguishable balls > into n distinguishable bins. Is it r-1 choose n-1 or is it r+n-1 choose r ? > Thanks. > > Ashutosh Somani From digital@sls.lcs.mit.edu Mon Apr 6 18:00:29 1998 Return-Path: Received: from sls.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA00586; Mon, 06 Apr 98 22:01:43 EDT Received: from bjorn.lcs.mit.edu by sls.lcs.mit.edu (4.1/SLS-4.1.1) id AA03337; Mon, 6 Apr 98 22:00:30 EDT Received: from bjorn.lcs.mit.edu by bjorn.lcs.mit.edu (SMI-8.6/SMI-SVR4) id WAA25244; Mon, 6 Apr 1998 22:00:29 -0400 Message-Id: <199804070200.WAA25244@bjorn.lcs.mit.edu> X-Mailer: exmh version 2.0zeta 7/24/97 To: 6042-help@theory.lcs.mit.edu Subject: ps 7 problem 7 Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Mon, 06 Apr 1998 22:00:29 -0400 From: James Wood Do you have any hints for ps 7 problem 7 ? Thanks in advance. --- James F. Wood, Jr. Athena: digital@mit.edu SLS: digital@sls.lcs.mit.edu http://web.mit.edu/digital/ http://www.sls.lcs.mit.edu/~digital/ From jslopez@MIT.EDU Mon Apr 6 18:10:07 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA00653; Mon, 06 Apr 98 22:11:21 EDT Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA09363; Mon, 6 Apr 98 22:10:09 EDT Received: from JSLOPEZ.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA20913; Mon, 6 Apr 98 22:09:59 EDT Message-Id: <2.2.32.19980407021007.00694844@po10.mit.edu> X-Sender: jslopez@po10.mit.edu X-Mailer: Windows Eudora Pro Version 2.2 (32) Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Mon, 06 Apr 1998 22:10:07 -0400 To: 6042-help@theory.lcs.mit.edu From: =?iso-8859-1?Q?=22Javier_S._L=F3pez=22_=3Cjslopez=40mit.edu=3E?=@MIT.EDU Subject: Problem #7 Hello, I have been trying to figure out how to do problem #7, but i do not even know how to begin. Could you give me a hint on how to start the problem. thank you, Javier From flattop@MIT.EDU Mon Apr 6 18:16:38 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA00668; Mon, 06 Apr 98 22:17:58 EDT Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA12548; Mon, 6 Apr 98 22:17:29 EDT Received: from TEST-SPARC4.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA21560; Mon, 6 Apr 98 22:16:33 EDT Sender: flattop@MIT.EDU Message-Id: <35298C85.1A9C@MIT.EDU> Date: Mon, 06 Apr 1998 22:16:38 -0400 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Mime-Version: 1.0 To: James Wood Cc: 6042-help@theory.lcs.mit.edu Subject: Re: ps 7 problem 7 References: <199804070200.WAA25244@bjorn.lcs.mit.edu> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Here's a hint: First ignore the constraint that the two subsets S, T are disjoint How would you prove that there are two non-empty subsets A, B such that A is not equal to B and their summations using these two subsets are equal? Second, given that you have these two non-empty different subsets A,B, how would you make them disjoint? Hope this will direct you in the right direction. jack James Wood wrote: > > Do you have any hints for ps 7 problem 7 ? > > Thanks in advance. > --- > > James F. Wood, Jr. > Athena: digital@mit.edu > SLS: digital@sls.lcs.mit.edu > http://web.mit.edu/digital/ > http://www.sls.lcs.mit.edu/~digital/ From flattop@MIT.EDU Mon Apr 6 18:17:34 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA00676; Mon, 06 Apr 98 22:18:50 EDT Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AB12710; Mon, 6 Apr 98 22:18:21 EDT Received: from TEST-SPARC4.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA21681; Mon, 6 Apr 98 22:17:29 EDT Sender: flattop@MIT.EDU Message-Id: <35298CBE.1C51@MIT.EDU> Date: Mon, 06 Apr 1998 22:17:34 -0400 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Mime-Version: 1.0 To: "Javier S. Lspez @MIT.EDU" Cc: 6042-help@theory.lcs.mit.edu Subject: Re: Problem #7 References: <2.2.32.19980407021007.00694844@po10.mit.edu> Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Here's a hint: First ignore the constraint that the two subsets S, T are disjoint How would you prove that there are two non-empty subsets A, B such that A is not equal to B and their summations using these two subsets are equal? Second, given that you have these two non-empty different subsets A,B, how would you make them disjoint? Hope this will direct you in the right direction. jack "Javier S. Lspez" @MIT.EDU wrote: > > Hello, > I have been trying to figure out > how to do problem #7, but i do not even know > how to begin. Could you give me a hint > on how to start the problem. > > thank you, > Javier From ecoder@MIT.EDU Tue Apr 7 07:36:56 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA06792; Tue, 07 Apr 98 11:38:59 EDT Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA20054; Tue, 7 Apr 98 11:37:47 EDT Received: from INSANITY.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA05584; Tue, 7 Apr 98 11:37:37 EDT Message-Id: <3.0.32.19980407113654.00859e20@po7.mit.edu> X-Sender: ecoder@po7.mit.edu X-Mailer: Windows Eudora Pro Version 3.0 (32) Date: Tue, 07 Apr 1998 11:36:56 -0400 To: 6042-help@theory.lcs.mit.edu From: Eugene Vaynshteyn Subject: PS7, questions 7 and 8 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Hi, I know that this is extremely late notice, but if someone could reply before lecture with any hints on questions 7 and 8, I would really appreciate it. I did the rest of the problem set with very few problems, but I am totally clueless on these two. Thanks, Eugene From meyer@theory.lcs.mit.edu Tue Apr 7 08:12:11 1998 Return-Path: Received: from stork.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA07475; Tue, 07 Apr 98 12:13:18 EDT Received: by stork.lcs.mit.edu (5.65c/TOC-1.2C) id AA11232; Tue, 07 Apr 98 12:12:11 EDT Date: Tue, 07 Apr 98 12:12:11 EDT Message-Id: <199804071612.AA11232@stork.lcs.mit.edu> From: "Albert R. Meyer" To: ecoder@MIT.EDU Cc: 6042-help@theory.lcs.mit.edu In-Reply-To: <3.0.32.19980407113654.00859e20@po7.mit.edu> (message from Eugene Vaynshteyn on Tue, 07 Apr 1998 11:36:56 -0400) Subject: Re: PS7, questions 7 and 8 Reply-To: 6042-meyer@theory.lcs.mit.edu For prob 7, initially ignore the disjointness condition. Then use pigeonholing. That's all I have time to write now. Regards, A. From flattop@MIT.EDU Sat Apr 11 07:59:00 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA07899; Sat, 11 Apr 98 12:00:16 EDT Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA02546; Sat, 11 Apr 98 11:59:02 EDT Received: from W20-575-7.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA12688; Sat, 11 Apr 98 11:58:51 EDT Sender: flattop@MIT.EDU Message-Id: <352F9344.15DB@MIT.EDU> Date: Sat, 11 Apr 1998 11:59:00 -0400 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Mime-Version: 1.0 To: 6042-help@theory.lcs.mit.edu Subject: Online hours Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit This message of primarily for the course assistants. During meeting last Thursday with Prof. Meyer, he decided to have only three hours of online help on Monday night. I went ahead and updated the web page and stated that the online help session will be from 8pm to 11pm monday night. So who wants to do which hour? For convience sake, it will be a first come fist serve basis, so please e-mail to this mailing list. If all the hours are not taken Sunday night, I will man the left over hours. thanks jack From ssadoway@MIT.EDU Sun Apr 12 21:10:56 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA15134; Mon, 13 Apr 98 01:12:45 EDT Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA15727; Mon, 13 Apr 98 01:11:31 EDT Received: from SILENT-BOB.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA18209; Mon, 13 Apr 98 01:11:19 EDT Message-Id: <3.0.2.32.19980413011056.008136a0@hesiod> X-Sender: ssadoway@hesiod X-Mailer: QUALCOMM Windows Eudora Pro Version 3.0.2 (32) Date: Mon, 13 Apr 1998 01:10:56 -0400 To: 6042-help@theory.lcs.mit.edu From: Steve *Silent Bob* Sadoway Subject: Pset 8, Problem 4c Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" A quick question... it asks for the 17th coefficient... is this assuming the first one listed is the zero-th coefficient? I'm getting a sequence that looks something like <0, -8, 0 -32, 0, ...> Is that first 0 the zero-th coefficient? Is it the first coefficient, or is the -8 the 1st coefficient and the -32 the 2nd coefficient? Maybe it's just too late for me right now, but I just wanted to clear that up. Thanks! -->Steve ~~~~~~~~~~~~~~~~~~~~~~~~~Steven Sadoway~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ E-mail: ssadoway@mit.edu | Homepage: http://web.mit.edu/ssadoway/www/ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ "We were talking 'bout something, seems like was funny, then Steven got quiet - I think Steven was mad. Maybe he wasn't mad, but we felt very strange, in the moment, but the moment was passed and forgotten about." --Ben Folds Five, "Steven's Last Night In Town" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ From meyer@theory.lcs.mit.edu Mon Apr 13 04:59:20 1998 Return-Path: Received: from stork.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA16796; Mon, 13 Apr 98 09:00:24 EDT Received: by stork.lcs.mit.edu (5.65c/TOC-1.2C) id AA15201; Mon, 13 Apr 98 08:59:20 EDT Date: Mon, 13 Apr 98 08:59:20 EDT Message-Id: <199804131259.AA15201@stork.lcs.mit.edu> From: "Albert R. Meyer" To: ssadoway@MIT.EDU In-Reply-To: <3.0.2.32.19980413011056.008136a0@hesiod> (message from Steve *Silent Bob* Sadoway on Mon, 13 Apr 1998 01:10:56 -0400) Subject: Re: Pset 8, Problem 4c Reply-To: 6042-meyer@theory.lcs.mit.edu Cc: 6042-help your choice to start w/ 0 or 1, but say which. Regards, A. X-Sender: ssadoway@hesiod X-Mailer: QUALCOMM Windows Eudora Pro Version 3.0.2 (32) Date: Mon, 13 Apr 1998 01:10:56 -0400 From: Steve *Silent Bob* Sadoway A quick question... it asks for the 17th coefficient... is this assuming the first one listed is the zero-th coefficient? I'm getting a sequence that looks something like <0, -8, 0 -32, 0, ...> Is that first 0 the zero-th coefficient? Is it the first coefficient, or is the -8 the 1st coefficient and the -32 the 2nd coefficient? Maybe it's just too late for me right now, but I just wanted to clear that up. Thanks! -->Steve ~~~~~~~~~~~~~~~~~~~~~~~~~Steven Sadoway~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ E-mail: ssadoway@mit.edu | Homepage: http://web.mit.edu/ssadoway/www/ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ "We were talking 'bout something, seems like was funny, then Steven got quiet - I think Steven was mad. Maybe he wasn't mad, but we felt very strange, in the moment, but the moment was passed and forgotten about." --Ben Folds Five, "Steven's Last Night In Town" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ From jslopez@MIT.EDU Mon Apr 13 13:51:13 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA22867; Mon, 13 Apr 98 17:52:30 EDT Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA09371; Mon, 13 Apr 98 17:52:01 EDT Received: from JSLOPEZ.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA07598; Mon, 13 Apr 98 17:51:03 EDT Message-Id: <2.2.32.19980413215113.006a4dbc@po10.mit.edu> X-Sender: jslopez@po10.mit.edu X-Mailer: Windows Eudora Pro Version 2.2 (32) Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Mon, 13 Apr 1998 17:51:13 -0400 To: 6042-help@theory.lcs.mit.edu From: =?iso-8859-1?Q?=22Javier_S._L=F3pez=22_=3Cjslopez=40mit.edu=3E?=@MIT.EDU Subject: Problem 4c,d Hello, I do not undertsand this question. Could you tell me what are they asking for? Thank you, Javier From wchien@MIT.EDU Mon Apr 13 16:20:40 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA24100; Mon, 13 Apr 98 20:22:12 EDT Received: from W20-575-19.MIT.EDU by MIT.EDU with SMTP id AA25165; Mon, 13 Apr 98 20:20:50 EDT Received: by w20-575-19.MIT.EDU (SMI-8.6/4.7) id UAA02665; Mon, 13 Apr 1998 20:20:41 -0400 Message-Id: <199804140020.UAA02665@w20-575-19.MIT.EDU> To: jslopez@MIT.EDU Cc: 6042-help@theory.lcs.mit.edu Subject: Re: Problem 4c,d In-Reply-To: Your message of "Mon, 13 Apr 1998 17:51:13 EDT." <2.2.32.19980413215113.006a4dbc@po10.mit.edu> Date: Mon, 13 Apr 1998 20:20:40 EDT From: Wendy S Chien > Hello, > I do not undertsand > this question. Could you tell > me what are they asking for? > Thank you, > Javier Part (a) and (b) of problem 4 have you write the partial fraction decomposition of the functions given. In that form you will see that they look like the sum of a sequence. Once you change this into polynomial form, you will be able to read off the coefficients that the question is asking for. Last term's Lecture 17 on OGF's do a problem very similar to this that you can see as an example. Hope this helps. Wendy From ecoder@MIT.EDU Mon Apr 13 18:46:05 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA25254; Mon, 13 Apr 98 22:48:19 EDT Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA03971; Mon, 13 Apr 98 22:47:50 EDT Received: from INSANITY.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA05521; Mon, 13 Apr 98 22:46:53 EDT Message-Id: <3.0.32.19980413224605.008c0150@po7.mit.edu> X-Sender: ecoder@po7.mit.edu X-Mailer: Windows Eudora Pro Version 3.0 (32) Date: Mon, 13 Apr 1998 22:46:05 -0400 To: 6.042-help@theory.lcs From: Eugene Vaynshteyn Subject: PS8, problem 3 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Hi! In problem 3 on the problem set, are we required to find a closed form for the ogf? e.g., for (a) can we just say: <1,1,1,1,1,...> <--> 1+x+x^2+x^3+... or do we need to say 1/(1-x) ? Thanks, Eugene From wchien@MIT.EDU Mon Apr 13 18:59:45 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA25401; Mon, 13 Apr 98 23:01:02 EDT Received: from W20-575-19.MIT.EDU by MIT.EDU with SMTP id AA06110; Mon, 13 Apr 98 23:00:33 EDT Received: by w20-575-19.MIT.EDU (SMI-8.6/4.7) id WAA03304; Mon, 13 Apr 1998 22:59:45 -0400 Message-Id: <199804140259.WAA03304@w20-575-19.MIT.EDU> To: Eugene Vaynshteyn Cc: 6042-help@theory.lcs.mit.edu Subject: Re: PS8, problem 3 In-Reply-To: Your message of "Mon, 13 Apr 1998 22:46:05 EDT." <3.0.32.19980413224605.008c0150@po7.mit.edu> Date: Mon, 13 Apr 1998 22:59:45 EDT From: Wendy S Chien > Hi! > In problem 3 on the problem set, are we required to find a closed form for > the ogf? > e.g., for (a) can we just say: > <1,1,1,1,1,...> <--> 1+x+x^2+x^3+... > or do we need to say 1/(1-x) ? > Thanks, > Eugene Hi Eugene, You should find the closed form solution. Wendy From jjkim@MIT.EDU Mon Apr 13 21:39:52 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA26630; Tue, 14 Apr 98 01:40:30 EDT Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA00559; Tue, 14 Apr 98 01:39:15 EDT Received: from JARSOFCLAY.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA22484; Tue, 14 Apr 98 01:39:04 EDT Message-Id: <2.2.32.19980414053952.00674df0@po7.mit.edu> X-Sender: jjkim@po7.mit.edu X-Mailer: Windows Eudora Pro Version 2.2 (32) Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Tue, 14 Apr 1998 01:39:52 -0400 To: 6042-help@theory.lcs.mit.edu From: Janice Kim Subject: Pset8, prob 6 hello.... I was wondering, for this problem, are we supposed to take a, b, c, d, e as having it's own restrictions? or is this problem a combination of restrictions from a..e for example, does each a occur an even number of times AND a multiple of five times AND (c.) AND (d.) AND (e.)? or for (a.) each a occur as even number of times for (b.) each a occurs a multiple of 5 times, but not each a occur as even number of times. ? sorry, if this is confusing... I don't know if I stated my questions correctly... thanks anyway! -janice ------------------------------------------------------- Janice Juyeon Kim 410 Memorial Drive Cambridge, MA 02139 e-mail : jjkim@mit.edu web : http://www.mit.edu/people/jjkim/Welcome.html ------------------------------------------------------- From ecoder@MIT.EDU Tue Apr 14 00:13:46 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA27367; Tue, 14 Apr 98 04:15:58 EDT Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA16060; Tue, 14 Apr 98 04:14:43 EDT Received: from INSANITY.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA27217; Tue, 14 Apr 98 04:14:32 EDT Message-Id: <3.0.32.19980414041345.008cc240@po7.mit.edu> X-Sender: ecoder@po7.mit.edu X-Mailer: Windows Eudora Pro Version 3.0 (32) Date: Tue, 14 Apr 1998 04:13:46 -0400 To: 6042-help@theory.lcs From: Eugene Vaynshteyn Subject: PS8 questions Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Hi, If someone could reply before lecture tomorrow (Tues) about these questions, I would really appreciate it: Problem 3: I did parts a-g just fine, but I don't know how to generalize h, or even how to approach i-l. Mainly, I think I'm having problems going from the generating function to the actual sequence it represents, as we have to do in i-l. Problem 5: I solved it, but I don't know how to use induction on it. Once again, this is because I don't know how to go from the gen. function to the sequence... Problem 6: No idea. What is it saying? Did we cover this stuff? Thanks a lot, Eugene From mroh@MIT.EDU Tue Apr 14 06:52:01 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA00404; Tue, 14 Apr 98 10:52:57 EDT Received: from EXODUS.MIT.EDU by MIT.EDU with SMTP id AA14015; Tue, 14 Apr 98 10:52:25 EDT From: mroh@MIT.EDU Received: by exodus.MIT.EDU (8.6.10/4.7) id KAA27394; Tue, 14 Apr 1998 10:52:01 -0400 Message-Id: <199804141452.KAA27394@exodus.MIT.EDU> To: Janice Kim Cc: 6042-help@theory.lcs Subject: Re: Pset8, prob 6 In-Reply-To: Your message of "Tue, 14 Apr 1998 01:39:52 EDT." <2.2.32.19980414053952.00674df0@po7.mit.edu> Date: Tue, 14 Apr 1998 10:52:01 EDT Janice, you should treat each part of problem 6 independently. For example, valid values for a_k in part a are 0,2,4,6,8... Valid values for a_k in part b are 0,5,10,15,20,... The only valid value for a_1 in part c is 0, etc. Mark ----------- Mark Roh, mroh@mit.edu (617) 497-4876 From ssadoway@MIT.EDU Sat Apr 25 13:49:21 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA02184; Sat, 25 Apr 98 17:51:18 EDT Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA14865; Sat, 25 Apr 98 17:50:03 EDT Received: from SILENT-BOB.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA20415; Sat, 25 Apr 98 17:49:44 EDT Message-Id: <3.0.2.32.19980425174921.00826350@hesiod> X-Sender: ssadoway@hesiod X-Mailer: QUALCOMM Windows Eudora Pro Version 3.0.2 (32) Date: Sat, 25 Apr 1998 17:49:21 -0400 To: 6042-help@theory.lcs.mit.edu From: Steve *Silent Bob* Sadoway Subject: Recitation notes, please! Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Hi, I'm trying to work on the problem set, but the notes from yesterday's tutorial aren't up on the web yet... Could somebody post them? Please? :) I don't know whose job it is to update the web page... sorry if I'm emailing this list in error. Thanks! -->Steve ~~~~~~~~~~~~~~~~~~~~~~~~~Steven Sadoway~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ E-mail: ssadoway@mit.edu | Homepage: http://web.mit.edu/ssadoway/www/ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ "We were talking 'bout something, seems like was funny, then Steven got quiet - I think Steven was mad. Maybe he wasn't mad, but we felt very strange, in the moment, but the moment was passed and forgotten about." --Ben Folds Five, "Steven's Last Night In Town" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ From luca@theory.lcs.mit.edu Sat Apr 25 14:14:43 1998 Return-Path: Received: from ostrich (ostrich.lcs.mit.edu) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA02286; Sat, 25 Apr 98 18:16:35 EDT Sender: luca@theory.lcs.mit.edu Message-Id: <35426053.2781E494@theory.lcs.mit.edu> Date: Sat, 25 Apr 1998 18:14:43 -0400 From: Luca Trevisan X-Mailer: Mozilla 3.01Gold (X11; I; SunOS 4.1.4 sun4m) Mime-Version: 1.0 To: Steve *Silent Bob* Sadoway Cc: 6042-help@theory.lcs.mit.edu Subject: Re: Recitation notes, please! References: <3.0.2.32.19980425174921.00826350@hesiod> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Steve *Silent Bob* Sadoway wrote: > > Hi, I'm trying to work on the problem set, but the notes from yesterday's > tutorial aren't up on the web yet... Could somebody post them? Please? > :) I don't know whose job it is to update the web page... sorry if I'm > emailing this list in error. Thanks! > > -->Steve Hi Steve, we normally put handouts online the same day they are distributed, which in this case would have been next monday. given your request, i just posted the tutorial notes now. Best -Luca From brianlin@MIT.EDU Sun Apr 26 17:24:43 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA09363; Sun, 26 Apr 98 21:25:40 EDT Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA12736; Sun, 26 Apr 98 21:24:19 EDT Received: from BRIANLIN.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA00779; Sun, 26 Apr 98 21:24:06 EDT Message-Id: <9804270124.AA00779@MIT.MIT.EDU> X-Sender: brianlin@po8.mit.edu X-Mailer: QUALCOMM Windows Eudora Pro Version 4.0 Demo Date: Sun, 26 Apr 1998 21:24:43 -0400 To: 6042-help@theory.lcs.mit.edu From: Li-Kuo Lin Subject: Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Hi, I have a question concerning #3 on the pset... when it says, maximum 'k', does it mean that all of the 6 #s chosen are <=k, or that one of the 6 #s is k, and the other chosen 5 are less than k? -Brian ---------------------------------------------------------------------------- ------------------ / Li-Kuo (Brian) Lin \ / / 410 Memorial Drive, Apt. 254F \ \ \' , / / / Cambridge MA, 02139 \ \ \ / /, _/ / / , (617)-225-8265 \ _ -/ / ' / / / <, brianlin@mit.edu \ / / / > \ \ \` __/_ /, ) -^>> _\` \ \ \ ( / \ \ / /\ \ / / _/ / \ \ \ \ ( ( ` ( ( "To laugh often and much, to win the respect of intelligent people and the affection of children, to earn the appreciation of honest critics and endure the betrayal of false friends, to appreciate beauty, to find the best in others, to leave the world a bit better, whether by a healthy child, a garden patch, or a redeemed social condition; to know even one life has breathed easier because you have lived. This is to have succeeded!" --Ralph Waldo Emerson From meyer@theory.lcs.mit.edu Sun Apr 26 18:24:31 1998 Return-Path: Received: from stork.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA09625; Sun, 26 Apr 98 22:25:26 EDT Received: by stork.lcs.mit.edu (5.65c/TOC-1.2C) id AA21968; Sun, 26 Apr 98 22:24:31 EDT Date: Sun, 26 Apr 98 22:24:31 EDT Message-Id: <199804270224.AA21968@stork.lcs.mit.edu> From: "Albert R. Meyer" To: brianlin@MIT.EDU Cc: 6042-help@theory.lcs.mit.edu In-Reply-To: <9804270124.AA00779@MIT.MIT.EDU> (message from Li-Kuo Lin on Sun, 26 Apr 1998 21:24:43 -0400) Subject: Re: Reply-To: 6042-meyer@theory.lcs.mit.edu The maximum of the set of six numbers is defined to be the largest of them, so your second interpretation is the correct one. Regards, A. X-Sender: brianlin@po8.mit.edu X-Mailer: QUALCOMM Windows Eudora Pro Version 4.0 Demo Date: Sun, 26 Apr 1998 21:24:43 -0400 From: Li-Kuo Lin Hi, I have a question concerning #3 on the pset... when it says, maximum 'k', does it mean that all of the 6 #s chosen are <=k, or that one of the 6 #s is k, and the other chosen 5 are less than k? -Brian ---------------------------------------------------------------------------- ------------------ / Li-Kuo (Brian) Lin \ / / 410 Memorial Drive, Apt. 254F \ \ \' , / / / Cambridge MA, 02139 \ \ \ / /, _/ / / , (617)-225-8265 \ _ -/ / ' / / / <, brianlin@mit.edu \ / / / > \ \ \` __/_ /, ) -^>> _\` \ \ \ ( / \ \ / /\ \ / / _/ / \ \ \ \ ( ( ` ( ( "To laugh often and much, to win the respect of intelligent people and the affection of children, to earn the appreciation of honest critics and endure the betrayal of false friends, to appreciate beauty, to find the best in others, to leave the world a bit better, whether by a healthy child, a garden patch, or a redeemed social condition; to know even one life has breathed easier because you have lived. This is to have succeeded!" --Ralph Waldo Emerson From flattop@MIT.EDU Sun Apr 26 18:42:59 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA09796; Sun, 26 Apr 98 22:44:23 EDT Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA16331; Sun, 26 Apr 98 22:43:08 EDT Received: from W20-575-16.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA06351; Sun, 26 Apr 98 22:42:49 EDT Sender: flattop@MIT.EDU Message-Id: <3543F0B3.44C7@MIT.EDU> Date: Sun, 26 Apr 1998 22:42:59 -0400 From: "Jack V. Chung" X-Mailer: Mozilla 3.01 (X11; U; SunOS 5.5.1 sun4m) Mime-Version: 1.0 To: Li-Kuo Lin Cc: 6042-help@theory.lcs.mit.edu Subject: Re: PS9 #3 References: <9804270124.AA00779@MIT.MIT.EDU> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Hey, Let me try to explain the problem again. You pick 6 numbers of the 45. All 6 of these numbers are different and less then 45. So k is the maximum of the 6 numbers chosen. Hope this is useful. jack Li-Kuo Lin wrote: > > Hi, > > I have a question concerning #3 on the pset... > when it says, maximum 'k', does it mean that all of the 6 #s chosen are > <=k, or that one of the 6 #s is k, and the > other chosen 5 are less than k? > > -Brian From joycelin@MIT.EDU Sun Apr 26 20:48:07 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA10875; Mon, 27 Apr 98 00:46:42 EDT Received: from MIT.MIT.EDU by MIT.EDU with SMTP id AA02842; Mon, 27 Apr 98 00:45:27 EDT Received: from HUNK-OF-JUNK.MIT.EDU by MIT.MIT.EDU (5.61/4.7) id AA14561; Mon, 27 Apr 98 00:45:08 EDT Message-Id: <2.2.32.19980427044807.006fdb80@po9.mit.edu> X-Sender: joycelin@po9.mit.edu X-Mailer: Windows Eudora Pro Version 2.2 (32) Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Mon, 27 Apr 1998 00:48:07 -0400 To: 6042-help@theory.lcs.mit.edu From: Joyce Lin Subject: Hi, I have a question regarding #4....can the following scenario exist in the problem? Could the probability of a component failing be dependent on the success of other components? If the are, take this scenario: The probability that a component fails given that a component succeeds is equal to 1. Therefore, the probability of the system failing becomes 1, which is above the upper bound of 1/10 ..and we can't prove that 1/10 is an upper bound because of this counterexample. From cynic@mit.edu Sun Apr 26 21:01:44 1998 Return-Path: Received: from SCHOPENHAUER.MIT.EDU by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA10929; Mon, 27 Apr 98 01:03:11 EDT Received: (from cynic@localhost) by SCHOPENHAUER.MIT.EDU (8.8.5/8.8.5) id BAA01221; Mon, 27 Apr 1998 01:01:44 -0400 From: Wesley S Chao Message-Id: <199804270501.BAA01221@SCHOPENHAUER.MIT.EDU> To: Joyce Lin Cc: 6042-help@theory.lcs.mit.edu Subject: Re: In-Reply-To: Your message of "Mon, 27 Apr 1998 00:48:07 EDT." <2.2.32.19980427044807.006fdb80@po9.mit.edu> Date: Mon, 27 Apr 1998 01:01:44 EDT > I have a question regarding #4....can the following scenario exist in >the problem? >Could the probability of a component failing be dependent on the success >of other components? If the are, take this scenario: Yes, this scenario can indeed exist, in a way. However, the counterexample you provide is not valid, and here's why: >The probability that a component fails given that a component succeeds is >equal to 1. Therefore, the probability of the system failing becomes 1, which (This part is a nuance:) Yes, but you don't know that any given component's probability of success is 1, so while the probability of a component failing given that the component it is dependent on succeeds is indeed 1, the probability of that component failing, period, is the probability of the other component succeeding, which is no less than 1- 1/10000. So what, you say, 9999/10000 is still a lot bigger than our supposed upper bound of 1/10. Well, I did say it was a nuance. The real reason why the counterexample is invalid is because it states in the problem that each component is known to fail with probability AT MOST 1/10000. Thus, if a component fails every time another component succeeds, it fails with probability at least 1-1/10000, which violates the above condition. The reason I say a component's probability of failure can depend on another component's probability of success (in a way) is that the component's probability of failure can be affected by the probability of the other component's probability of failure, which is just the opposite of success. :) Hope this helps..if you have any more difficulty with problem 4, feel free to ask the help line some more. From kylee@mit.edu Sun Apr 26 22:37:27 1998 Return-Path: Received: from Dragon-Cliff.mit.edu (CLIFF.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA11241; Mon, 27 Apr 98 02:38:50 EDT Received: (from kylee@localhost) by Dragon-Cliff.mit.edu (8.8.5/8.8.5) id CAA22668; Mon, 27 Apr 1998 02:37:27 -0400 Date: Mon, 27 Apr 1998 02:37:27 -0400 Message-Id: <199804270637.CAA22668@Dragon-Cliff.mit.edu> From: Edmond Kayi Lee To: Joyce Lin Cc: 6042-help@theory.lcs.mit.edu Subject: Re: In-Reply-To: Your message of "Mon, 27 Apr 1998 00:48:07 EDT." <2.2.32.19980427044807.006fdb80@po9.mit.edu> Hi Joyce, Your scenerio does not satisfy the condition given in the question. Let A_i be the event that component i does not fail. We denote ~A_i to be "Not A_i". So we have P(~A_i)<=1/1000. Without loss of generality assume your scenerio says P(~A_1|A_2)=1. P(~A_1) = P(~A_1|A_2)P(A_2)+P(~A_1|A_3)P(A_3)+many other terms >= P(~A_1|A_2)P(A_2) >= 1*999/1000 This does not satisfy our condition. So your scenerio does not really make a contradiction. Edmond From wchien@MIT.EDU Tue May 19 14:17:46 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA05207; Tue, 19 May 98 18:17:50 EDT Received: from SCRUBBING-BUBBLES.MIT.EDU by MIT.EDU with SMTP id AA26451; Tue, 19 May 98 18:17:42 EDT Received: by scrubbing-bubbles.MIT.EDU (8.8.7/4.7) id SAA19899; Tue, 19 May 1998 18:17:47 -0400 (EDT) Message-Id: <199805192217.SAA19899@scrubbing-bubbles.MIT.EDU> To: 6042-help@theory.lcs.mit.edu Subject: help line hours Date: Tue, 19 May 1998 18:17:46 EDT From: Wendy S Chien I am sorry, but it looks like I won't have time to man the help line for a specific block of time. I will try to log in every now and then though on Thursday to check for any questions. Wendy From 851977@uCCTJq.com Sat Aug 15 14:13:34 1998 Return-Path: <851977@uCCTJq.com> Received: from paknet2.ptc.pk ([194.74.28.2]) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA00897; Sat, 15 Aug 98 10:17:18 EDT Received: from ns1 by paknet2.ptc.pk (SMI-8.6/SMI-SVR4) id TAA23406; Sat, 15 Aug 1998 19:13:34 -0500 Date: Sat, 15 Aug 1998 19:13:34 -0500 From: 851977@uCCTJq.com Message-Id: <199808160013.TAA23406@paknet2.ptc.pk> To: 6042-help@theory.lcs.mit.edu Subject: High Performance Hosting Now when you sign up for web hosting with Virtual Hosters Web Site Hosting you get free site submission to over 620 search engines.* Virtual Hosters provides high speed virtual web site hosting services starting as low as $20.00 per month including the following: - 99.9% Guaranteed Uptime - Multiple T-3 Internet backbone connections - Microsoft Front Page Server extensions - Complete user configurable secure shopping cart - coming 09-01-98 - Support for Active Server Pages & Microsoft Visual InterDev - Free site submission to over 620 search engines* - Comprehensive monthly web site statistics - Choice of primary server country - 24/7 Network Operations Support - 5 inbound e-mail boxes with e-mail forwarding & autoresponders - FTP access with username and password - Microsoft Access 97 - Microsoft SQL Server 6.5 - Microsoft Index Server - Microsoft Transaction Server - Microsoft Distributed Transaction Coordinator - User discussion forum - CGI program support - PERL program support - Complete daily backups - One DNS mapping for your domain name - Access to raw history files - ISAPI support - 20 MB of disk storage - Free SSL Certificate - coming soon - CyberCash - coming soon (extra charges may apply) - Volcano Chat - coming soon - True Speech - coming soon (extra charges may apply) - Real Audio & Streaming Video - coming soon (extra charges will apply) This is a limited time offer so call Virtual Hosters U.S. sales office at (970) 349-0796 (24 Hours) and sign up today! Thank you. * Some special terms apply for free site submission