(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.