Write an algorithm in pseudocode which takes in a list
(or array or whatever) of n
numbers, and determines whether or not there is a number
that appears more than once in the list. For example,
dups(3,8,5,1,6) would return false, but
dups(3,8,5,3,6) would return true.
Analyze your algorithm's running time as a function of n. Hint: there's a brute-force way to do it, and a more efficient (but not quite as obvious) way to do it. For full credit, show me the latter.
You are given a list of points in a plane, each specified by an (x,y) coordinate pair, and you want to know whether there is a single circle that they're all on. (Don't worry about "close enough"; you may assume for this problem that your floating-point numbers are infinitely accurate.) Describe an algorithm in pseudocode to solve this problem. Analyze it: tell how long it takes, as a function of the number of points.
Imagine two TV networks, A and B. There are n prime-time programming slots, and each network has n shows. Each network wants to choose a schedule -- an assignment of each show to a distinct slot -- so as to attract as much market share as possible.
Each show has a fixed rating, based on how popular it was last year. We assume, for simplicity, that there are no new shows and no two shows have exactly the same rating. A network wins a given time slot if the show it puts in that time slot has a higher rating than the show the other network puts in that time slot. The goal of each network is to win as many time slots as possible.
Suppose that at the start of the season, Network A reveals its schedule S and Network B reveals its schedule T. This pair of schedules (S,T) determines which network wins which time slots. Network A might decide that it can do better by changing its schedule a week into the season, thus replacing schedule S with schedule S'; unfortunately, Network B might also decide to change its schedule to T', either simultaneously or in response. We call a pair of schedules (S,T) stable if neither network wants to change, i.e. if there is no S' for which (S',T) is better for Network A than (S,T) is, and if there is also no T' for which (S,T') is better for Network B than (S,T) is.
Question: Given the ratings of all n programs on each of the two networks, is there necessarily a stable pair of schedules? If so, give an algorithm that produces such a stable pair; if not, give an example of a set of ratings so that there is no stable pair of schedules (i.e. no matter how they are arranged, one network or the other will always have an incentive to change).
You have a bunch of identical glass jars, and you want to find the maximum height from which they can be dropped without breaking. You have a ladder with n rungs, and your job is to find the highest safe rung.
One approach would be binary search: start halfway up the ladder, drop a jar, see if it breaks, and recursively search the top half or the bottom half of the ladder, taking log(n) drops. But you could go through a lot of jars in the process. (How many?)
On the other hand, you could do it with only one jar if you started at the bottom rung, then moved up one rung, then another, until the jar breaks. But this takes n drops, which is a lot more than log(n).
We seem to have a trade-off between jars and drops. Let's study this: suppose you have a fixed "budget" of k jars; what is the smallest number of drops necessary to solve the problem. With k=1, as we've seen, it takes n drops in the worst case; with k unlimited, it can be done with log(n) drops.
Find and analyze an algorithm for the k=2 case. You should be able to do it with o(n) jars (i.e. asymptotically less than n).
Find and analyze an algorithm for an arbitrary k. If the function fk(n) represents the number of drops it takes with k jars (for example, f1(n) = n), each fk should be asymptotically smaller than the previous one.
Consider the following two-player game: several distinct positive integers (initially two) are written down on a large sheet of paper. Each player, in alternation, chooses two of the existing numbers and writes down their difference on the sheet, but only if that number is not already written down. Whichever player makes the last legal move wins.
For 1 point, prove that the game will end, i.e. eventually one player or the other won't be able to move.
For 1 more point, tell me which player wins, if they both play optimally. If it depends on what two numbers are written down, tell me how it depends on those numbers, i.e. given the two numbers, how would you decide whether you wanted to move first or second? (And, incidentally, what constitutes "playing optimally"?) If it doesn't depend on what numbers are written down, convince me that it doesn't.
For 1 more point, suppose you had to decide whether to move first or second before the initial numbers were chosen (at random). Would your chances of winning be better if you moved first, if you moved second, or are the chances the same? (It may take a bit of work even to state the problem precisely, since there are infinitely many possible numbers to choose from.)
For 1 more point (even if you didn't do the preceding "random" part of the problem), generalize the problem to any number of players (at least two) and any number of numbers written down initially (at least two).