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

Exercises

  1. Devise an algorithm to reverse the contents of an ordered list. Determine the running time of your algorithm.
  2.   Devise an algorithm to append the contents of one ordered list to the end of another. Assume that both lists are represented using arrays. What is the running time of your algorithm?
  3. Repeat Exercise gif, but this time assume that both lists are represented using linked lists. What is the running time of your algorithm?
  4.   Devise an algorithm to merge the contents of two sorted lists. Assume that both lists are represented using arrays. What is the running time of your algorithm?
  5. Repeat Exercise gif, but this time assume that both lists are represented using linked lists. What is the running time of your algorithm?
  6. The withdraw method can be used to remove items from a list one at a time. Suppose we want to provide an additional a method, withdrawAll, that takes one argument and withdraws all the items in a list that match the given argument. We can provide an implementation of the withdrawAll method in the AbstractSearchableContainer class like this:
    public class AbstractSearchableContainer
        extends AbstractContainer
        implements SearchableContainer
    {
        void withdrawAll (Comparable arg)
        {
    	Comparable object;
    	while ((object = Find (arg)) != null)
    	    withdraw (object);
        }
        // ...
    }
    Determine the worst-case running time of this method for each of the following cases:
    1. an array-based implementation of an ordered list,
    2. a linked-list implementation of an ordered list,
    3. an array-based implementation of a sorted list, and
    4. a linked-list implementation of a sorted list.
  7.   Devise an O(n) algorithm, to remove from an ordered list all the items that match a given item. Assume the list is represented using an array.
  8. Repeat Exercise gif, but this time assume the ordered list is represented using a linked list.
  9. Consider an implementation of the OrderedList interface that uses a doubly-linked list such as the one shown in Figure gif (a). Compare the running times of the operations for this implementation with those given in Table gif.
  10. Derive an expression for the amount of space used to represent an ordered list of n elements using a doubly-linked list such as the one shown in Figure gif (a). Compare this with the space used by the array-based implementation. Assume that integers and pointers each occupy four bytes.
  11. Consider an implementation of the SortedList interface that uses a doubly-linked list such as the one shown in Figure gif (a). Compare the running times of the operations for this implementation with those given in Table gif.
  12.   Verify that Program gif correctly computes the sum of two polynomials.
  13. Write an algorithm to multiply a polynomial by a scalar. Hint: Use a visitor.

next up previous contents index

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