Description
Feel free to discuss and help each other out but it does not imply that you can give away your code or your answers! Make sure to read all instructions before attempting this lab. You can work with a lab partner and submit one lab package for your group.
You must use an appropriate provided template from Canvas or my website (zeus.mtsac.edu/~tvo) and output “Author: Your Name(s)” for all your programs. If you are modifying an existing program, use “Modified by: Your Name(s)”.
Lab question 1: Construct a Huffman coding tree for the following input string “more money”. Show the code for each character and include the total number of bits for the input string.
Lab question 2: Explain the main difference between standard tries and compressed tries. How much space is saved from standard tries to compressed tries?
Implement the MCP algorithm and print out resulting table as well as the minimum number of operations. Try BCD with B a 2×10 matrix, C a 10×50 matrix, and C a 50×20 matrix. Try another test case with 10×5, 5×2, 2×20, 20×12, 12×4, and 4×60.
Extra Credit: Implement the LCS algorithm and print out the longest common sub-sequence of the two strings. Try Y = “CGATAATTGAGA” and X = “GTTCCTAATA”.
Online Submission: Submit one PDF file via Canvas includes status, answers to lab questions, output and source code for all required programs.
