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 highlevel
pseudocode,
 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 pseudocode is
also fine. Solutions that consist of a long
piece of pseudocode 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 pseudocode
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 endofchapter 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 endofchapter 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.

 Do Problem 1 in Chapter 1 of the text.
 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 pairup 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 leftover, unpartnered student.
 Do Problem 6 in Chapter 1 of the text.