You are given a bunch of floating-point numbers, and you want to find which two of them are closest together. Describe an algorithm (in pseudocode) that solves this problem. Analyze the algorithm: tell how long it will take, as a function of how many numbers there are. You'll get one point for a correct but inefficient algorithm, two for a more efficient 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).
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.
Write an algorithm in pseudocode which takes in two
natural numbers x and b, and produces
the sequence of digits in the base-b representation of
x. You may assume that b is
at least 2 and at most 10.
Your algorithm may use the standard arithmetic operations -- addition,
subtraction, multiplication, division, and remainder -- and a table
containing the characters '0', '1', '2', ... '9', but you may
not assume any built-in conversion routines.
Trace the action of your algorithm as it computes
the base-7 representation of 103 and the base-9 representation of 5280.
Implement, test, and debug your base-conversion algorithm in your favorite programming language -- C, C++, Java, Scheme, Prolog, perl, Pascal, etc.