CS 6505, Computability and Algorithms
Below are some practice problems for midterm 2. These are meant to
give you extra practice outside of the homeworks, and not as sample
questions for the midterm.
Though they are not included in the course notes, CLRS chapter 34 and Kleinberg
and Tardos chapter 8 also give more background material for those that are
CLRS 34.5-7: The longest-simple-cycle problem is the problem of
determining a simple cycle (no repeated vertices) of maximum length
in a graph. Show that this problem is NP-complete.
Bonnie and Clyde have just robbed a bank.
They have a bag of money and want to divide it up.
For each of the following scenarios, either give a polynomial-time
algorithm, or prove that the problem is NP-complete.
The input in each case is a list of the n items in the bag, along
with the value of each.
a. There are n coins, but only 2 different denominations:
some coins are worth x dollars, and some are worth y dollars.
They wish to divide the money exactly evenly.
b. There are n coins, with an arbitrary number of different
denominations, but each denomination is a nonnegative integer power of 2,
i.e., the possible denominations are 1 dollar, 2 dollars, 4 dollars, etc.
They wish to divide the money exactly evenly.
c. There are n checks, which are, in an amazing coincidence, made out
to "Bonnie or Clyde."
They wish to divide the checks so that they each get the exact same
amount of money.
d. There are n checks as in part (c), but this time they are willing to
accept a split in which the difference is no larger than 100 dollars.
Kleinberg and Tardos Problem 8.3:
Suppose you're helping to organize a summer sports camp, and the
following problem comes up. The camp is supposed to have at least
one counselor who's skilled at each of the n sports covered by the camp
(baseball, volleyball, and so on). They have received job applications from
m potential counselors. For each of the n sports, there is some subset
of the m applicants qualified in that sport. The question is: For a given
number k < m, is it possible to hire at most k of the counselors and have
at least one counselor qualified in each of the n sports? We'll call this the
Efficient Recruiting Problem.
Show that Efficient Recruiting is NP-complete.
Divide and Conquer:
Dasgupta, Papadimitriou, and Vazirani, problems 2.4, 2.5, and 2.28
CLRS Problem 15-6: Moving on a checkerboard
Suppose that you are given an n by n checkerboard and a checker.
You must move the checker from the bottom edge of the board to the top
edge of the board according to the following rule.
At each step you may move the checker to one of three squares:
1. the square immediately above,
2. the square that is one up and one to the left (but only if the
checker is not already in the leftmost column),
3. the square that is one up and one to the right (but only if the checker
is not already in the rightmost column).
Each time you move from square x to square y, you receive p(x,y) dollars.
You are given p(x,y) for all pairs (x,y) for which a move from x to y is legal.
Do not assume that p(x, y) is positive.
Give an algorithm that figures out the set of moves that will move the
checker from somewhere along the bottom edge to somewhere along the top
edge while gathering as many dollars as possible.
Your algorithm is free to pick any square along the bottom edge as a
starting point and any square along the top edge as a destination in order
to maximize the number of dollars gathered along the way.
What is the running time of your algorithm?
There are more practice problems, with solutions, at
this MIT site.
Also, Kleinberg and Tardos, Chapter 6, has many problems and example solutions
that would make excellent exercises.
Problems 6-4, 6-11, 6-12, and 6-20 are fairly short and easy to understand.
It is also highly recommended for its explanations. There is a reserve copy
of Kleinberg and Tardos at the library.
1. Suppose that we have two strings that are very long and cannot be
transmitted to another site.
We want to know if the two strings are exactly the same.
(In a homework problem we asked for an estimate of the relative distance
between two strings, not if they were the same.
This is a different problem.)
Give an algorithm to compare the two strings, give the number of trials
necessary, and give the number of bits transferred.
(Hint: Use polynomial identity testing.)
2. Suppose that you have a blackbox that can test if a number is prime.
Create a randomized algorithm to pick a prime number in the range [x,y].
How many calls can you expect to make to the blackbox?
(The Prime Number Theorem states that, as n approaches infinity,
there are n/ln(n) prime numbers less than n. Assume that this formula
holds for all n.)