University of Nevada Las Vegas
Howard R. Hughes College of Engineering
School of Computer Science
My Home Page

CSC 477/677 Assignment 2: Last Problem

Due date: Thursday, March 10, 2011, 4:00 PM.

So: you think the assignment was too easy? Want something challenging? Ok, you asked for it!
A prefix code is said to be alphabetic if the codes for the symbols are in lexical order. For example, A = 0, B = 10, C = 11 is alphabetical, but A = 1, B = 00, C = 01 is not.
Huffman's algorithm finds the most efficient prefix code for a given alphabet with a distribution, but that code might not be alphabetic. There is, however, a different algorithm "out there" which finds the most efficient alphabetic prefix code.
  1. Find that algorithm.
  2. Use that algorithm to find an optimal alphabetic prefix code for the same alphabet and distribution given for the first problem. Assume that "space" comes before A.

Back to Course Page