Homework 1

CS 482 - Summer 2007

Due: Thursday, Jul 12

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 problems from the text (both those with and those without solutions) 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.

1.  
   1. Do Problem 1 in Chapter 1 of the text.
   2. Imagine for a moment that you are a CS instructor instead of a student. Your goal is to form your students into pairs for their final project. During the semester, the students have each formed strong opinions about the other students in the course, so each student has submitted a list to you, ordered by preference, indicating the students with which they would prefer to partner. As the instructor, your goal is to pair-up the students so that, even if some students do not get their favorite partner, each student is unable to find another student willing to ditch their current partner for them (i.e., the goal is to create a stable paring of students). Given the students and their preference lists, is there always a way to assign students to partners so that the assignment is stable? If so, give an algorithm to find such an assignment. If not, give an example of students and preferences such that for any assignment, at least one pair of students prefers each other to their assigned partners. Assume that there are 2n students, so that we don't have to worry about a left-over, unpartnered student.
       
2. Do Problem 6 in Chapter 1 of the text.