The square root of a number tends to be either quite simple (e.g. sqrt(9) = 3) or irrational, a non-repeating infinitely long decimal. So most algorithms for computing square roots involve successive approximations: they start with a guess at the right answer, then use it to compute a closer guess, then a still closer guess, etc. until the approximation is "close enough" for the purpose at hand. (The "close enough" criterion usually determines how long the algorithm takes, acting like a size parameter.)
One simple algorithm for computing square roots is binary search. Given a positive number c, you know that the square root is somewhere between 0 and c (technically this is only true if c>1; assume that for now and we'll come back to it later). So pick a guess in the middle of that range, c/2. If (c/2)2 is larger than c, that means your guess was too high, and the actual answer is between 0 and c/2; if smaller, your guess was too low and the actual answer is between c/2 and c. In either case, you now have a range of possible answers only half as large as you had before. Repeat the process until the range is "small enough": for example, if you want an answer correct to two decimal places, repeat until the range is less than 0.01.
Another algorithm, developed by the ancient Babylonians at least 3500 years ago, is as follows. Suppose you want a square of area c. Start with a rectangle of dimensions 1 x c; this has the right area, but it's not square. So take the average of these two dimensions, yielding (1+c)/2, and use this as one dimension to get a "more nearly square" rectangle. If one dimension is (1+c)/2 and the area is c, then the other dimension must be c/((1+c)/2), or 2c/(1+c). This now has the right area, but it's not quite square either, so take the average of these two dimensions.... If you want an answer correct to two decimal places, repeat until your two dimensions are within .01 of one another.
Trace the action of each of these algorithms to find the square root of 5, correct to three decimal places. Then do the same to find the square root of 29, correct to three decimal places. (You may want to write a little program to help with this, but it's not required.)
For each of the two algorithms and each of the two numbers (5 and 29), how many iterations did it take to reach an accuracy of .1? An accuracy of .01? An accuracy of .001?
Four people need to cross a narrow suspension bridge. The bridge is only strong enough for two people to cross at a time. Furthermore, it's really dark and the suspension bridge has some gaps, so nobody's going to cross the bridge without a flashlight. Unfortunately, there's only one flashlight among the group, and the batteries will die in 17 minutes. Some of the people in the group can walk faster than others, and if two people are crossing together, they can only go as fast as the slower of the two. To be precise, the guide can cross the bridge in 1 minute; another person can cross in 2 minutes; another in 5 minutes; and another in 10 minutes. The bridge is too long to throw the flashlight across; it must be carried.
For one point, is it possible to get all four people across the bridge before the batteries die? Who should cross, with whom, in what order?
For two more points, generalize the problem: give an algorithm which, given any number of people and how long each of them takes to cross, and the amount of battery life left, tells whether it's possible to do it in that length of time (and how). Even better, have your algorithm determine the shortest time in which all the people can get across. How efficient is your algorithm?
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. --
which takes in two
non-negative integers in binary (represented as arrays or lists of
booleans) and adds them, producing the result as another array or list
of booleans. (Converting to int and using the built-in
+ operation is cheating.)
For more credit, also provide a way to do multiplication on this binary representation.
In either case, be sure to provide well-chosen test cases with correct answers (preferably written before you write the addition and multiplication algorithms themselves), so it's easy to test the program and tell whether it actually produces the answers it's supposed to produce.