Homework 1

CS 482 - Summer 2007

Due: Thursday, Jul 12

Some comments and suggestions about homework for this course:

  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.