Some of these problems can be done in varying levels of detail. The more work you do, and the more aspects of the problem you explore, the more impressed I'll be and the more credit you'll get.
Here's a silly way to sort a bunch of numbers: generate each of the possible permutations of the numbers, and for each one, test whether it's in order. Analyze this algorithm: tell how long it takes, as a function of how many numbers there are, using big-O notation.
A slightly less-silly way to sort: for each number, count how many of the other numbers are less than it, and use this count to put it into the right location in an array. Then read off the array from beginning to end. Analyze this algorithm: tell how long it takes, as a function of how many numbers there are, using big-O notation. Do you see any significant limitations of this algorithm? Can you fix them?
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.
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 a program in your favorite programming
language -- C, C++, Java, Scheme, Prolog, perl, Pascal, etc. --
to manipulate polynomials. A polynomial is
(usually) represented as a list of coefficients: for example, the list
3, -4, 2 could represent the polynomial
3x2 -4x + 2
You need to write the following functions/methods:
toString method, in Java)For each function/method, be sure to provide well-chosen test cases with correct answers (preferably written before you write the function/method itself), so it's easy to test the program.
I'm not really interested in your ability to write I/O and driver code, so I recommend doing this problem in a system that allows you to call functions directly and interactively, such as BlueJ, SWI-Prolog, or DrScheme.