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 2inputsymbol 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:

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:

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 spaceefficient 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. 
Copyright © 1999 Luc Devroye. Email: luc@cs.mcgill.ca.