# CSS 549  Algorithm Design and Analysis  Problem set 1

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 , and a hospital h, so that

- s is assigned to h, and

- is assigned to no hospital, and

- h prefers to s.

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

- s is assigned to h, and

- is assigned to , and

- h prefers to s, and

- prefers h to .

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.

f1(n) = n2.5

f2(n) = 10n

f3(n) = n2 log n

f4(n) = 2log n             (The logarithm is base 2.)

f5(n) = n4/3

f6(n) = n (log n)3

f7(n) = 24n

f8(n) = n log n

f9(n) = nlog 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)

Lets say that you have interviewed a set of closely related people regarding their ancestors (all of whom are now passed away). The ancestors are A1, A2, , An. The people you have interviewed provide with two types of facts:

·         For some i and j, Ai passed away before Aj was born

·         For some i and j, Ai and Aj 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, Ai and Aj, have overlapping life spans, then Ai was born before Aj 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 h1, h2, , hn (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.