Data Structures and Algorithms with Object-Oriented Design Patterns in Python
next up previous index

Exercises

    1. How much space does the Array class declared in Program gif use to store an array of IntTypes of length N?
    2. How much space does the LinkedList class declared in Program gif use to store a list of n IntTypes?
    3. For what value of N/n do the two classes use the same amount of space?
  2. The array subscripting methods defined in Program gif don't test explicitly the index expression to see if it is in the proper range. Explain why the test is not required in this implementation.
  3. The baseIndex property setBaseIndex accessor of the Array class defined in Program gif simply changes the value of the baseIndex instance attribute. As a result, after the base is changed, all the array elements appear to have moved. How might the method be modified so that the elements of the array don't change their apparent locations when the base is changed?
  4. Equation gif is only correct if the subscript ranges in each dimension start at zero. How does the formula change when each dimension is allowed to have an arbitrary subscript range?
  5. The alternative to row-major layout of of multi-dimensional arrays is called column-major order . In column-major layout the leftmost subscript expression increases fastest. For example, the elements of the columns of a two-dimensional matrix end up stored in contiguous memory locations. Modify Equation gif to compute the correct position for column-major layout.
  6. Write a plus method for the DenseMatrix class defined in Program gif that implements the usual matrix addition semantics.
  7. Which methods are affected if we drop the _tail member variable from the LinkedList class. Determine new running times for the affected methods.
  8. How does the implementation of the prepend method of the LinkedList class defined in Program gif change when a circular list with a sentinel is used as shown in Figure gif (c).
  9. How does the implementation of the append method of the LinkedList class defined in Program gif change when a circular list with a sentinel is used as shown in Figure gif (c).
next up previous index

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