| Quiz |
Posted
(Thursdays) |
Given in class
(Thursdays) |
| | 20 | Apr |
27 | Apr |
Information about quizzes:
- On the date a quiz is given, a die will be thrown by a student in
the class.
- Books and notes are put away.
- A question very similar to the chosen published question will be written
on the board.
- You have 5 minutes to answer the question.
The questions are intended to be straightforward. If you keep up with
the material in the class, almost no preparation may be necessary.
The Collaboration Policy allows you to
study
in groups for the quizzes, but you are on your own when you take the quiz.
You will fare better on the quiz if you
try working the problems before looking at
the solutions. If you don't understand the question or its answer,
please get help.
The problems below are based on stable matching, as discussed in class.
We have N slots and N students. The slots propose to the students and
the students accept or reject the arrangement.
-
Suppose slot i's first choice is student i. But
student i ranks slot i last. What is the result of
stable matching given this data?
-
Suppose every slot prefers student N as its first choice.
Student N ranks the slots N, N-1, N-2.., 1. How many times is the
arrangement involving Student N broken?
-
Same as previous question, but student N ranks the slots 1, 2, 3, ..., N.
How many times is the arrangement involving Student N broken?
-
For 4 slots and 4 students, show a table of student/slot and slot/student
preferences such that one student's arrangement is broken three times.
[ solution ]
Last modified 22:27:07 CDT 13 April 1999
by Ron K. Cytron