Description
1. [50 pts] Definition: A Hamiltonian Path in graph G = (V,E) is a path
<v0,v1,…,vn> s.t. all vertices
of V are on the path, and no vertex appears more than once.
The “Hamiltonian Path Problem” asks if a graph G has a Hamiltonian Path.
Definition: A simple path in graph G = (V,E) is a path <v0,v1,…,vn> s.t. no vertex
vi is repeated.
The “Longest Path Problem” seeks to find a simple path in G that is as long as
it can be.
Show that the Hamiltonian Path Problem reduces to the Longest Path
Problem.
2. [50 pts] The *rod-cutting* problem is the following:
Given a rod of length n inches and a table of prices pi for i = 1, 2 …, determine
the maximum revenue rn obtainable by cutting up the rod and selling the
pieces. Note that if the price pn for a rod of length n is large enough, an
optimal solution may require no cutting at all.
Example
Consider the case when n = 4, with the price (in $) breakdown given below
length i | 1 2 3 4 5 6 7 8 9 10
price pi | 1 5 8 9 10 17 17 20 24 30
One possible way choice is not to cut the rod at all, but to sell it intact for $9.
Another alternative would be to cut it into 4 1 inch pieces for $4. Not as good
as our first option.
a. Give an algorithm that solves the rod cutting problem for any length rod and
price breakdown list.
b. What is the complexity of your algorithm?
c. Show a trace of your algorithm running to solve the initial example shown
above.