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

Exercises

1. How much space does the Array class declared in Program use to store an array of Fixnumss of length N?
2. How much space does the LinkedList class declared in Program use to store a list of n Fixnums?
3. For what value of N/n do the two classes use the same amount of space?
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.
The baseIndex attribute accessor of the Array class defined in Program 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?
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?
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.
Write a + method for the DenseMatrix class defined in Program that implements the usual matrix addition semantics.
Which methods are affected if we drop the @tail member variable from the LinkedList class. Determine new running times for the affected methods.
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).
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).