1. Implement KNAPSACK (see Section 16.2). Measure its running time on a number of inputs. What is the largest practical input size for this problem?
2. 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.