COMP 360 - Assignment 2

Due in class October 2

I hope you enjoy at least a couple of these:

  1. Stallings, problem 2.1, page 45.
  2. Stallings, problem 2.2, page 45.
  3. The following message (with correct spacing) was encoded using a monoalphabetic substitution code. What is the message and what was the key that produced the substitution?

    t ivd zcrtic fqniq tu tf q xavfcz feqxc pcqucz wk q fuvbc fnrrtxtciuak wty dtup mcfecxu uv upc bvanhc vr upc feqxc upc fuvbc xviuqtif fuvicf nfnqaak vi upc uve uv uqgc q fqniq wqup tu tf qafv icxcffqmk upqu upc fuvbc tf emvecmak pcqucz qiz upqu kvn pqbc upc rqxtatuk vr upmvdtiy dqucm vi upc fuvicf

  4. The following pairs of ciphertexts were computed by permuting the letters of two words using the same permutation, e.g. DAB GOD decodes to BAD DOG since in both cases the letters are reversed. Find the original pairs in each case.
    1. ROENEUGS EYESLAWN
    2. CEELXLENT DRUGNREAD
    3. SPERURIO SUDSTENT
    1. Perform Huffman encoding on the following four letter alphabet with the given probabilities: a (1/2), b (1/6), c (1/6), d (1/6).
    2. For the above probabilities, compute the Entropy and the average length of a codeword used by the Huffman encoding created in part (a).
    3. Perform the Huffman encoding on pairs of letters with the same probabilities as in part (a), i.e., aa (1/2 * 1/2 = 1/4), ab (1/2 * 1/6 = 1/12), etc.
    4. For the pairs of letters case, compute the average length of a codeword and the average number of bits to encode a single letter (i.e., the average codeword length divided by 2).
  6. Bonus #1: Compose a paragraph (as long as you possibly can make up) which makes sense and avoids using any of a given symbol which is conspicuously missing from a problem you are reading now.
  7. Bonus #2: Create an (hopefully amusing or apt) anagram using your name or a variation on your name or a nickname. For example, my full name is David Daniel Martin Krizanc and if you let me cheat a little and use D. Dany Krizanc I can get CRAZY AND KIND. If you can come up with something better for me I would be interested as well.
Report problems to dkrizanc at wesleyan.edu Top of Page