Submitting:

  • All homeworks should be turned in electronically to myCourses.
  • Paper submissions may be scanned in if legible.
  • If you take a photo of your paper solution, please take the photo outside or close to a bright window, for legibility.

Due dates:

  • Homeworks are due by 10pm on the due date (Thu).
  • No late submissions are accepted.
  • If there are extenuating circumstances, contact the instructor as soon as possible to make arrangements.

References:

  • If you find a resource helpful (from internet search, blog post, Stack Overflow, online courses, our lecture notes, etc), be sure to cite it. Citation format doesn’t matter, but make it easy for the TA to find the source: e.g., a clickable link.
  • Code / pseudocode should be your own work. If you find code online, understand how it works, then go write up your solution on your own.
  • The basic machine model was discussed in Lecture 1. Don’t use library functions which obviate the bulk of a question. E.g., if you’re asked to implement a sort, don’t use Python’s sorted().

Programming assignments:

  • Please submit all your code, either separately uploaded or in a ZIP (or tar) file. Up to 20 files (20MB total) may be uploaded to myCourses.
  • Make it easy for the TA to recompile and run it if needed.
  • Include a short, informal write-up describing your code. Make it easy for the TA to understand your code.
  • Include extensive test cases (valid and invalid input, simple and complex) demonstrating each aspect of your code. Document the purpose of each test case, and include a demo with actual output.
  • You are encouraged but not required to use revision control like Git and Github.

HW7 (40pts) (solutions)

  1. (20 pts) Choose one of the textbook problems #15-1 to #15-12 (p.406-412).
    Some of them, e.g., 15-2 and 15-5, may benefit from reading section 15.4. Others, e.g., 15-1 and 15-7, may benefit from ch22.
    Code your own implementation to solve the problem using dynamic programming (bottom-up).
    All policies for programming projects apply. User interface is your choice and can be rudimentary. Be sure to answer any questions given in the problem statement.

  2. The task is to make change for n (>0) cents using the fewest number of coins of given denominations `c_1=1 < c_2 < … < c_k`. Consider the following greedy strategy: use a coin of largest denomination smaller than the remaining amount, and iterate on the rest.
    • (a) (2 pts) Demonstrate via counterexample that this greedy strategy is not optimal if we can only use pennies, dimes, and quarters (i.e., c = { 1, 10, 25 }). (A coin set is called canonical if greedy is optimal for all n.)
    • (b) (2 pts) Find all n for which the greedy strategy is not optimal, on the above coin set.
  3. Below are 12 most-frequently used letters in the English language, and their relative frequencies, (Source: Norvig + Mayzner, 2012)
    • E T A O I N S R H L D C
      12.5% 9.3% 8.0% 7.6% 7.5% 7.2% 6.5% 6.3% 5.1% 4.1% 3.8% 3.3%
    • (a) (5 pts) Build a Huffman encoding tree for these 12 letters, following the pseudocode in lecture. (The sequence of left vs right child is important.)
    • (b) (2 pts) Encode a text of your choosing (at least 8 letters long) using the above Huffman tree. Show your chosen text and split it up by letter, to make it easier for the TA to read.
    • (c) (2 pts) Decode using the Huffman tree: 10111100110110001010000011100
      (If it looks like gibberish or doesn’t end properly, just do as much as you can.)
    • (d) (2 pts) Calculate the compression ratio of this Huffman code, versus a fixed-length encoding. (Assume the text to be compressed uses only these 12 letters.)
  4. (5 pts) Design (i.e., pseudocode) a dynamic programming solution for the 0-1 knapsack problem.
    Hint: For n items and a knapsack capacity of W, the subproblem graph is a 2D n x W table, where each subproblem (i, w) solves for the first i items and a capacity of w.