CS 305 Test 1

CS 305, Computer Algorithms I

Fall 2003 - Test 1

Nyhoff identifies three control structures with which it's possible to construct any algorithm. It is possible to construct an algorithm using only sequencing; is it possible to construct an algorithm using only one of the other two control structures? If so, give an example; if not, explain why.
Without sequencing, you have iteration and choice left. You can implement linear search using a iteration only:
```
for (i = 0; (i < n) and (a[i] != x); i++) { }
```
You can implement binary maximum (or minimum) using choice:
```
if (a < b)
  max = b
else
  max = a
```
A lot of people had a harder time with this then they should have, mainly because they didn't describe an algorithm.
In class we derived an expression to map indices to array elements. That derivation depended on knowing the address of the first array element.
Derive the expression to map indices to array elements when we know the address of the last array element. Don't forget to explain your derivation. You should assume C++ style arrays and only answer the question for 1-dimensional arrays.
Given an n-element array, the last array element is at index n - 1. We have to express an index into the array as an offset from index n - 1; that is, index 0 is offset n - 1 from the last element; index 1 is offset n - 2 from the last element; and, in general, index j is offset n - (1 + j) from the last element. The expression we need to map index j into address addr_j is
addr_j = addr_n-1 - (n - (1 + j))*sizeof(Etype)
where addr is the address of the last element and Etype is the element type.
Several people seemed to come close to the right answer, but it was hard to tell from the answers given. To many people didn't even come close, most just dealing with the index values without considering the element addresses and a few trying to use a for loop.
A colleague of yours wants to declare an n-dimensional array
element-type array-name[dim₁]...[dim_n];
but is afraid it will use up too much memory. To save space, your colleague wants to declare a 1-dimensional array with the same number of elements. Show the equivalent declaration for the 1-dimensional array. What is your opinion of your colleague's attempt to save space? Explain.
An n element 1-dimensional array contains n elements; an n x m element 2-dimensional array contains nm elements; and so on. The number of elements in your colleague's array should be
dim₁*dim₂*. . .*dim_n
and the necessary declaration is
element-type array-name[dim₁*. . .*dim_n];
Most people got the declaration wrong but the observation that it wasn't helpful right. The most frequent error was adding rather than multiplying the separate dimensions into a single one.
Nyhoff mentions that arrays violate a basic principle of object-oriented programming. Do records violate the same principle? Explain.
Nyhoff's problem with arrays is that they're not self-contained; in particular they don't contain an indication of how many elements they contain. Records don't suffer from that problem. Everything you need to know about using a record is contained in the record: the name and type of the fields
Apparently many people tried to reason backwards on this problem, noting that records were heterogeneous and arrays homogeneous, concluding that Nyhoff was complaining about homogeneity and stating that records didn't have that problem, which is correct but not what Nyhoff was complaining about.

This page last modified on 27 September 2003.