Assign6: Huffman Coding

Due Wednesday, August 12 at 11:59 pm

• The assignment deadline is by the end of the day in Pacific Daylight Time. This means that you have until 11:59pm PDT on the day of the assignment deadline to submit the assignment.
• There is no grace period for this assignment. The deadline is firm, and no late submissions can be accepted.
• Note that our Paperless submission system displays due dates and submission times in the PDT frame of reference.

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 assignment 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!

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

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

The only source files you will edit is huffman.cpp.

Additionally, you will answer questions in short_answer.txt.

Helpful Resources

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

• Trip's Assignment 6 YEAH slides
• A Guide to Testing Code in CS106B
• Common Build/Run Errors Guide, put together by one of our wonderful section leaders, Jillian Tang.
• Stanford Libraries Documentation
• Lecture Slides: Monday Trees, Tuesday Binary Search Trees, Wednesday Huffman Coding
• Section: Trees
• Textbook Chapter 16 Trees

Getting help

As on the last assignment, we recommend drawing lots of diagrams and making use of the debugger whenever possible when working on this assignment. As always, we're here to help you if you get stuck. You can contact us on Ed, email your section leader, or stop by the virtual LaIR (here is the schedule of help hours). You can find more information about how to get help at the LaIR here. As a reminder, try to visit the LaIR for code debugging questions – however, if you cannot make it to the LaIR due to timezone issues, you can post on Ed to get help. However, you must use a private post if you are including code so that you are not posting your solutions for the whole class to see.

Submit

Before you call it done, run through our submission checklist to be sure all your ts are crossed and is dotted. Then 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.