Assigned: February 25th, 2020
Due: March 5th, 2020
CIS 121 ¡ª Data Structures and Algorithms Homework Assignment 5
Note: The homework is due electronically on Gradescope on March 5th, 2020 by 11:59 pm ET. For late submissions, please refer to the Late Submission Policy on the course webpage. You may submit this assignment up to 2 days late.
A. Gradescope: You must select the appropriate pages on Gradescope. Gradescope makes this easy for you: before you submit, it asks you to associate pages with the homework questions. Forgetting to do so will incur a 5% penalty, which cannot be argued against after the fact.
B. LATEX: You must use the LaTex template provided on the course website, or a 5% penalty will be incurred. Handwritten solutions or solutions not typeset in LaTex will not be accepted.
C. Solutions: Please write concise and clear solutions; you will get only a partial credit for correct solutions that are either unnecessarily long or not clear. Please refer to the Written Homework Guidelines for all the requirements.
D. Algorithms: Whenever you present an algorithm, your answer must include 3 separate sections.
1. A precise description of your algorithm in English. No pseudocode, no code. 2. Proof of correctness of your algorithm
3. Analysis of the running time complexity of your algorithm
E. Collaboration: You are allowed to discuss ideas for solving homework problems in groups of up to 3 people but you must write your solutions independently. Also, you must write on your homework the names of the people with whom you discussed. For more on the collaboration policy, please see the course webpage.
F. Outside Resources: Finally, you are not allowed to use any material outside of the class notes and the textbook. Any violation of this policy may seriously affect your grade in the class. If you¡¯re unsure if something violates our policy, please ask.
February 25th, 2020 Homework Assignment 5 2 1. [15 pts] Sneha¡¯s Ticket Turmoil
Sneha is planning a spring break trip with some of the 121 TAs. She is considering booking one of n plane tickets, which she sorts in order by price. Amongst the chaos of planning this trip, she forgot to invite Liz. Salty that she wasn¡¯t invited on the trip, Liz messes with the order of the plane tickets while Sneha is not looking.
When Sneha notices the plane tickets are not in order, she is furious because it took her a long time to sort all the tickets in the first place. Thankfully, she observes that every ticket is at most k positions away from their sorted position. Liz must have been in a hurry and not done a good job of messing up the order.
Given this, design an algorithm to help Sneha sort the tickets in O(n log k) time so that she can better compare the tickets and book a flight. Note that you are given k as an input to the algorithm as well as the prices of the n tickets as an array A[1..n].
The following list would be an example with n = 7 and k = 3. [3,2,5,1,7,4,6]
Important Note: You only need to provide an algorithm and running time justification, but we recommend thinking about how you would go about proving its correctness.
2. [10 pts] Hufflepuff
Morgan is super excited about variable length encoding, and wants to see if she can push it to its ex- treme. Specifically, she wants to find the maximum difference in length between the shortest codeword and the longest codeword. Using the Huffman coding scheme on a set S of n symbols with frequencies f1 ¡Ý f2 ¡Ý . . . ¡Ý fn corresponding to characters c1 . . . cn, what is the maximum difference between encoding lengths for c1 and cn? Give an example set of frequencies that would produce this case. Make sure that your example is generalizable for any value of n. You must prove that your example frequencies result in the difference in encoding lengths which you stated, for all values of n, and that it is a valid set of frequencies (meaning they sum to 1). You do not need to prove that the difference you found is maximal. Assume n > 2.
[0 pts] Feedback: No feedback form for this assignment. Feel free to reach out to the Head TAs if you have any comments/concerns.