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

1. Consider a particular solution for the Stable Marriage Problem with n men and n women.
   1. 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.
   2. 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.
       
2. Do Problem 7 in Chapter 1 of the text.

Part B

1. Do Problem 3 in Chapter 1 of the text.
    
2. Do Problem 5 in Chapter 2 of the text.

Part C

1. Do Problem 4 in Chapter 3 of the text.
    
2. Do Problem 7 in Chapter 3 of the text.