CS251- Winter 1999- Practice questions

Third set of practice questions--CS251--Winter 1999

This set contains practice questions on the choice of an algorithm or data structure, and on Huffman trees.

Question 1	Coding. What is a prefix code? Can you state conditions for a prefix code so that any sequence of bits can get decoded to something? Can you give a simple 2-input-symbol prefix code such that not all bit sequences can get decoded?
Question 2	Huffman trees. We have symbols occurring with probabilities 1/2, 1/4, 1/8, ..., 1/2^n, 1/2^n. (Note that this sequence decreases geometrically, and that only the last two entries are identical.) Give a possible Huffman code for the given collection of symbols (for general n).
Question 3	Huffman trees (continued). Derive the average code length in the previous example when n is very very large. This involves the summation of a series. In particular, is the answer O(1), O(log n) but not O(1), O(n) but not O(log n), or Omega(n) but not O(n)?
Question 4	Efficient algorithms. How would you merge n (n is large) sorted linked lists of length n each into one gigantic sorted linked list of n^2 elements? Choose one of the following strategies: Merge all linked lists pairwise (they are all of length 2n now), and repeat this procedure until all lists are joined into one. Put all linked lists together into an array of size n^2. Apply buildheap to the array. Empty the heap into a new linked list. Define n traveling pointers, one for each linked list. Find the minimum top element by looking at all top elements. Transfer it to the new linked list. Update the traveling pointer in question, and repeat all of this until all linked lists are exhausted.
Question 5	Clever implementations. We are looking for a data structure to efficiently deal with biological data that consist of a large number (n) of species, and names of animals within species. We would like to perform the following operations: search (species, name) insert (species, name) delete (species, name) delete (species): this deletes an entire species. Assume that there are n names within each species, where n is large and unknown. How would you implement this? Please give a drawing and a type definition with very concise explanations. No long-winded text or explicit algorithms please! Give the worst-case complexities of your operations.
Question 6	Sending numbers. I have to send my friend a sequence of numbers 0, 1, or 2, and let us say that each number occurs about equally often. Propose a simple and space-efficient method for this.
Question 7	Huffman tree construction algorithm. I claim that if the frequencies of n symbols are given in a sorted list, then the Huffman tree can be constructed in linear time (O(n)) using a queue. Derive this algorithm.