From kylee@MIT.EDU Tue Feb 24 15:12:30 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA17692; Tue, 24 Feb 98 20:13:27 EST Received: from M38-370-2.MIT.EDU by MIT.EDU with SMTP id AA15658; Tue, 24 Feb 98 20:12:30 EST Received: by m38-370-2.MIT.EDU (SMI-8.6/4.7) id UAA03388; Tue, 24 Feb 1998 20:12:30 -0500 Message-Id: <199802250112.UAA03388@m38-370-2.MIT.EDU> To: 6042-sec5@theory.lcs.mit.edu, 6042-sec6@theory.lcs.mit.edu Subject: Mailing list created Date: Tue, 24 Feb 1998 20:12:30 EST From: Edmond Kayi Lee Hi all, This is a mail sent to the mailing list for 6.042 students in section 5 and section 6. If you receive this mail, that means you are in the mailing list. The list names for section 5 and section 6 are 6042-sec5@theory.lcs.mit.edu and 6042-sec6@theory.lcs.mit.edu respectively. Please feel free to send mail to the list for questions, comments concerning the recitation. Also, I will make section announcements via this mailing list. Thanks, Edmond From kylee@MIT.EDU Wed Feb 25 12:23:21 1998 Return-Path: Received: from MIT.EDU (SOUTH-STATION-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA29395; Wed, 25 Feb 98 17:24:19 EST Received: from MINT-SQUARE.MIT.EDU by MIT.EDU with SMTP id AA05294; Wed, 25 Feb 98 17:23:23 EST Received: by mint-square.MIT.EDU (8.8.7/4.7) id RAA18866; Wed, 25 Feb 1998 17:23:22 -0500 (EST) Message-Id: <199802252223.RAA18866@mint-square.MIT.EDU> To: 6042-sec5@theory.lcs.mit.edu, 6042-sec6@theory.lcs.mit.edu Subject: Problem Set 4 question 1 Date: Wed, 25 Feb 1998 17:23:21 EST From: Edmond Kayi Lee Hi, In problem set 4 question 1, it is asking the Robot problem similar to the one given in the lecture. However, pay attention that the robot is moving a distance of 1 unit for each time. Therefore, the solution is not as trivial as it looks. For example, if it goes in the 45 degree direction at the first step, then it will end up in the coordinate (sqrt(2)/2, sqrt(2)/2), instead of (1,1) as in the lecture. To prove "yes", give the path that the robot can reach the point. To prove "no", design and prove an invariant such that the state (1,1) does not satisfy the invariant. Good luck, Edmond From kylee@MIT.EDU Sat Feb 28 18:43:12 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA04607; Sat, 28 Feb 98 23:44:10 EST Received: from W20-575-33.MIT.EDU by MIT.EDU with SMTP id AA02044; Sat, 28 Feb 98 23:43:37 EST Received: by w20-575-33.MIT.EDU (SMI-8.6/4.7) id XAA01289; Sat, 28 Feb 1998 23:43:12 -0500 Message-Id: <199803010443.XAA01289@w20-575-33.MIT.EDU> To: Dmitry Brant Cc: 6042-sec5@theory.lcs.mit.edu, 6042-sec6@theory.lcs.mit.edu Subject: Re: 6.042 ps4 question In-Reply-To: Your message of "Sat, 28 Feb 1998 16:05:24 EST." <199802282105.QAA24010@w20-575-45.MIT.EDU> Date: Sat, 28 Feb 1998 23:43:12 EST From: Edmond Kayi Lee >I have a question about question 4e on the pset. When they say "every stable mar >riage set leaves two bachelors of each sex" do they mean 2 bachelors are women + > 2 bachelors are male? If so, then does the hint suggest the situation when the >marriage >set is empty? is that valid? > Yes, what you said is right. Here it is talking about every stable marriage set has to leave 2 men unmarried, and also 2 women. In the case involving 2 men and 2 women, this reduces to the case where the only stable marriage is "no marriage" at all, which is a stable marriage by definition. Thus, you have to think of a situation (an acceptance list) where there cannot be any non-trivial stable marriage. Hope this helps. -Edmond From kylee@mit.edu Wed Mar 11 12:46:25 1998 Return-Path: Received: from KINGS-COLLEGE.MIT.EDU by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA05215; Wed, 11 Mar 98 17:47:29 EST Received: (from kylee@localhost) by Kings-College.MIT.edu (8.8.5/8.8.5) id RAA29836; Wed, 11 Mar 1998 17:46:25 -0500 Message-Id: <199803112246.RAA29836@Kings-College.MIT.edu> To: 6042-sec5@theory.lcs.mit.edu, 6042-sec6@theory.lcs.mit.edu Subject: Quiz next week Date: Wed, 11 Mar 1998 17:46:25 EST From: Edmond Kayi Lee Hi, Just a reminder that the mid-term quiz is next Wednesday. The questions in the quiz will cover materials up to lecture yesterday. I'll give a brief summary of topics here: - Propositional Logic - Basic proof technique: direct proof, proof by contradiction, proof by cases - (strong) Induction (on mathematical equations, graphs or any other mathematical objects) - Well Ordering Principle - Graph Theory: definition, coloring, isomorphism (you should also be familiar with definition of terms such as tree, path, connected component, cycle/circuit, adjacency matrix, DAG, etc) - State Machines: Design and Proof of Invariants, Derived Variables and Termination. - Sum and series: perturbation method, differentiation method, integration method for closed forms or bounds. Also the "guess" method by solving for the coefficients of speculated closed form and verification by induction. - Asymptotic Notation: Definition of big-O, Theta, big-Omega notation. Comparison between functions. - Divide and Conquer Recurrence: Deriving Recurrence, Plug-and-Chuck(Iteration), Master Theorem Also, you should be able to read definitions of new stuff and do proofs according to the definition. If you find yourself comfortable with all these topics, you are in good shape. If not, be sure to go over it again and ask me about any confusion. Also, the section this Friday will be a bit short. I am expecting to have some time left (hopefully 20-30 minutes) to answer your questions. So if you have any questions about any topics covered so far, be prepared to ask. Last reminder, the topic Divide and Conquer Recurrence is not covered in any problem sets due before the quiz. You may want to do some practice exercise on that. Please look at the practice quiz we are going to give out soon. Sorry for the long message. Wish you all do well next week. Edmond From kylee@mit.edu Fri Mar 13 17:09:32 1998 Return-Path: Received: from KINGS-COLLEGE.MIT.EDU by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA04187; Fri, 13 Mar 98 22:10:36 EST Received: (from kylee@localhost) by Kings-College.MIT.edu (8.8.5/8.8.5) id WAA25439; Fri, 13 Mar 1998 22:09:32 -0500 Message-Id: <199803140309.WAA25439@Kings-College.MIT.edu> To: 6042-sec5@theory.lcs.mit.edu, 6042-sec6@theory.lcs.mit.edu Subject: About Recurrence Date: Fri, 13 Mar 1998 22:09:32 EST From: Edmond Kayi Lee Some of you have asked me about where to get the materials for recurrences, and I would say the first place you should check if the recitation note 6 on the web. It states the Master Theorem, a corollary, some examples and the Change of variable we went over today. There is also a proof of the Theorem for those who are interested. So I guess it contains the basic information that you need to know about the topic. The lecture note last year (lecture 10) is also a good reference for the topic. It talks about how to find and solve a recurrence using plug and chuck, and also verifying it using induction. The Towers of Hanoi example is not mentioned in the lecture, but it is an interesting example for you to learn how to find a recurrence. Note that section 4, the Akra-Bazzi Method is not covered this year. Last but not least, to get yourself familiar with the recurrence problems, you have to practice more. The practice problem set has some questions on recurrence. If you think you need more, I would recommend you to check out old 6.042 webpages before Fall 97. The Divide-and-Conquer recurrence questions in those terms will not include Akra-Bazzi and fit the topic for this year. Work hard and good luck on the exam. Edmond From kylee@mit.edu Mon Mar 16 18:11:35 1998 Return-Path: Received: from KINGS-COLLEGE.MIT.EDU by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA27919; Mon, 16 Mar 98 23:12:41 EST Received: (from kylee@localhost) by Kings-College.MIT.edu (8.8.5/8.8.5) id XAA28542; Mon, 16 Mar 1998 23:11:36 -0500 Message-Id: <199803170411.XAA28542@Kings-College.MIT.edu> To: 6042-sec5@theory.lcs.mit.edu, 6042-sec6@theory.lcs.mit.edu Subject: Problem set 5 graded Date: Mon, 16 Mar 1998 23:11:35 EST From: Edmond Kayi Lee Hi, Problem set 5 is graded. I will bring those and all the unclaimed problem sets to the lecture tomorrow so that you can pick up. For those who still wants to read more about Master Theorem, you can refer to the book Introduction to Algorithms by Borman, Rivest and Leiserson. There are 3 pages (p.61-64) explaining how to understand and use the theorem. This is the book for the course 6.046, so your neighbour may have it. Reminder: office hour tomorrow 4-10 in 24-115. Edmond From kylee@mit.edu Fri Mar 20 12:06:17 1998 Return-Path: Received: from KINGS-COLLEGE.MIT.EDU by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA08564; Fri, 20 Mar 98 17:07:24 EST Received: (from kylee@localhost) by Kings-College.MIT.edu (8.8.5/8.8.5) id RAA04680; Fri, 20 Mar 1998 17:06:17 -0500 Message-Id: <199803202206.RAA04680@Kings-College.MIT.edu> To: 6042-sec5@theory.lcs.mit.edu, 6042-sec6@theory.lcs.mit.edu Subject: Quiz 1 Date: Fri, 20 Mar 1998 17:06:17 EST From: Edmond Kayi Lee Alrite quiz 1 is graded and handed back, and I see a lot of students having trouble in problem 1. I know it's too late for the quiz, but I would like to suggest a general way on how to find the falsity in the proof. This should be something that is useful for you. 1. Agree that the proof is faulty, and find a counterexample (better a simple one). 2. Verify the faulty proof LINE BY LINE with your counterexample. And find the transition of lines where it turns false for your counter- example. Since it is a false proof, there must be such a transition. This is the place where the proof goes wrong. 3. Think about the transition and get a sense of why that is false. Then make a comment and explanation on that. That is all what you should do. It should work for most of the cases, even though I can't guarantee it works for all false proofs. I hope that helps. Have a nice break. Edmond From kylee@mit.edu Thu Mar 26 09:06:08 1998 Return-Path: Received: from Dragon-Cliff.mit.edu (CLIFF.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA15104; Thu, 26 Mar 98 14:07:19 EST Received: (from kylee@localhost) by Dragon-Cliff.mit.edu (8.8.5/8.8.5) id OAA05151; Thu, 26 Mar 1998 14:06:09 -0500 Message-Id: <199803261906.OAA05151@Dragon-Cliff.mit.edu> To: 6042-sec5@theory.lcs.mit.edu, 6042-sec6@theory.lcs.mit.edu Subject: PS6 Problem 1 Date: Thu, 26 Mar 1998 14:06:08 EST From: Edmond Kayi Lee Hi, When you are doing problem 1 in problem set 6, be sure your argument goes rigorously. It is a standard pigeon-hole type question. So if you use pigeon hole principle to prove, be sure to write down what is pigeon, what is hole, and why the pigeon-hole principle can make you prove the desired statement. Maybe some of you will write down something like: "The only way to place 32 checkers is to place them alternatively (or place them in squares with the same color). And if you try to put the 33rd checker, there is no way for you to do that." This is a true assertion and right intuition, but this is NOT a rigorous proof, becuase you haven't proved why all others ways to put the checkers do not work. (If your proof really cover all the possible cases, that's fine. But I am sure you don't want to do this since there are so many possible ways of placing checkers to consider.) In conclusion, I have reminded you not to write down the "intuitive" argument above. You'd better find another way to prove the result rigorously. Edmond From kylee@MIT.EDU Mon May 4 12:10:22 1998 Return-Path: Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA02803; Mon, 04 May 98 16:12:01 EDT Received: from W20-575-4.MIT.EDU by MIT.EDU with SMTP id AA07736; Mon, 4 May 98 16:10:45 EDT Received: by w20-575-4.MIT.EDU (SMI-8.6/4.7) id QAA26228; Mon, 4 May 1998 16:10:22 -0400 Message-Id: <199805042010.QAA26228@w20-575-4.MIT.EDU> To: 6042-sec6@theory.lcs.mit.edu Cc: 6042-sec5@theory.lcs.mit.edu Subject: A bad mistake in recitation Date: Mon, 04 May 1998 16:10:22 EDT From: Edmond Kayi Lee Hi all, In the recitation Friday (Sec 6) I mentioned two Random Variables X,Y are independent iff Ex(X*Y)=Ex(X)*Ex(Y). I checked that at home and I found that this is not true. This is true only for one direction: if X, Y are independent, then Ex(X*Y)=Ex(X)*Ex(Y). But the other direction is not true: even if X,Y depend on each other, Ex(X*Y)=Ex(X)*Ex(Y) MAY still hold. For example, Let (A,B) be (1,1),(1,-1),(-1,2),(-1,-2) each w/prob 1/4. So P(A=1)=P(A=-1)=1/2 P(B = 1) = P(B = -1) = P(B = 2) = P(B = -2) = 1/4 We have E(B)=0, E(A)=0, and E(AB)=0 However, A and B are dependent since P(A=1|B=1)=1 but P(A=1)=1/2. So in conclusion: - independence of random variables is defined as P(A=i and B=j) = P(A=i)P(B=j) for all i,j. To show independence, you show the random variables have the above property. - If A and B are independent, then Ex(AB)=Ex(A)Ex(B), but the converse is not true. I am sorry about the mistake. I made that mistake, so I hope you won't follow me. Edmond From kylee@mit.edu Thu May 14 07:14:23 1998 Return-Path: Received: from Dragon-Cliff.mit.edu (CLIFF.MIT.EDU) by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA14698; Thu, 14 May 98 11:14:27 EDT Received: (from kylee@localhost) by Dragon-Cliff.mit.edu (8.8.5/8.8.5) id LAA03252; Thu, 14 May 1998 11:14:23 -0400 Message-Id: <199805141514.LAA03252@Dragon-Cliff.mit.edu> To: 6042-sec5@theory.lcs.mit.edu, 6042-sec6@theory.lcs.mit.edu Subject: Office Hours Date: Thu, 14 May 1998 11:14:23 EDT From: Edmond Kayi Lee Hi, I am planning to hold office hours this week and next week in order to help you prepare for the final. My tentative time will be 3-5 this Friday, next Monday and Thursday. If you have trouble with any problems or topics, they are the good times for you to make it clear. The place will be 3rd Student Center in Lobdell. (Sorry I don't have an office. Lobdell is a decent place for study in non-meal times though.) If the time doesn't work out for you. You are welcome to schedule another time with me. Have fun studying. Edmond