Harvey Mudd College CS 60 Practice Final Exam

Fall 1999

During the exam, the only item to which you may refer is your own reference sheet, one double-sided sheet of 8.5" x 11" paper.

The exam is planned for 3 hours.

When code is requested, exhibiting the correct idea is more important than syntactic precision. However, keep your definitions clean and readable. Use the clearest program structure possible.

The answers to these problems should not be exceptionally long. Please think through your solution before you plunge into a long exposition that might not address the main point of the question.

1. (Invariants)

Consider the following list-reversal algorithm:

R = nil;
while ( !isEmpty(L) )
{
  R = cons(first(L), R);
  L = rest(L);
}

Give the loop invariant, energy function, and proof which shows that this algorithm correctly ends up with R == reverse(L₀), where L₀ is the initial value of L. You may wish to make use of the functions append, reverse, and length in your invariant or energy function. [Hint: Simulate the program for a list, say L₀ = [x₁, x₂, x₃, …., x_n]. What can you say about the value of append(reverse(L), R)?]

Consider the following code for binary search of an ordered array of length N. It returns an index at which the sought element occurs in the array, or -1 if the element does not occur.

long binary_search(int array[], long N, int sought) { long low = 0, high = N-1;

while ( /* invariant */ low <= high ) 
  { 
  long midpoint = (low + high)/2; 

  if( array[midpoint] == sought ) 

    return midpoint; // found

  if( array[midpoint] < sought ) 

    low = midpoint + 1; // search upper 

  else 

    high = midpoint - 1; // search lower 
  } 

return -1; // not found 
} 

Provide a descriptive and convincing loop invariant which shows that binary search really works. State why your invariant leads to the function giving the correct answer in the case that the sought element does not occur in the array.

2. (Complexity)

Consider developing a function which tests two lists for being equal-as-sets, meaning that they have the same elements without regard to repetition and order. For example, the pair of lists on the left are equal-as-sets, whereas the pair on the right are not:

[3, 1, 2, 1, 5] vs. [1, 2, 3, 5]     [1, 2, 3] vs. [2, 3, 4] 

Although the lists won't necessarily contain numbers as elements, assume throughout that two elements can be compared for == and for < in O(1) time. Consider three possible implementations for equal-as-sets:

a. Use two nested loops which range over the two lists, searching the second list once for every element of the first list to see whether the element lies in the second list, or vice-versa.

b. Sort the two lists first and remove duplicates, then check to see whether the lists are identical by comparing them point-by-point. (Don't give the algorithms themselves; just state reasonable assumptions.)

c. Build a hash table for the elements of each list. For each element of the first list, check to see whether it is in the table of the second and vice-versa. (Assume that each check is O(1).)

Give an "O" complexity comparison of these three methods for testing equality-as-sets, assuming for simplicity that both lists have the same number, N, of elements.

3. (Prolog)

Suppose a binary relation knows among people is given in Prolog. From this relation, show the definition in Prolog of another binary relation linked as follows: Person P is linked to person Q if either both P and Q know some person, or if one of them knows someone who is linked to the other.

4. (Logic and Grammars and Everything Else!)

A database is stored as a certain type of tree structure. Each interior (i.e. non-leaf) node of the tree is an array of references, indexed starting at 0. It is desired to access the leaves of this array using “Dewey decimal” notation (actually a generalization of the one used in libraries), in which there is one or more decimal numerals separated by periods (with no whitespace interspersed). The numerals toward the left are used to select within nodes nearer the root of the tree. For example:

3

Selects node number 3 from the nodes which are targets of the root.

1.20

Selects node number 1 from the nodes which are targets of the root, then node number 20 from that node.

3.0.1

Selects node number 3 from the nodes which are targets of the root, then node number 0 from that node, then node number 1 from that.

The diagram below shows how the node 3.0.1 is located, for example

a.

Construct a grammar for the Dewey decimal notation as described above. Assume that the number of levels is arbitrary and that null string (which would identify the root) is not allowed.

answer

b.

Sketch the structure of a parser for the language defined in part a. Use actual code or pseudo-code. Return an object failure if the input is not valid, and a Vector, array, or list which can be used to access the database if it is valid.

answer

c.

Sketch the structure of a program for accessing the tree database efficiently, given the result of part b.

answer

d.

Analyze the complexity of accessing the tree database (i.e. finding the node represented by a Dewey decimal string) based on your program in part c, not counting the time taken to parse the string itself. Indicate what size-parameter you are using, and state clearly any assumptions you are making in your analysis.

answer

e.

Similar to the previous problem, the “Dewey binary” system is like Dewey decimal, except that only binary numerals are used. Thus the alphabet is just {'0', '1', '.'}. For example, this is a valid string in Dewey binary:

1.101.0

Construct a finite-state machine (an acceptor) which accepts the Dewey binary language.

answer

f.

Give a regular expression for the Dewey binary language.

answer

g.

For the finite-state machine you constructed in part a, construct a simplified switching-circuit implementation of the state-transition part. Make the logic as simple as you can.

answer