Note: Please include your Cornell NetID on your each section of your homework. This simplifies the process of recording your grades.
Another Note: Our first prelim takes place on Thursday, Feb 24, at 7:30pm.
Suppose you're consulting for a bank that's concerned about fraud detection, and they come to you with the following problem. They have a collection of n bank-cards that they've confiscated, suspecting them of being used in fraud. Each bank-card is a small plastic object, containing a magnetic stripe with some encrypted data, and it corresponds to a unique account in the bank. Each account can have many bank-cards corresponding to it, and we'll say that two bank-cards are equivalent if they correspond to the same account.
It's very difficult to read the account number off a bank-card directly, but the bank has a high-tech "equivalence tester" that takes two bank-cards and, after performing some computations, determines whether they are equivalent.
Their question is the following: among the collection of n cards, is there a set of more than n/2 of them that are all equivalent to one another? Assume that the only feasible operations you can do with the cards are to pick two of them and plug them in to the equivalence tester. Show how to decide the answer to their question with only O(n log n) invocations of the equivalence tester.
As a solved exercise in Chapter 5, we gave an algorithm with O(n log n) running time for the following problem. We're looking at the price of a given stock over n consecutive days, numbered i = 1, 2,..., n. For each day i, we have a price p(i) per share for the stock on that day. (We'll assume for simplicity that the price was fixed during each day.) We'd like to know: how should we choose a day i on which to buy the stock and a later day j > i on which to sell it, if we want to maximize the profit per share, p(j) - p(i)? (If there is no way to make money during the n days, we should conclude this instead.)
In the solved exercise, we showed how to find the optimal pair of days i and j in time O(n log n). But in fact it's possible to do better than this. Show how to find the optimal numbers i and j in time O(n).
Suppose it's nearing the end of the semester and you're taking n courses, each with a final project that still has to be done. Each project will be graded on the following scale: it will be assigned an integer number on a scale of 1 to g > 1, higher numbers being better grades. Your goal, of course, is to maximize your average grade on the n projects.
Now, you have a total of H > n hours in which to work on the n projects cumulatively, and you want to decide how to divide up this time. For simplicity, assume H is a positive integer, and you'll spend an integer number of hours on each project. So as to figure out how best to divide up your time, you've come up with a set of functions fi : i = 1, 2,..., n (rough estimates, of course) for each of your n courses; if you spend h < H hours on the project for course i, you'll get a grade of fi(h). (You may assume that the functions fi are non-decreasing: if h < h' then fi(h) < fi(h').)
So the problem is: given these functions fi, decide how many hours to spend on each project (in integer values only) so that your average grade, as computed according to the fi, is as large as possible. In order to be efficient, the running time of your algorithm should be polynomial in n, g, and H; none of these quantities should appear as an exponent in your running time.