Data Structures & Algorithms

Exam 1

Sample 2, 75 Minutes

In the class ArrayLinearList a linear list is represented as a one-dimensional array element. The data member size is such that the list elements are in positions 0 through size-1 of the array. The member method compress removes every other element of the list. For example, if the list element[0:5] = [1, 2, 3, 4, 5, 6], whose size is 6, is compressed, the result is [1, 3, 5], whose size is 3.

(a)
[8] Write code for the member method compress. Do not assume the existence of any methods for ArrayLinearList.

(b) [2] What is the time complexity of your code as a function of the list size?
Consider the class Chain. The public methods of this class are:
makeEmpty() ... make the chain empty. The time taken by this method is O(1).
append(x) ... append x to the end of the chain. The time taken by this method is O(1).
iterator() ... returns an object of type Iterator that can be used to move through the chain from left to right. The time taken by this method is O(1).

The public methods associated with the chain iterator are:
hasNext() ... returns true iff the chain has more elements. The time taken by this method is O(1).
next() ... returns the next element in the chain; returns null if there is no next element. The time taken by this method is O(1).

The nonmember method threeWaySplit(a,b,c,d) splits the chain a into three chains b, c, and d. The first, fourth, seventh, ... elements of a, in that order, define the chain b; the second, fifth, eighth, ... elements of a, in that order, define the chain c; and the third, sixth, ninth, ... elements of a, in that order, define the chain d. The chain a is not modified by the split.

(a)
[8] Write code for the nonmember method threeWaySplit(a,b,c,d). Do not assume the existence of any methods other than those stated above.

(b) [2] What is the time complexity of your code as a function of the length of the initial chain a?
In an n x n S-matrix, n is odd and all terms other than those in rows 1, n and n/2 + 1, the top half of column 1, and the bottom half of column n are zero. An S-matrix can be compactly stored in a one-dimensional array by first storing the rows of the S in the order 1, n/2 + 1, and n. Next, the remaining elements of column 1 of the S are stored. Finally, the remaining elements of column n of the S are stored.
```
                              x x x x x x x x x 
                              x              
                              x    zero   
                              x              
                              x x x x x x x x x 
                                              x
                                 zero         x
                                              x
                              x x x x x x x x x 


                         x denotes a possible nonzero


                         all other terms are zero
```
(a)
[2] Give a sample 5 x 5 S-matrix and its compact representation.

(b)
[8] Suppose that we are defining a class SMatrix that represents an n x n S-matrix in a one-dimensional array element as above. Besides element, the class has the data members n and zero (the zero element for the matrix). Write code for the member method get(i, j) which returns the value of S(i,j) for 1 <= i <= n and 1 <= j <= n. You must verify that i and j are in this range.

Solutions