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

Projects

Design a class that extends the abstract Solution class 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 feasible?, complete?, objective, bound, and successors. Note, the successors method returns an iterator object 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 abstract Solution class:
```
class GreedySolution < Solution

    def greedySuccessor
	# ...
    end

end
```
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 abstract Solution class:
```
class SimulatedAnnealingSolution < Solution

    def randomSuccessor
	# ...
    end

end
```
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 mul 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?