From: "Alexander M. S. Duran" To: meyer@theory.lcs.mit.edu Cc: stasio@theory.lcs.mit.edu, etara@mit.edu, kylee@mit.edu Subject: 6.042 Final Date: Wed, 20 May 1998 16:29:43 EDT I've looked at the problems, here's my opinion: All comments subject to TA's being able to do problems succesfully. I might have thought a problem was fine but somehow messed up. Problem 1, fine. Maybe one or two of the true false are suboptimal, but that's probably just me. Pay attention to how Al and Mark do. Problem 2, problems are fine as T/F, but asking people to sketch a proof is very poor. I would remove this problem and shunt them over to the straight T/F section. Problem 3, ok, but somewhat poor. We really didn't deal with double term divide and conquer recurrences. Problem 4, Fine. Problem 5, (a), Fine, but useless without b. (b) Poor. I don't remember how we told them that the multinomial coefficient was to be interpreted. Since I've always viewed it as picking sets in order, the proof to (b) seems unecessary. I worry that people will have different interpretations of the multinomial and thus will have wildly differing views on what is an acceptable proof. Problem 6, Fine, I think. Problem 7, Fine. Problem 8, Fine. Problem 9, 10, 11, 12. 9 is passable, I really don't like 10. 11 and 12 are both fine. Problem 13, Fine. Problem 14, Fine (we presented this solution (b) in recitation. See if people were paying attention :) ) Problem 15, Fine. Problem 16, Fine. Problem 17, I got bogged down somewhere with my math in c, but I really have never used chebyshev's bound, so someone with more practice might have no problems. But I think problem 16 adequately covers this and that this problem adds very little value. Problem 18, Redundant. I'd prefer to have 15 and 16 and not 17 and 18, personally. So, my suggested test is: 1 + T/F from 2. 3, maybe modified for one term(we have to have DnC in this test) 4 6 7 11 12 13 14 15 16 for a total of 11 problems. Maybe put 9 back in. Also, a student was asking me what he needed on the final to make a D. With an unadjusted quiz score, he needs something like a 90/100 on the final(unadjusted) to pass the class. His quiz score is only about 2 points below the mean. I'd like to give him better news than that. Do we know about any quiz recentering? --Alex amsduran@mit.edu %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% From: stasio@theory.lcs.mit.edu (Stanislaw Jarecki) Date: Wed, 20 May 98 20:00:48 EDT To: amsduran@mit.edu, etara@mit.edu, kylee@mit.edu, meyer@theory.lcs.mit.edu In-Reply-To: "Alexander M. S. Duran"'s message of Wed, 20 May 1998 16:29:43 EDT <199805202029.QAA00894@NW61-431-1.MIT.EDU> Subject: 6.042 Final From: "Alexander M. S. Duran" Date: Wed, 20 May 1998 16:29:43 EDT I've looked at the problems, here's my opinion: All comments subject to TA's being able to do problems succesfully. I might have thought a problem was fine but somehow messed up. Problem 1, fine. Maybe one or two of the true false are suboptimal, but that's probably just me. Pay attention to how Al and Mark do. some of them are difficul! 1&2 made me think for a long time, and i got 1 wrong 8 (the decimal representation of \pi: is quite tricky, to prove it, i know you dont have to prove things, but how else can they convince themselves...) 9 and 10 : i'm not sure these are fair. have they seen a construction for 9 (line/plane) ? also, for 10 you need to know that natural numbers is a smallest infinite set, and this is somewhat tricky... Problem 2, problems are fine as T/F, but asking people to sketch a proof is very poor. I would remove this problem and shunt them over to the straight T/F section. i think the proof sketch is ok, especially in (c) it will be easy to grade. part (a) will be messier... maybe we could skip that? (the test is so long anyway, and what is (a) really testing anyway?) Problem 3, ok, but somewhat poor. We really didn't deal with double term divide and conquer recurrences. This is difficult! i dont have any books or old notes on me and i cant think of how to solve this at all. Problem 4, Fine. except: in (b), we should tell them not to really compute it, just leave it as a complicated numerical expression. i.e. "dont simplify" we should say. also, the points dont add up: 10+5+8+5 > 25 Problem 5, (a), Fine, but useless without b. (b) Poor. I don't remember how we told them that the multinomial coefficient was to be interpreted. Since I've always viewed it as picking sets in order, the proof to (b) seems unecessary. I worry that people will have different interpretations of the multinomial and thus will have wildly differing views on what is an acceptable proof. i had no idea what to do here, exactly because we didnt have any interpretation of multinomial except of subset picking! so there is nothing for them to say there... (is that what you wanted to test: but it will be hard to see from the answer whether they understand anything at all, or they think it's trivial) Problem 6, Fine, I think. by counting? (you'd have to compute these cases: all 4 adjacent, 3 adjacent, 2 pairs adjacent, only one pair adjacent) it's a little messy maybe... (is there some better way to do it?) Problem 7, Fine. yes, but it doesnt have a score. isuggest (10) Problem 8, Fine. yep Problem 9, 10, 11, 12. 9 is passable, I really don't like 10. 11 and 12 are both fine. in 9(a): do you mean : "he will pull *exactly* n_r reds and n_w whites?" we'd better write that down 10 is really messy for an exam question, i agree with alex 11 and 12 are nice together! Problem 13, Fine. 13 : it's ok, but just how far we want them to go: like should they say how many times they should run this? i guess they can't, because they dont have any numbers use... so what are we going to do when they say: "repeat it and then the answer like this: " (note that we ask them to explain how to do it, but we not do ask them to justify why it will work. we should ask them that!) Problem 14, Fine (we presented this solution (b) in recitation. See if people were paying attention :) ) It is straight from the recitation. For part (b), if you dont remember an example from the recitation, it probably takes a long time to get an exapmle yourself! (so i'm not sure it makes sense to test them on that) Problem 15, Fine. good, but i'm not sure it is worth 20 points: probably 14 only... (to come up with teh example for 14b takes more time than this) Problem 16, Fine. (points are not assigned for parts a,b,c,d) part c is very easy, right? part d: why should they remember this equation for e? let's get rid of part d also, the probabilities are somewhat large! Problem 17, I got bogged down somewhere with my math in c, but I really have never used chebyshev's bound, so someone with more practice might have no problems. But I think problem 16 adequately covers this and that this problem adds very little value. we shouldnt do this: it's very verbose and it's too much for the test. they dont have the nerves to go through stuff like that on a final. i recommend against it strongly, Problem 18, Redundant. I'd prefer to have 15 and 16 and not 17 and 18, personally. I like this problem: it's funny and it's just the right format: a little thinking, but then using the bounding formulas. in this way it is better than 15. Problem 16 is different: you dont use the bounds there. 16 is good because at least we have one trivial problem from probability. So, my suggested test is: 1 + T/F from 2. 3, maybe modified for one term(we have to have DnC in this test) 4 6 7 11 12 13 14 15 16 for a total of 11 problems. Maybe put 9 back in. i suggest: 1 2(without a) if you have to have some recurrence, put something much easier than 3, 4 6 (but this is a little too grungy) 7 8 (this is at least easy: let them have it) 11 and 12 13 14 (but only part a) 16 (i'm not sure part d is fair: why should they know this equation for e?) 18 and this is too long already! Stas %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% From: stasio@theory.lcs.mit.edu (Stanislaw Jarecki) Date: Wed, 20 May 98 21:02:53 EDT To: 6042-meyer@theory.lcs.mit.edu In-Reply-To: "Albert R. Meyer"'s message of Wed, 20 May 98 20:50:42 EDT <199805210050.AA07041@stork.lcs.mit.edu> Subject: how did the exam go? it was problem 3. we have 8 students, and they answered all questions (whether right or wrong), and none of them had a clue about how to do problem 3. they all wrote something, but some said this: if T1(n) = T1(3/4 n), the solution is this: if T2(n) = T2(1/5 n), the solution is this, and they sum it up somebody else expanded, wrongly, and got senseless answer, few others just wrote: it's this: ...., without much explaining, two of them used the master theorem, wrongly so this does not look well... as for problem 8: i just checked: they all did the recurrence relation, the characteristic equation, and got some Ax^{n1} + Bx^{n2} expression, some of them wrong one (some because they got the probability equation wrong) so problem 8 is ok. And the fact that all these students made pretty good progress on problem 8 and none in problem 3 really is meaningful, isn't it? stas %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Date: Wed, 20 May 1998 22:05:47 -0400 From: "Albert R. Meyer" To: stasio@theory.lcs.mit.edu In-reply-to: <199805210102.AA02770@sandpiper.lcs.mit.edu> (stasio@theory.lcs.mit.edu) Subject: Re: how did the exam go? reply-to: 6042-meyer And the fact that all these students made pretty good progress on problem 8 and none in problem 3 really is meaningful, isn't it? Yes. I thought there were two easy ways to do Prob 8: plug-and-chug or guess linear and prove it by induction. Just tried plug-and-chug and it is hard to perceive and explain the expansion pattern, so only the guess linear way is realy feasible on an exam. So a hint to approach it that way is necessary; then I think the problem is easy. Regards, A. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% X-Mailer: exmh version 2.0.2 2/24/98 To: 6042-meyer@theory.lcs.mit.edu Cc: kylee@mit.edu, etara@mit.edu, stasio@mit.edu, amsduran@mit.edu Date: Wed, 20 May 1998 22:08:13 EDT From: Edmond Kayi Lee I have looked through the exam and here are my comments: 1: Fine. But is question 6 seems quite obvious since the two clauses are kind of contradictory. Is that your original intention? For the second last question, it may be better to say "that require at least n-colors", though I don't think there is much confusion with that. 2: The questions are good. But I can imagine students looking for all cases to prove part a), and it will be difficult for us to look for any missing cases. It may be better to make it a false question, or make the number of vertices large enough so as to make it impossible to use brute force case analysis. 3: Yes, we haven't dealt with 2-term recurrence in problem sets or recitations. Better change that or give them the close form and ask them to prove it by induction. 4: Good. I like this question. 5: I agree with Alex's comment in 5b). Students are likely to give some imperfect but sort-of-OK answers. 6, 7: 6 and 7 are good. 8: very standard question 9: Fine. 10: Fine, I would suggest giving more points to part e (maybe take away 1-2 points from part d). Also, a typo between part a and part b (the vspace2in). In part b, do we expect them to mention every sample point has probability >=0? 11: Seems ok. 12: Asking them to justify the reasoning is a bit vague if we expect them to write down Wald's Theorem. It would be better to ask them explicitly state the theorem they are using. 13: I don't know what I should write to be a satisfactory answer. It will be better to come with numbers, and what probability is considered to be reliable. (For example, ask them to devise a test which gives a provably upper bound of probability of 3/4. But it would be too long for them.) 14: Fine. 15: Part b), to be more specific, ask them to give a tighter upper bound rather than simply to ask "what fraction ...". 16: Part d), is that a Chernoff bound question? My worry is that student might be able to get a different answer through different method or different transformation. 17: 17 is too much to read. 18: Part b), do you mean 500 flies? Others should be fine. Edmond %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% FROM LUCA: among others, problems 5,10, and 14.b are very good. in problem 4, the sum of the points is not 25. perhaps problem 4.c is worth 5 points. problem 13 (polluted water problem). the text should specify that the events corresponding to errors in repeated executions of the test are mutually independent. btw this is somewhat irrealistic. perhaps the idea is that students have to figure out by themselves the issue of independence and discuss it in their answer?