1. Trees
   1. Draw the red-black tree generated by inserting the following sequence of numbers one by one to an initially empty red-black tree:

      {53, 36, 5, 50, 43, 13, 8, 88, 62, 78, 97, 91, 33, 28, 4, 58},

      clearly identify the color of each node in your tree.
   2. Draw the (2,4)-tree that is equivalent to the red-black tree you gave in the previous question.
   3. What is the minimum number of data items (numbers) to be inserted into your (2,4)-tree you gave in the previous question to result a split operation of an internal node in your (2,4)-tree? Show an example of such a set of data items (numbers).
2. Compute a table representing the KMP failure function for the following pattern string within the double quotation marks:

   "tattarrattat"

   (Note: The double quotation marks are not part of the string. The meaning of the word is "the imitation of the sound of knocking on door".)
3. Given the following text string:

   huffman encoding algorithm uses optimized variable length bit strings to encode characters in a given string x over some alphabet. the optimization is based on the frequencies of the characters used in string x. the basic idea of the optimization is to use fewer digits to represent the characters with high frequencies. it is a greedy algorithm.

   1. Assume the alphabet contains the lower case letters only (i.e., you can ignore the word delimiters and punctuations). Compute the frequency table for letters appearing in the text only. Show both the algorithm you used to generate the table and the resulting table itself.
   2. Draw the Huffman tree based on your frequency table.
   3. Show the Huffman code assigned to each letter.
4. Using Lempel-Ziv algorithm to decode the following binary code string, where white space and new line characters are used to separate the codes.

   010000 010010 001111 000010 000001 000010 001100 000101 000000 001001 001101 010000 001111 010011 010011 001001 000010 001001 001100 001001 010100 001001 000101 010011 000000 000001 010010 100010 010100 001111 000000 000010 100010 011011 000101 000110 000101 010010 110101 000100 000000 110111 100011 100101 011100 011110 100000 111011 100111 101001 101011 101101 101111 110001

   The following rules are used when encoding a message to the above code string:
   • The alphabet should contain the white space and the 26 lower case letters (in that order).
   • 6 bits are used to encode each entry in the codebook dictionary.
   • When fully filled, the codebook dictionary simply stops accepting new entries. And the rest of the message is encoded using this codebook dictionary.
   • If you are curious how the above code is generated, here is the source code file I used to encode the message.
   Your tasks:
   1. Show the decoded message.
   2. If you did the decoding manually (not recommended), attach your final codebook dictionary.
      If you did the decoding using a program, attach your program's source code.
5. Draw a standard trie and a compressed trie respectively to store the following set of strings:

   {compassion, concern, confidence, consideration, content, honesty, honor, humility, humor, integrity, intelligence, modesty, morality}

6. Based on the directed and weighted graph shown below:
   
   1. Draw the adjacent matrix of the given graph;
   2. Show the adjacent vertices list of each vertex;
   3. Show the order of the vertices as they are visited in a DFS (depth first search) traversal starting from vertex A;
   4. Show the order of the vertices as they are visited in a BFS (breadth first search) traversal starting from vertex A.
   5. Draw the minimum spanning tree of the given graph. For the purpose of this question only, treat all the edges as undirected ones.

If you would like to submit this assignment electronically, use the submit name WA2. Currently, the submit script accepts files with extension name .pdf, .txt or .md.