There are ten problems, and nine days to do them. I'll grade only some of them; think of the rest as practice exercises.
As you're doing these, think of which one you'd like to present in class, and let me know as soon as you've decided.
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 number c ≥ 1, you know that the square root is somewhere between 1 and c. So pick a guess in the middle of that range, (c+1)/2. If ((c+1)/2)2 is larger than c, your guess was too high, and the actual answer is between 1 and (c+1)/2; if smaller, your guess was too low and the actual answer is between (c+1)/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.
Implement both of these algorithms as programs in the language of your choice (C, C++, Java, Scheme, perl, Prolog, python, ruby, etc.). Each program should take in the number to find the square root of, and a number that tells how close is "close enough", and indicate somehow not only the final answer but what steps it went through to get there. For example, a functional Scheme program might return a list of the successive values that it tried; an imperative Java program might return the answer, but print each successive approximation along the way.
Test your programs on a variety of numbers and a variety of accuracy criteria. What conclusions can you draw about the number of steps?