Due: Friday, April 5 2019 by 5pm
Collaboration: If you collaborated with someone during lab to generate data or a visualization, please acknowledge that person’s contributions clearly. You must work on the first problem individually.
Submission: Email files (probably one for the written questions and one for the chart/spreadsheet) by 5pm on the due date.
- Consider the following tree that defines a Huffman encoding. Recall that each of the rectangular leaf nodes contains a character and its frequency in some text. The binary code for each character is obtained by combining the binary digits along the path from the root to the given character (with 0s for left branches and 1s for right branches). For example, in this tree the binary code for M is 01111, and the code for N is 001.
(a) What are the binary codes for L and A?
(b) Decode the following message that was encoded with this tree: 1100100001111110001101101111111100000001
- Please submit the following items from the lab regarding searching, held Monday, April 1.
(a) Your description of linear/sequential search (lab question 1)
(b) Your description of binary search (lab question 2)
(c) Charts depicting the running times (number of steps) of the two search algorithms on both successful and unsuccessful searches (lab question 4). Be sure your axes are labeled and your graphs are titled.
(d) Your conclusions from the experiments on search algorithms (lab question 5).
