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

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 properties getIsFeasible, getIsComplete, getObjective, getBound, and getSuccessors. Note, the getSuccessors 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(self):
	pass
    greedySuccessor = abstractmethod(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 abstract Solution class:
```
class SimulatedAnnealingSolution(Solution):

    def randomSuccessor(self):
	pass
    randomSuccessor = abstractmethod(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 __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?