Thought I'd give you a place to talk about preparing for the midterm, ask questions, announce your study group meetings, etc. Use the comments section, as usual.
I'm starting up a new discussion topic, called "Spoilers for practice test." Please use that one for discussing the answers to last year's midterm, and this one for all other midterm-related posts.
It is not the answer for the question, but is just discussion hypothetically. Midterm Exam, 2010, #3 choice (a). We said a matching is stable if no man wants to propose to someone else's wife? Will it depend how we define the Stable Matching problem? Say, by running an algorithm, we got all men a bride, but not every one of them have his first choice, so not every one of them is happy, so there is some man m that wants to propose to the woman engaged with m'. So this way, (a) is false. However, if we say that he can't propose, because he already proposed her, and this would mean that he doesn't want to propose her. Then (a) is true. Am I missing something?
@Lucia, what you've said is true, but not quite the point. (a) is false, because the definition of the stable matching problem says nothing at all about "proposals". Proposals are a feature of the Gale-Shapley solution, but there may be many other solutions that look very different. (Brute force for instance, is a solution without proposals. Not a good solution though.)
Here's a copy of Justin's file with edit permission for everyone. https://docs.google.com/document/d/1s8IxiQN3Ol0LG7O6dS6ySgPiVmgVlapHQYaM17zccA4/edit?hl=en_US
I'm assuming he wanted it to be publicly editable.
So, I think I'm *sort of* squared on most of last year's midterm, but I think problem #3 would have tripped me up; I'm worried about a question like this on the exam...I'm wondering if the prof could give us any little "nuggets of wisdom" to help "guide" us in the right direction to study...as in, should we focus on anything specific? Loaded question...but maybe we'll get him to give something up... =)
Would it be ok to list my answers and explanations to the questions on last year's midterm to discuss??
ReplyDeleteThanks!
-TIM
I'm starting up a new discussion topic, called "Spoilers for practice test." Please use that one for discussing the answers to last year's midterm, and this one for all other midterm-related posts.
ReplyDeleteIt is not the answer for the question, but is just discussion hypothetically. Midterm Exam, 2010, #3 choice (a). We said a matching is stable if no man wants to propose to someone else's wife? Will it depend how we define the Stable Matching problem? Say, by running an algorithm, we got all men a bride, but not every one of them have his first choice, so not every one of them is happy, so there is some man m that wants to propose to the woman engaged with m'. So this way, (a) is false. However, if we say that he can't propose, because he already proposed her, and this would mean that he doesn't want to propose her. Then (a) is true. Am I missing something?
ReplyDelete@Lucia, what you've said is true, but not quite the point. (a) is false, because the definition of the stable matching problem says nothing at all about "proposals". Proposals are a feature of the Gale-Shapley solution, but there may be many other solutions that look very different. (Brute force for instance, is a solution without proposals. Not a good solution though.)
ReplyDeleteReposting this comment from the "Spoilers" thread, where it doesn't belong:
ReplyDeleteJustin said...
I created a google doc so that we all can collaborate our notes, so that we can all have a good review!
https://docs.google.com/document/d/18LGfKfJPtsoqKHSzVKUEOaXbyBX9_GCzGrv06RH0t-A/edit?hl=en_US
October 21, 2011 7:25 PM
Order relation and Equivalence relation? Would you please refer me to the page of the book or to the lecture about it? I cannot find it now. Thanks.
ReplyDeleteFor some reason I cannot edit Justin's file. Is it read only?
ReplyDelete@Lucia
ReplyDeleteFrom my notes order relations were discussed on 9-20 and equivalence relations on 9-27.
Julian
I am noticing that the file is read-only as well, can we get that changed?
ReplyDeleteHi,
ReplyDeleteHere's a copy of Justin's file with edit permission for everyone.
https://docs.google.com/document/d/1s8IxiQN3Ol0LG7O6dS6ySgPiVmgVlapHQYaM17zccA4/edit?hl=en_US
I'm assuming he wanted it to be publicly editable.
So, I think I'm *sort of* squared on most of last year's midterm, but I think problem #3 would have tripped me up; I'm worried about a question like this on the exam...I'm wondering if the prof could give us any little "nuggets of wisdom" to help "guide" us in the right direction to study...as in, should we focus on anything specific? Loaded question...but maybe we'll get him to give something up... =)
ReplyDeleteI am still fighting with #5. I got several solutions, but all of them leave out part of the T, so they are worthless.
ReplyDeleteI'd like some good clean rules for asymptotic analysis regarding sqrts and cube roots with respect to logarithms. :P
ReplyDeleteI made a stack overflow question on it . . . http://stackoverflow.com/questions/7882915/asymptotic-complexity-of-logarithms-and-powers