Assignment 1

Due Friday, Jan 18

1. Chapter 1, Page 22, Problem 1
Decide whether you think the following statement is true or false. If it is true, give a short explanation. If it is false, give a counterexample.

In every instance of the Stable Matching Problem, there is a stable matching containing a pair (m,w) such that m is ranked first on the preference list of w and w is ranked first on the preference list of m.

2. Chapter 1, Page 22, Problem 2
Decide whether you think the following statement is true or false. If it is true, give a short explanation. If it is false, give a counterexample.

Consider an instance of the Stable Matching Problem in which there exists a man m and a woman w such that m is ranked first on the preference list of w and w is ranked first on the preference list of m. Then in every stable matching S for this instance, the pair (m,w) belongs to S.

3. Chapter 1, Page 22, Problem 4
Consider the following variant of the Stable Matching problem, where instead of matching men and women, we match residents to hospitals. There are m hospitals, each with a certain number of available positions, and n students, each wanting to join a hospital. Each hospital ranks the students, and each student ranks the hospitals. Say there are more students than available slots in the m hospitals. We say an assignment of students to hospitals is stable if neither of the following situations arises:

• First instability: 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.
• Second instability: 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.
  • s' prefers h to h'.

4. Chapter 2, Page 67, Problem 2.
Suppose you have algorithms with the running times listed below. Suppose you have a computer that can perform 10¹⁰ operations per second, and you need to compute the result within at most one hour. For each of the algorithms, what is the largest input size n for which you would be able to get the results within an hour?

1. n²
2. n³
3. 100 n²
4. n log n
5. 2 ⁿ
6. 2^(2^n)

5. Chapter 2, Page 67, Problem 3.
Take the following list of functions and arrange them in ascending order or 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)).

• f₁(n) = n^2.5
• f₂(n) = sqrt(2 n)
• f₃(n) = n + 10
• f₄(n) = 10ⁿ
• f₅(n) = 100ⁿ
• f₆(n) = n² log n

6. Chapter 2, Page 68, Problem 5.
Assume you have functions f and g such that f(n) is O(g(n)) for each of the following statements, decide whether you think it is true or false, and give a proof or counterexample.

1. log₂ f(n) is O(log₂ g(n))
2. 2^f(n) is O(2^g(n))
3. f(n)² is O(g(n)²)

7. Chapter 2, Page 69, Problem 8(a)
You're doing some stress testing on various models of glass jars to determine the height from which they can be dropped and still not break. The setup for this experiment is as follows. You have a ladder with n rungs, and you want to find the highest run from which you can drop a copy of the jar without breaking it. We calll this the highest safe rung.

It might be natural to try binary search: drop the jar from the middle rung, see if it break, then recursively try from n/4 or 3n/4. But this has the drawback that you could break a lot of jars.

If your primary goal were to conserve jars, on the other hand, you could try the following strategy. Start by dropping a jar from the first rung, then the second, third, etc, until the jar breaks. This way you only need one jar. But this way, you may have to drop it n times.

It seems you can perform fewer drops if you're willing to break more jars. To understand how much better you can do, consider how to run this experiment given a fixed budget of k jars. You have to determine the highest safe rung, using at most k jars.

Suppose you are given a budget of k = 2 jars. Describe a strategy that requires you to drop a jar at most f(n) times, for some function f(n) that grows slower than linearly.

Extra Credit

1. Concrete Application (2 points)

In class we've discussed the Travelling Salesman and Stable Matching. We discussed a few examples, but we mostly dealt with the abstract mathematical model of the problem. For extra credit, give additional concrete examples of these problems. This means you must find a real world problem, and explain precisely which parts of the mathematical model correspond to which real world objects. (You can choose either Travelling Salesman or Stable Matching, but you won't get more credit for doing two.)

You may not use any examples from class or the book. For TSP, this means you cannot use travelling salesmen or printed circuit boards. For stable matching, you may not use marriage / dating / etc., students / schools, residents / hospitals, or sporting events.

2. Chapter 2, Page 70, Problem 8(b) Challenge Problem (2 points)