CSC 344
Homework 2

Assigned 18 March, due 1 April

Pegs and Holes (2 points):

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.

Design and analyze an algorithm to match each bolt to the appropriate hole. A brute-force algorithm takes O(n²) time; try to do significantly better.

Polynomials (3 points)

Write a program, in the programming language of your choice, which does basic operations (display, evaluation, addition, multiplication) on polynomials of one variable.

For example, if we define p(x) = x² + 3x -2 and q(x) = 4x³ - x² -5x + 5, then
p(5) should equal 38,
p(x) + q(x) should equal 4x³ -2x + 3,
and p(x) * q(x) should equal 4x⁵ +11x⁴ -16x³ -8x² +5x -10
Hint: don't spend a lot of your time on I/O formatting or user interface; I'm more interested in correct answers.

Making change (1-8 points):

Consider the problem of making change for a specified amount of money, using as few coins as possible. For example, if you needed to make 37c change, you could do it with three dimes, a nickel, and two pennies (6 coins), or with a quarter, a dime, and two pennies (4 coins); the latter is optimal.

• Write and analyze a greedy algorithm in pseudocode to solve this problem, assuming an infinite supply of pennies, nickels, dimes, and quarters.

• The greedy algorithm most people come up with works fine for the denominations of coins (1, 5, 10, 25) used in the U.S., but it doesn't necessarily work with other coin values. Give an example of a set of coin denominations for which the greedy algorithm does not choose the fewest possible coins.

• (Extra credit) What is special about U.S. coin values that makes the algorithm work correctly? What properties would a set of coin denominations have to have in order for the greedy algorithm to work optimally?

• Assuming your original greedy algorithm didn't work for arbitrary denominations of coins, design and analyze an algorithm in pseudocode that does work for arbitrary denominations of coins. (You may assume that the amount of change is a positive integer number of cents, and that one of the denominations is 1c, so at least there always is a way to make the change.)

Independent sets in a vertex-weighted path (5 points)

This is problem 6.1 from the Kleinberg & Tardos book.

A set of vertices in a graph is called an independent set if no two of the chosen vertices have an edge between them. Obviously, the empty set is always independent, and any single-vertex set is independent, but the more vertices you want in the set, the harder it is to find an independent set.

The general problem of "largest independent set" appears to be computationally intractable (in the sense of having no polynomial-time solution), but the special case of a path is more manageable. A path is a sequence of vertices v₁, v₂, ... v_n, with each vertex connected to the ones immediately before and after it, but to no others. Clearly, if you want to put the largest possible number of vertices into an independent set, a simple greedy algorithm does the job: use the first, skip the second, use the third, skip the fourth, and so on.

A more interesting problem is the weighted independent set problem: each vertex has a value (which let's assume is a positive integer), and you want to find an independent set with the largest possible total value. The above greedy algorithm doesn't work: for example, if the values of the vertices are 1, 5, 1, 5, 1, the greedy algorithm picks the first, third, and fifth vertices for a total value of 3, whereas the optimal solution is to pick the second and fourth for a total value of 10.

1. The failure of that example suggests another approach: compute the total value of all the odd-numbered vertices, and the total value of all the even-numbered vertices, and return whichever set has the larger value. Give an example of a weighted path for which this algorithm doesn't produce an optimal result.

2. Here's a different greedy algorithm: ``heaviest-first''. At each step, pick the largest-value remaining vertex, then remove it and its neighbors (so the result is guaranteed to be independent). Give an example in which this greedy algorithm doesn't produce an optimal result.

3. Design and analyze an algorithm in pseudocode that does produce optimal results, for any vertex-weighted path. (An obvious brute-force algorithm takes time O(n * 2ⁿ); you should be able to do much better than that!)

Programming (3 points)

Implement (in the programming language of your choice) the always-correct algorithm for one of the previous two problems, whichever you prefer.