In this assignment there are nonprogramming options for all 100 points of the assignment.

1. (75 points)
   • Programming option: Complete the definition of the classes BrancherAndBounder and define a class ZOKNode so that
     1. the ZOKNode class extends the Node class
     2. the ZOKNode class has a public constructor that takes an array of integer weights, an array of integer benefits, and an integer capacity, and returns a node representing the root of a search tree for the ZOK instance with those parameters. This constructor should arrange that
        1. the number of items in the ZOK instance is equal to the smaller of the number of weights provided and the number of benefits provided (it may do this by truncating the longer of the two input lists)
        2. no item has a nonpositive weight or a nonpositive benefit (it may do this by ignoring any such items provided)
     3. the ZOKNode class implements appropriately each of the four abstract methods that are specified as part of the given Node abstract class, according to the specifications given in the documentation for that class. The optimistic estimator is to use the formula given on p. 634 of our textbook. The pessimistic estimator may simply return the negation of the value of the solution so far. The successor function is to arrange that
        1. successor states correspond to a decision about whether to include or not include the unconsidered item with the highest profit density
        2. no successor state will cause overflow of the knapsack
        3. in every list of successor states, the state that results from failing to include an item appears last.
     4. the toString method of the ZOKNode class returns a string that describes at least the items included so far in the corresponding partial solution, their total weight and benefit, and the number of items considered so far for inclusion.
     5. there is a public method BrancherAndBounder.branchAndBound that performs a depth first search for the state space with a given root of type Node, and returns a Node representing the solution.
     6. there is a new public method lazySolve method that work likes the solve method, except that it
        1. does not maintain a node curBest
        2. does not inspect successor nodes before inserting them into the priority queue, but instead inserts them unconditionally
        3. uses a new boolean-valued method (which you are to define abstractly for the Node interface and concretly for the ZOKNode class) isGoalNode that returns true iff the node represents a feasible solution. In the case of the ZOKNode class, all items must have been considered.
        4. inspects nodes as they leave the priority queue by applying the isGoalNode method to them, and returning a node as the overall solution if the result of this application is true
        5. returns null if the priority queue becomes empty
     7. instances of the BrancherAndBounder class maintain counters that keep track of the number of nodes generated, the number of nodes expanded, and the maximum number of nodes that are simultaneously in storage. For recursive methods, this last counter need only keep track of the maximum depth of recursion. The class is to have a method resetCounters() that resets these counters to their appropriate initial values.
     8. both BrancherAndBounder.branchAndBound and BrancherAndBounder.solve are to update the three counters described above in the appropriate way. In particular, the second of these methods is to keep track of the maximum size of the priority queue that it uses.

   • Nonprogramming option: Sketch that portion of the state space that is generated by each of the BrancherAndBounder.branchAndBound, BrancherAndBounder.solve, and BrancherAndBounder.lazySolve methods, for the instance tested in the BrancherAndBounder.main method with 6 items and capacity 22.

     For each node in each state space tree, show the total weight so far for the node, the total benefit so far for the node, and the value of the optimistic estimator for the node. Also label the nodes of each tree with the order in which the nodes are generated. Assume that all children of a node are generated at the same time. State how many nodes are generated for each method, and how many are expanded.

2. (25 points) Trace the behavior of the approximation algorithm of Section 13.4.3 of the text on the TSP instance whose adjacency matrix is given below. Show at least the result of finding the minimum-cost spanning tree, of finding the Euler tour, and of finding the minimum-cost Hamiltonian cycle. Assume that the vertices are numbered from 0 through 5.

       0  5 27 35 40 45
       5  0 25 37 42 47
      27 25  0 60 65 70
      35 37 60  0 10 15
      40 42 65 10  0 20
      45 47 70 15 20  0
   

   You may obtain your answer by programming, or by hand. You need not use any particular algorithm for finding the minimum-cost spanning tree. If you write a program, you may use either of the algorithms of Section 7.3.1 or 7.3.2 of the text with appropriate credit.

   You are to test your classes by executing the (main method of) the BrancherAndBounder class. This partially defined class, along with the fully defined but abstract Node class, is available on the class web site. You are to turn in hard and soft copies of your any class definitions that you modify. You are also to turn in a hard copy of the results of your tests, and of any work that you do by hand (that is, any work that you are submitting for credit as part of a nonprogramming option).