CS410, Summer 1998			Name:
Quiz #2
July 2

Consult no sources.  Put your answers below (obviously).

1. Let T(n) = T(n/2) + O(1).  Give an f(n) such that T(n) is
Theta(f(n)).  You do not need to prove your answer correct. [Hint: I
asked Theta instead of O just so you couldn't come up with a loose
bound.  Just come up with the smallest upper bound you can.]

2. Write a Java method called find73 which takes one argument, an
object of type IntList, and returns true if 73 is in the linked list
represented by the object, and false otherwise. Assume the empty list
is represented by null.

class IntList {
    int val;
    IntList rest;
}

3. What kind of linked list is best for implementing:
a) a stack
b) a queue
c) a double-ended queue
(Be specific, but more than half a sentence is unnecessary.)

ANSWERS
=======

1. T(n) is O(log n).

Notes that aren't part of the answer:
*  Notice we cut the problem size in half and do constant
   additional work.  An example algorithm with this recurrence is binary search.
* A recursion tree would look (sideways) like: 1 -- 1 -- 1 -- 1...
  and there are log n levels.
* The master theorem applies: a = 1, b = 2, k = 0
	a = b^k so the "second case" applies.
	        so T(n) is O(n^k log n) 
			is O(log n) since k = 0

Grading: 4 points
	1 point for O(n)
	1 point for a recursion tree that shows a "1" at each level,
		but has the wrong number of levels.

2. boolean find73(IntList lst) {
	while (lst != null) {
	    if (lst.val == 73)
		return true;
	    lst = lst.rest;
	}
	return false;
   }

Grading: 3 points
	2 points off for not iterating through the list with a for loop, while
		loop, or tail recursion.
	1 point off for minor Java glitches (2 points for lots of them).

3. a) singly-linked list
   b) singly-linked list with pointer to last item
   c) doubly-linked list

Grading: 1 point each, no partial credit except .5 for "b) singly-linked list"