## 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.