Data Structures and Algorithms with Object-Oriented Design Patterns in Java

Projects

Design a class that implements the Solution interface defined in Program to represent the nodes of the solution space of a 0/1-knapsack problem described in Section .
Devise a suitable representation for the state of a node and then implement the following methods isFeasible, isComplete, getObjective, getBound, clone, and getSuccessors. Note, the getSuccessors method returns an Enumeration which that enumerates all the successors of a given node.
1. Use your class with the DepthFirstSolver defined in Program to solve the problem given in Table .
2. Use your class with the BreadthFirstSolver defined in Program to solve the problem given in Table .
3. Use your class with the DepthFirstBranchAndBoundSolver defined in Program to solve the problem given in Table .
Do Project for the change counting problem described in Section .
Do Project for the scales balancing problem described in Section .
Do Project for the N-queens problem described in Exercise .
Design and implement a GreedySolver class, along the lines of the DepthFirstSolver and BreadthFirstSolver classes, that conducts a greedy search of the solution space. To do this you will have to add a method to the Solution interface:
```
public interface GreedySolution
    extends Solution
{
    Solution GreedySuccessor ();
}
```
Design and implement a SimulatedAnnealingSolver class, along the lines of the DepthFirstSolver and BreadthFirstSolver classes, that implements the simulated annealing strategy described in Section To do this you will have to add a method to the Solution interface:
```
public interface SimulatedAnnealingSolution
    extends Solution
{
    Solution RandomSuccessor ();
}
```
Design and implement a dynamic programming algorithm to solve the change counting problem. Your algorithm should always find the optimal solution--even when the greedy algorithm fails.
Consider the divide-and-conquer strategy for matrix multiplication described in Section .
1. Rewrite the implementation of the times method of the Matrix class introduced in Program .
2. Compare the running time of your implementation with the algorithm given in Program .
Consider random number generator that generates random numbers uniformly distributed between zero and one. Such a generator produces a sequence of random numbers . A common test of randomness evaluates the correlation between consecutive pairs of numbers in the sequence. One way to do this is to plot on a graph the points
1. Write a program to compute the first 1000 pairs of numbers generated using the UniformRV defined in Program .
2. What conclusions can you draw from your results?