Quiz 3

Milestones

Rubric

All questions on the quizzes in this course are out of 3 points. When assessing these quizzes, score answers as follows:

• 3 is reserved for excellent responses that that fully explain the answer to the question, show a true understanding of the question being asked, and don’t contain any errors. As a general guideline, we expect no more than 25-30% of answers are likely to receive a 3 on any particular question.
• 2 is awarded for a good response that’s getting at the right idea, but might not explain it fully or might have a few minor errors. 2, indeed, is what the course expects most students are likely to earn. As a general guideline, we expect approximately 50-60% of answers are likely to receive a 2 on any particular question.
• 1 is awarded for an inadequate response that misses the mark, is wholly incorrect, or otherwise fails to answer what the question is asking.
• 0 is given to answers that are exceedingly brief, or blank, and as such are effectively non-responses.

The above rubric should be applied for all questions on the quiz.

If you give a score lower than full credit, please include a brief comment in the “Provide comments specific to this submission” section of the form. You can also re-use comments in the “Apply Previously Used Comments” to save time so that you don’t find yourself typing the same thing over and over!

Grading Responsibilities

Answer Key

Question 1

1. No. Different starting states might lead to different local maxima.
2. Yes. If you always start at the same starting state, and always choose the highest valued neighbor, there’s no randomness in the process. As a result, you will always end up with the same state.
3. No. Even if you start from the same starting state, stochastic hill climbing will choose randomly among neighbors, so different runs of the algorithm may result in different chosen neighbors and different results.

Question 2

The updated version of line 5 will only return if all of the neighbors are worse than the current state. This is a problem if we end up at a flat local maximum, because we’ll end up infinitely going back and forth between states at that flat local maximum. Our function has now entered an infinite loop, and will never terminate as a result.

Question 3

1. -400C1 - 500C2. Note that our cost function is something we’re trying to minimize, rather than maximize, so we invert profit numbers to be negative.
2. 2C1 + 3C2 <= 12; C1 <= 4; C2 <= 10.

Question 4

1. A’s domain is {Wed}
2. B’s domain is {Tue}
3. C’s domain is {Mon}
4. D’s domain is {Mon, Wed}
5. E’s domain is {Tue, Wed}
6. F’s domain is {Wed}
7. G’s domain is {Mon, Tue}