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

Projects

  1. Design and implement a sorting algorithm using one of the priority queue implementations described in this chapter.
  2. Complete the BinaryHeap class introduced in Program gif by providing suitable definitions for the following methods: compareTo, isFull, accept, and getEnumeration. Write a test program and test your implementation.
  3.   Complete the LeftistHeap class introduced in Program gif by providing suitable definitions for the following methods: LeftistHeap (constructor), getLeftHeap, getRightHeap, swapContents, and swapSubtrees. You will require a complete implementation of the base class BinaryTree. (See Project gif). Write a test program and test your implementation.
  4.   Complete the implementation of the BinomialTree class introduced in Program gif by providing suitable definitions for the following methods: BinomialTree (constructor), getCount, and swapContents. You must also have a complete implementation of the base class GeneralTree. (See Project gif). Write a test program and test your implementation.
  5. Complete the implementation of the BinomialQueue class introduced in Program gif by providing suitable definitions for the following methods: BinomialQueue (constructor), purge, compareTo, accept, and getEnumeration. You must also have a complete implementation of the BinomialTree class. (See Project gif). Write a test program and test your implementation.
  6. The binary heap described in this chapter uses an array as the underlying foundational data structure. Alternatively we may base an implementation on the BinaryTree class described in Chapter gif. Implement a priority queue class that extends the BinaryTree class (Program gif) and implements the PriorityQueue interface (Program gif).
  7. Implement a priority queue class using the binary search tree class from Chapter gif. Specifically, extend the BinarySearchTree class (Program gif) and implement the PriorityQueue interface (Program gif). You will require a complete implementation of the base class BinarySearchTree. (See Project gif). Write a test program and test your implementation.
  8. Devise and implement an algorithm to multiply two polynomials:

    displaymath65982

    Generate the terms of the result in order by putting intermediate product terms into a priority queue. That is, use the priority queue to group terms with the same exponent. Hint: See also Project gif.


next up previous contents index

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