CS 306, Computer Algorithms II

Quiz 1, 30 January 2007

---

1. Given a sorted array a of n distinct elements (that is, no two elements in the array have the same value), describe a recursive algorithm that finds an index i such that a[i] = i or -1 if no such element exists. Briefly explain why your algorithm's correct.

   For full credit, your algorithm should be more efficient than an iterative algorithm for the problem.

   ---

   Consider the middle element of the array, a[m]. If a[m] = m then stop and return m. If a[m] < m, then every element with index i < m must be less than i because the indices decrease as slowly as possible (by 1 at each step), while the elements may decrease more quickly (remember, there are no duplicate elements). This means the algorithm can throw away the lower half of the array a[0..m] and recurse on the remaining half.

   Similarly, if a[m] > m, then every element with index i > m must be greater than i and the algorithm can throw away the upper half of the array a[m..n-1] and recurse on the remaining half.

   If there are no elements in the array, return -1.

   ---

2. Pointers can be compared using relational operators, as in p1 < p2, so long as p1 and p2 have the same type. Explain why comparing two pointers of different type should result in a type error. You may assume no conversions of any kind are involved.

   ---

   A relational operator between two pointers determines the order between the pointers; which comes before the other. For such an ordering to make sense, both pointers have to be referencing the same data sequence. If two data pointers have different types, they must be referencing different data sequences and a relational comparison between them makes no sense. Because a pointer's type is known at compile time, a relational comparison between different pointer types should be flagged as an error.

   ---

3. A colleague of yours has implemented a class, each instance of which contains an open file. Your colleague has implemented a class destructor to close the file when an instance is deleted. Does your colleague need to obay the Rule of Three for the class? Explain.

   ---

   Yes. The default copy constructor copies the reference to the open file, so when any copy is deleted, the file is closed for all copies. The default assignment operator has the same problem, plus, the file descriptor on the left-hand side of the assignment is clobbered by the file descriptor on the right-hand side of the assignment, leaking the descriptor.

   ---

4. A colleague of yours wrote a recursive preorder procedure to print the data stored in a binary tree:

   preorder_print(root)
     if root != nil
       print root->data
       preorder_print(root->left)
       preorder_print(root->right)
   

   and then translated the procedure into an iterative version using a while loop and a stack. Except your colleague forgot and used a queue instead of a stack. What's the difference, if any, in output behavior between the recursive and iterative versions of your colleague's procedure?

   ---

   The correct implementation is

   preorder_print(root)
     stack.push(root)
     while not stack.empty()
       root = stack.pop
       if root != nil
         print root->data
         stack.push(root->right)
         stack.push(root->left)
   

   The recursive implementation printed left-child data before right-child data. To provide the same behavior in the iterative version your colleague had to reverse the order in which the children are processed. However, that only works for a stack; your colleague used a queue, which prints the right-child data before the left-child data.

   ---