CSC 343
Homework 1

• Exercise 1.6 on sparse arrays: describe the ADT and two different implementations (a few sentences each; no code!)
• Exercise 1.8 on generalizing a sequential-search function (a paragraph or two; no code!)
• Exercise 1.11 on the operations and time constraints in designing a spell checker (a few sentences)
• Exercise 1.20: describe a data structure that supports both insertion and search quickly
• Choose one: either exercise 2.15 (permutations) or 2.16 (subsets). You can write this in pseudocode, but if you're not sure your algorithm is correct, try writing it in real code (whatever language you like) and testing it. It may be easier to think of your function as returning the answer rather than printing it.
• Exercise 2.22 (an induction proof)
• Exercise 2.32 (proving by induction the solution to a recurrence)
• Exericse 2.33 (solving a recurrence & proving the solution correct by induction)
• Choose two of exercises 2.36-2.45 (back-of-the-envelope estimation)

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)² 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 more credit, 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?

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

3x² -4x + 2

You need to write the following functions/methods:

• A way to create a polynomial, given its coefficients (e.g. a constructor, in Java)
• A way to display a polynomial (e.g. a toString method, in Java)
• A way to test whether two polynomials are exactly the same
• A way to evaluate a polynomial by plugging in a particular value for x
• A way to add two polynomials, producing a new polynomial
• A way to multiply two polynomials, producing a new polynomial

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 DrRacket.