Homework 1

- Chapter 1, Exercise 3, about two competing television networks. 3 points.
- Chapter 2, Exercise 1, working with asymptotic growth rates. 1 point.
- Chapter 2, Exercise 2, working with asymptotic growth rates. 1 point.
- Chapter 2, Exercise 3, working with asymptotic growth rates. 1 point.
- Chapter 2, Exercise 4, working with asymptotic growth rates. 1 point.
- Chapter 2, Exercise 6, analyzing and improving an algorithm in pseudocode. 3 points.
- Chapter 2, Exercise 8, developing (in pseudocode) and analyzing a series of algorithms for destructive testing of glass jars. 3 points.

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

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.

Last modified: Tue Feb 10 10:28:38 EST 2009 Stephen Bloch / sbloch@adelphi.edu