IS4200/CS6200 12S Homework 03

Created: Tue 13 Mar 2012
Last modified: 

Assigned: Tue 13 Mar 2012
Due: Tue 20 Mar 2012


Instructions

  1. This assignment is due at the beginning of class on the due date assigned above.

  2. In addition to the results requested below, you must submit printouts of any code you wrote that generates those results.

  3. If you collaborated with others, you must write down with whom you worked on the assignment. If this changes from problem to problem, then you should write down this information separately with each problem.


Problems

Problem 1. (20 points) Huffman coding.

Consider the following text fragment:

a man, a plan, a canal, panama

Note: This is a famous palindromic sentence --- the letter sequence is the same forwards or backwards.

This text fragment contains 30 total characters (including the six internal space characters and the three commas), and it includes eight unique characters.

Problem 2. (15 points) Lempel-Ziv: Encoding.

Consider your three initials, lower case. (If you do not have a middle name, use the first two letters from your first and the first letter from your last name.) For my name, Javed A. Aslam, the three lower case initials are "jaa".

Problem 3. (15 points) Lempel-Ziv: Decoding.

Consider the string:

00110010010010010011011010110101101100000111101000010110100000100011100

This bit string is the result of encoding a piece of text using the Lempel-Ziv algorithm described above (and in class).

Problem 4. (10 points) Elias Omega Codes

Problem 5. (40 points) PageRank and Markov Chains

Consider the following directed graph:

graph