Data Structures and Algorithms with Object-Oriented Design Patterns in C++

Projects

Design and implement a class derived from the abstract Solution class defined in Program which represents 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 member functions IsFeasible, IsComplete, Objective, Bound, Clone and Successors. Note, the Successors function requires an iterator which 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 member function to the abstract Solution class:
```
class GreedySolution : public Solution
{
    virtual Solution& GreedySuccessor () const = 0;
};
```
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 member function to the abstract Solution class:
```
class SimulatedAnnealingSolution : public Solution
{
    virtual Solution& RandomSuccessor () const = 0;
};
```
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 multiplication operator, operator*, of the Matrix<T> class declared 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 declared in Programs and .
2. What conclusions can you draw from your results?