1. (10 points)

Is the following statement true or false? If true, give a proof. If false, give a counterexample.

Consider
instances of the Stable Matching Problem in which there exists a hospital h and
a student s such that h is ranked first on the preference list of s and s is
ranked first on the preference list of h. Then in **every** stable matching
S for instances that meet this definition, the pair (h, s) belongs to S.

2. (20 points)

Consider
a generalization of the problem that we examined in lecture, where there are *m*
hospitals, each with a certain number of available positions. There are *n*
students graduating in a particular year. Each hospital has a ranking of the
students in order of preference, and each student has a ranking of the
hospitals in order of preference. Assume that there are more students graduating
than there were slots available in the *m* hospitals.

We want to find a way of assigning each student to at most one hospital, in such a way that all available positions in all hospitals were filled. Some students will not be assigned.

We will say that an assignment of students to hospitals is stable if neither of the following instabilities occurs.

·
Instability 1: There are students *s*
and *s*, and a hospital *h*, so that

- *s*
is assigned to *h*, and

- *s*
is assigned to no hospital, and

- *h*
prefers *s* to *s*.

·
Instability 2: There are students *s*
and *s*, and hospitals *h* and *h*, so that

- *s*
is assigned to *h*, and

- *s*
is assigned to *h*, and

- *h*
prefers *s* to *s*, and

- *s*
prefers *h* to *h*.

Basically, we have the Stable Matching Problem, except that hospitals may want more than one resident, and not all students will be assigned.

a. Give an algorithm to find a stable matching. Use pseudocode similar to the book (for example, the Gale-Shapley algorithm on page 6).

b. Prove that the algorithm finds a stable matching.

c. What is the worst-case running time of the algorithm (Big-O)?

3. (15 points)

Take the following list of functions and arrange them in ascending order of growth rate. That is, if function g(n) immediately follows function f(n) in your list, then it should be the case that f(n) is O(g(n)). You do not need to prove the order is correct.

f_{1}(n)
= n^{2.5}

f_{2}(n) = 10^{n}

f_{3}(n)
= n^{2 }log n

f_{4}(n)
= 2^{log n }(The logarithm is base 2.)

f_{5}(n)
= n^{4/3}

f_{6}(n)
= n (log n)^{3}

f_{7}(n)
= 2^{4n}

f_{8}(n)
= n log n

f_{9}(n)
= n^{log n}

4. (15 points)

A
binary tree is a rooted tree in which each node has a most two children. Show **by
induction** that in any binary tree the number of nodes with two children is
exactly one less than the number of leaves.

**Note:** Be careful to state what value you are performing
induction on and clearly show the basis step, the inductive hypothesis, the
inductive conclusion, and where the inductive hypothesis is used to prove the
inductive conclusion.

5. (20 points)

Lets
say that you have interviewed a set of closely related people regarding their
ancestors (all of whom are now passed away). The ancestors are A_{1}, A_{2},
, A_{n}. The people you have interviewed provide with two types of
facts:

·
For some i and j, A_{i}
passed away before A_{j} was born

·
For some i and j, A_{i}
and A_{j} lived (at least for a while) at the same time

Owing to fallible memories, these facts may not all be correct. You want to determine if all of the facts can all be true simultaneously.

a. Find an efficient algorithm to determine whether all of these facts can be true at the same time. A description of the algorithm is sufficient. Full pseudocode is unnecessary.

b. What is the worst-case running time of the algorithm if there are n ancestors and m facts?

Hint: If two ancestors, A_{i} and A_{j},
have overlapping life spans, then A_{i} was born before A_{j}
died and vice versa.

6. (20 points)

You
live upon a straight residential street upon which you are trying to provide
wireless internet for every house. Each house must be within 100 m of a
wireless router to access it. Given a list of house locations h_{1}, h_{2},
, h_{n} (distances from the beginning of the street), give an
efficient algorithm for placing router locations such that the fewest possible
routers is used. (They do not need to be at a house location.) Prove that your
algorithm uses as few routers as possible. Give the worst-case running time of
your algorithm.

__ __

Rules:

· Working in pairs is acceptable, but both students must be present when all problems are solved.

· It is not acceptable to search the web for solutions to the problems.

· Solutions are to be turned in online. It is preferable that the solutions are typed (for example, in Word). However, clearly legible written solutions may be scanned.