Assign7: Huffman (optional)

We have revised our end-quarter schedule to make completion of Assignment 7 optional.

• This is the Assignment 7 that would be the usual capstone in a normal CS106B course, but in this highly non-normal quarter, students are not expected to complete this assignment nor submit for credit. You are good to go on earning course credit given complete and satisfactory work on assignments 1-6, section participation, and midquarter assessment.
• For a student at risk of not passing the course, our original plan was to offer use of the optional end-quarter exam as a makeup; instead Assignment 7 is now the makeup task. A student may complete and submit Assignment 7 and use that score to replace one assignment grade, and thus potentially bring the overall record into the "Satisfactory" range. We must receive an Assignment 7 submission by end of day June 10 to be considered in grading.

We've made it to the final CS106B assignment of the quarter! It's been a challenging, but hopefully rewarding, journey through many different topics to get here, and we hope that this assignments acts as a final capstone of sorts for your CS106B experience. Your goal will be to write a program that uses Huffman coding to compress and decompress files. This task pulls together ideas from all over the quarter – recursive exploration, linked structures, trees, and streaming algorithms and will allow you to make use of many different new tools in your programming toolkit that you have built up over the quarter. Once you’ve finished coding this one up, you’ll have a fairly impressive piece of software that’s powered by a bunch of clever algorithms – what a great way to finish off the quarter!

Learning goals

• Students will gain practice with constructing, manipulating, and traversing binary trees.
• Students will be able to synthesize a number of different data structures and algorithms to accomplish an important real-world task.
• Students will develop understanding of how compression algorithms take advantage of patterns and trends in data to allow for more space-efficient representation.

Assignment parts

This assignment consists of a warmup exercise to get you thinking about the different components of Huffman encoding and a main programming task that asks you to implement the Huffman encoding algorithm.

• Warmup

  This component consists of some conceptual exercises on Huffman coding, as well as developing some tree-traversal code that will be helpful for later use when testing your Huffman program.

• Huffman

  The grand finale: You will implement an end-to-end compression -> decompression tool that employs Huffman coding to optimally compress data.

Getting started

As always, we have provided a ZIP of the starter project. Download the zip, extract the files, and open the project in Qt creator.

📦 Starter code

This assignment is to be completed individually. Working in pairs/groups is not permitted.

Getting help

Here are some resources that you might find helpful while working on the assignment:

• You can find the slides from the Assignment 7 YEAH session here and the recording of the session has been posted on Canvas. We highly recommend starting with these resources as you get started on the assignment.
• We will be hosting two collaborative group work session for Assignment 7. The sessions are open to anyone and will be focused on providing a collaborative group work environment where students can work together and collaborate on the assignment at a high level, while a section leader will be around to answer any conceptual questions regarding how to get started on the assignment. Zoom information for both sessions can be found on the Zoom details page.
  • The first session will be on Tuesday, June 2 from 6:00-7:00pm PDT.
  • The second session will be on Wednesday, June 3 from 5:00-6:00pm PDT.
• Lecture Slides: Friday Trees, Wednesday Binary Search Trees, Friday Huffman Coding
• Section: Trees
• Textbook Chapter 16 Trees
• We’re here to help you get there! Contact us on Ed discussion, email your section leader, or come join non-stop coding party that is the LaiR.

Submit

Review our submission checklist before calling it done. Upload your completed files for grading to the Paperless website.

Please submit only the files you edited; for this assignment, these files will be

• huffman.cpp
• short_answer.txt

🏁 Submit to Paperless

Note: When submitting to Paperless, due dates are expressed in PDT.