Homework 1
CS 482 - Spring 2007
Due: Friday, Feb 2
Recall this information on homework from the course web page:
- Submitting Homework: To simplify the process of distributing papers
for grading, each homework will consist of 3 parts (A, B, and C). Each
part must be turned in separately. In other words, each of parts A, B,
and C will be placed in separate piles when homework is handed in on Friday.
- Homework Privacy: Normally, graded homework is handed back in a
self-service stack. In other words, your homework grade is not
private. If you prefer more privacy, clearly mark HOLD at the top of
the first page of each piece (A, B, and C) of your homework; I will hold
these papers for pick-up during my office hours.
Some comments and suggestions about homework for this course:
- When you are asked to "give an algorithm", this means
- describe the algorithm using a combination of English and high-level
pseudo-code,
- prove that the algorithm works, and
- analyze that algorithm's running time.
- Typically, the clearest way to explain an algorithm is in English with the use of some notation.
A clear explanation in English followed by some annotated pseudo-code is
also fine. Solutions that consist of a long
piece of pseudo-code with no accompanying explanation tend to be
indecipherable by anyone but the author. We reserve the right to deduct a
significant number of points for solutions that consist only of pseudo-code
with no explanation, even if they turn out to be correct.
- It's in your interest to write up solutions neatly. This makes it easier
to understand what's going on in your solution, and to assign partial credit
in cases where the answer is not completely correct.
- You may find it helpful to look at the problems at the end of each chapter
in the text. The text includes solutions to some end-of-chapter problems. You are welcome to discuss these problems (both those with and
those without solutions) during office hours with any member of the course
staff. If you want to use a result from an end-of-chapter problem as part of
the solution for a homework problem, and no proof of the result is given in
the text, then you must include a proof of the result as part of your
solution.
Part A
- Consider a particular solution for the Stable Marriage Problem with n men
and n women.
- Suppose there is at least one man did not get his top choice and
further suppose that this man has changed his mind: he now finds his
wife to be more compatible than expected. In other words, suppose this
man changes his preference list by moving his wife higher on the list.
Does this change the stability of the marriages? Either prove the
marriages remain stable or give an example to show that they don't.
- What if instead, there is some man who moves his wife lower on his
preference list. Does this change the stability of the marriages? Either
prove the marriages remain stable or give an example to show that they
don't.
- Do Problem 7 in Chapter 1 of the text.
Part B
- Do Problem 3 in Chapter 1 of the text.
- Do Problem 5 in Chapter 2 of the text.
Part C
- Do Problem 4 in Chapter 3 of the text.
- Do Problem 7 in Chapter 3 of the text.