Practice Midterm

There are five questions, all of equal weight. This exam is open-book, open-notes: you may use the textbook, your notes, your corrected homework, and any handouts or on-line materials.

(1) Consider what would happen if you implemented the nonrecursive quicksort program on page 122 of the book, but used a queue instead of a stack to hold the record of "work to be done." Would the algorithm sort correctly? If not, why not? If so, why is a queue inferior to a stack for this purpose?

(2) What positions could be occupied by the third largest key in a max-heap of 32 elements. (A max-heap is a heap with the largest element at the top.)

(3) How many comparisons does insertion sort do in the worst case? Try to derive the answer exactly, without using O-notation and without ignoring constant factors. (The worst case is when the file is in reverse-sorted order.)

(4) Suppose I implement a hashtable, using chaining to resolve collisions. Unfortunately, my program has a bug which causes the hashfunction to return the same value every time. What happens? How many comparisons does each search do?

(5) Draw a nondeterministic finite state machine that detects all strings of 0's and 1's that, when interpreted as binary numbers, are divisible by three.