CSC 344
Homework 3

Assigned Mar. 24, due Apr. 2

Problems from the textbook

• Chap. 4, problem 5 (placing cell phone towers), 1 point.
• Chap. 4, problem 6 (scheduling triathlon competitors), 3 points.
• Chap. 5, problem 1 (finding median of 2n values from two sorted databases), 2 points.
• Chap. 5, problem 5 (which of a bunch of lines are "visible" from above?), 3 points.

Weighed in the Balance

A balance scale is a device with two pans, on each of which you can put heavy objects. It tells you whether the stuff in the left pan is lighter, heavier, or the same weight as the stuff in the right pan. The most common way to use one is to put an unknown object on the right pan, then add one or more pre-calibrated weights to the left pan until they balance, at which point you can tell what the unknown object weighs by adding up the calibrated weights.

Suppose you're given a bunch of objects that each weigh an integer number of ounces, and you need to find out how much each one weighs. Before you start, you are allowed to choose n calibrated weights: for example, if n were 2, you might choose to have a 1-ounce weight and a 3-ounce weight. What weights of unknown objects could you handle with these?

Given the number n, how would you choose calibrated weights so as to be able to handle every possible integer number of ounces 1, 2, 3, ... W where W is as large as possible?
Hint: Solve this problem first for the situation in which you can only put calibrated weights on the left pan; then solve it for the situation in which you can put calibrated weights on either or both pans.

Making change

Consider the problem of making change using pennies, nickels, dimes, and quarters (i.e. coin values 1, 5, 10, 25).

1. Give a greedy algorithm (in pseudocode) which, for any specified number of cents, makes that amount of change with as few coins as possible. (1 point)

2. The aforementioned greedy algorithm works fine in the U.S, but it doesn't necessarily work with other coin values. Give an example of a set of coin values for which the aforementioned greedy algorithm does not choose the fewest possible coins. (1 point)

3. Extra credit: What properties of a set of coin values would guarantee that the greedy algorithm works? (2 more points)

Fast exponentiation

Write and analyze an algorithm which, given two numbers a and n, computes aⁿ. You may assume that n is a non-negative integer. A brute-force approach to this takes O(n) time; give me a significantly more efficient solution. (2 points)

Pegs and holes

You are given a board with n holes of various sizes drilled in it, and n bolts to be inserted into them. You are guaranteed that there is a bolt exactly matching the size of each hole, but none of the bolts or holes are labelled, and you don't have a measuring device, nor any way to compare two holes or two pegs together. The only thing you can do is try a peg in a hole to learn whether it's too large, too small, or just right.

Give an algorithm to match each bolt to the appropriate hole, in time O(n log(n)). (3 points)

Chip testing

An electronic chip is designed in such a manner that any two chips can be connected to test one another; each chip reports whether the other one is good or bad. A good chip always reports correctly whether the other chip is good or bad, but a bad chip's report cannot be trusted. Thus there are four possible outcomes:

Chip A says	Chip B says	Conclusion
B is good	A is good	Either both are good, or both are bad
B is good	A is bad	A (and possibly B) is bad
B is bad	A is good	B (and possibly A) is bad
B is bad	A is bad	At least one is bad

1. Suppose more than half of the n chips are good. Describe an algorithm you could use to reduce the problem to one of at most approximately n/2 size, using approximately n/2 tests. (Note: the new problem must still satisfy the assumption that more than half of the chips are good, or it doesn't count as the same problem.)
2. Still assuming that more than half of the n chips are good, describe an algorithm to find exactly which chips are good, using θ(n) tests. (This will require stating and solving a recurrence.)
3. Assume that at least half of the chips are bad. Convince me (i.e. "prove") that under these circumstances, there is no way to tell which ones are good and which are bad. Hint: imagine that the bad chips are all controlled by a single malevolent demon who's trying to lead you to a wrong answer. Describe an algorithm this demon could use to fool you, no matter what algorithm you use.

Programming:

Implement, test, and debug either the coin-changing algorithm or the fast-exponentiation algorithm (from above) in a real programming language.

The part of the program that does the real work should be callable from other parts of the program, e.g. with known test cases or to actually use the results for some other purpose.