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)?|
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:
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 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.|
Copyright © 1999 Luc Devroye. Email: firstname.lastname@example.org.