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

Exercises

    1. How much space does the DynamicArray class declared in Program gif use to store an array of Int32s of length N?
    2. How much space does the LinkedList class declared in Program gif use to store a list of n Int32s?
    3. For what value of N/n do the two classes use the same amount of space?
  1. Consider the Copy method of the DynamicArray class given in Program gif. What is the purpose of the test array != this on line 8?
  2. The Copy method of the DynamicArray class defined in Program gif has the effect of making the target of the assignment exactly the same as the source. An alternative version could assign the elements based on their apparent locations in the source an target arrays. That is, assign a[i] to b[i] for all values of i that are valid subscripts in both a and b. Write an Copy method with the modified semantics.
  3. 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.
  4. The Base property set accessor of the DynamicArray class defined in Program gif simply changes the value of the baseIndex field. 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?
  5. 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?
  6. 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.
  7. Consider the Times and Plus methods of the Matrix interface defined in Program gif. Implement these methods for the DenseMatrix class defined in Program gif.
  8. Which methods are affected if we drop the tail member variable from the LinkedList class declared in Program gif? Determine new running times for the affected methods.
  9. 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).
  10. 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).
  11. Consider the assignment operator for the LinkedList class given in Program gif. What is the purpose of the test linkedlist != this on line 8?

next up previous contents index

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