Data Structures and Algorithms with Object-Oriented Design Patterns in C#

Exercises

1. 1. How much space does the DynamicArray class declared in Program  use to store an array of Int32s of length N?
   2. How much space does the LinkedList class declared in Program  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?
2. Consider the Copy method of the DynamicArray class given in Program . What is the purpose of the test array != this on line 8?
3. The Copy method of the DynamicArray class defined in Program  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.
4. The array subscripting methods defined in Program  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.
5. The Base property set accessor of the DynamicArray class defined in Program  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?
6. Equation  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?
7. 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  to compute the correct position for column-major layout.
8. Consider the Times and Plus methods of the Matrix interface defined in Program . Implement these methods for the DenseMatrix class defined in Program .
9. Which methods are affected if we drop the tail member variable from the LinkedList class declared in Program ? Determine new running times for the affected methods.
10. How does the implementation of the Prepend method of the LinkedList class defined in Program  change when a circular list with a sentinel is used as shown in Figure  (c).
11. How does the implementation of the Append method of the LinkedList class defined in Program  change when a circular list with a sentinel is used as shown in Figure  (c).
12. Consider the assignment operator for the LinkedList class given in Program . What is the purpose of the test linkedlist != this on line 8?

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