Huffman code

Algorithms Final Exam

Assigned: 11/30/2021 at 2:10pm. I have explained the questions in class on 11/30.

Due: 12/02/2021 4:00pm on Blackboard (email submissions will not be accepted)

Weight: 25%

Late policy: Late submissions not allowed. For completeness, as before, it is good to state anyway that there will be 25 pts penalty for every late day. But, this is the final exam and the letter grades need to be submitted shortly after the due date. Therefore, you may not get your letter grade if you submit late.

There are 5 questions and each one is 20 points.

When submitting the document, make sure you include all the answers in a single file (such as MSWord) and use the following filename format: YourFullName_Final.doc

For each question you must include a figure (or a table, or even a pseudocode) for demonstration such as the tables we create in Boyer-Moore or dynamic programming and explain that figure as part of your answer. You may not get full credit for a question without a figure and a sufficient explanation of it.

Graduate students: In addition to the items above, for each question (except Question 5) you must include a pseudocode and briefly explain it.

1. In Chapter 8, Slides 14-19, we covered optimal binary search trees and explained how to compute the average/expected number of comparisons in a successful search in a given binary search tree.

Symbol	2	3	4	5	7	8	9
Probability	0.2	0.1	0.25	0.15	0.15	0.1	0.05

Table 1. Symbols and their probabilities

Answer the following briefly:

1. What is the greedy binary search tree for the table given in Problem 1 and what is its average number of comparisons.
2. Is the following tree better than your solution? Why or why not?

• What is Huffman code (Chapter 9 Greedy Technique, Slides 16-17) for the symbols given in Table 1? Show your work.

• Slide 4 of Chapter 8, solve the problem for the following row with n=9

5, 7, 1, 2, 1, 3, 10,  7, 1.

Show your work.

• In Chapter 6, Slide 34, heapsort is demonstrated using max-heap. Use min-heap to sort that list. Show your steps (what is your bottom-up constructed heap etc).

• Pick only one of the options below.

Option 1: Chapter 7, Slide 7 uses Horspool’s string searching algorithm. Solve that example using the Boyer-Moore algorithm. Explain your steps.

Option 2: In Chapter 7, we talked about the issues related to deleting an item from a hash table using Closed Hashing. Lazy deletion refers to the concept of marking an element as deleted, rather than erasing it entirely (https://en.wikipedia.org/wiki/Lazy_deletion). Explain how that can help on the example of Slide 20. After all the keys are inserted, perform the following:

insert “KID”

delete “A”

search “KID” (show that you can still find it?)

insert “M”