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

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  by providing suitable definitions for the following operations: _compareTo, getIsFull, accept and __iter__. Write a test program and test your implementation.
3.   Complete the LeftistHeap class introduced in Program  by providing suitable definitions for the following operations: __init__, swapContentsWith and swapSubtrees. You will require a complete implementation of the base class BinaryTree. (See Project ). Write a test program and test your implementation.
4.   Complete the implementation of the BinomialTree class introduced in Program  by providing suitable definitions for the following operations: __init__, getCount and swapContentsWith. You must also have a complete implementation of the base class GeneralTree. (See Project ). Write a test program and test your implementation.
5. Complete the implementation of the BinomialQueue class introduced in Program  by providing suitable definitions for the following methods: __init__, purge, _compareTo, accept and __iter__. You must also have a complete implementation of the BinomialTree class. (See Project ). 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 . Implement a priority queue class that extends the BinaryTree class (Program ) and the abstract PriorityQueue class (Program ).
7. Implement a priority queue class using the binary search tree class from Chapter . Specifically, extend the BinarySearchTree class (Program ) and the abstract PriorityQueue class (Program ). You will require a complete implementation of the base class BinarySearchTree. (See Project ). Write a test program and test your implementation.
8. Devise and implement an algorithm to multiply two polynomials:

   

   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 .

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