Java Reference
In-Depth Information
by using a brute-force algorithm that checks all possible sets of vertices of
size k to find an acceptable vertex cover, and measure the running time on a
number of input graphs. Then try to reduce the running time through the use
of any heuristics you can think of. Next, try to find approximate solutions to
the problem in the sense of finding the smallest set of vertices that forms a
vertex cover.
17.2 Implement KNAPSACK (see Section 16.1). Measure its running time on a
number of inputs. What is the largest practical input size for this problem?
17.3 Implement an approximation of TRAVELING SALESMAN; that is, given a
graph G with costs for all edges, find the cheapest cycle that visits all vertices
in G. Try various heuristics to find the best approximations for a wide variety
of input graphs.
17.4 Write a program that, given a positive integer n as input, prints out the Collatz
sequence for that number. What can you say about the types of integers that
have long Collatz sequences? What can you say about the length of the
Collatz sequence for various types of integers?
