CSC 344 Homework 3

Assigned Mar 31, due Apr 14

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.
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 an. 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 saysChip B saysConclusion
B is goodA is goodEither both are good, or both are bad