Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Projects

  1.   Design a class that implements the Solution interface defined in Program gif to represent the nodes of the solution space of a 0/1-knapsack problem described in Section gif.

    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 gif to solve the problem given in Table gif.
    2. Use your class with the BreadthFirstSolver defined in Program gif to solve the problem given in Table gif.
    3. Use your class with the DepthFirstBranchAndBoundSolver defined in Program gif to solve the problem given in Table gif.
  2. Do Project gif for the change counting problem described in Section gif.
  3. Do Project gif for the scales balancing problem described in Section gif.
  4. Do Project gif for the N-queens problem described in Exercise gif.
  5. 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 ();
    }
  6. Design and implement a SimulatedAnnealingSolver class, along the lines of the DepthFirstSolver and BreadthFirstSolver classes, that implements the simulated annealing strategy described in Section gif To do this you will have to add a method to the Solution interface:
    public interface SimulatedAnnealingSolution
        extends Solution
    {
        Solution RandomSuccessor ();
    }
  7. 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.
  8. Consider the divide-and-conquer strategy for matrix multiplication described in Section gif.
    1. Rewrite the implementation of the times method of the Matrix class introduced in Program gif.
    2. Compare the running time of your implementation with the tex2html_wrap_inline58434 algorithm given in Program gif.
  9. Consider random number generator that generates random numbers uniformly distributed between zero and one. Such a generator produces a sequence of random numbers tex2html_wrap_inline68399. 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

    displaymath68393

    1. Write a program to compute the first 1000 pairs of numbers generated using the UniformRV defined in Program gif.
    2. What conclusions can you draw from your results?


next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.