Assign6: Huffman Coding

Due Wednesday, August 11 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're going to say it one more time before you start: we will not be accepting submissions after 8/11 at 11:59PM PT. Even if you're not quite finished with the assignment, we strongly recommend that you submit what you have by this deadline. Any work submitted after 8/11 will not be graded.

🛑🛑

The summit of Mt. CS106B is now in your sights – many congratulations on the hard work that got you here! The task for Assignment 6 is to write a program that uses the nifty Huffman coding algorithm to compress and decompress files. This program draws upon concepts from across the quarter including use of ADTs, recursive exploration, linked structures, trees, and streaming algorithms and will leverage the powerful skills for effective development, testing, and debugging that you have built up. You'll finish with an impressive piece of software that serves as a great testament to all that you have learned 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 utility functions that you will later use to test your Huffman program.

• Huffman

  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 double-click the .pro file to open the project in Qt Creator.

📦 Starter code

Resources

Here are resources that will be helpful for this assignment:

• The YEAH Session is scheduled for Friday 8/6 at 11:30AM PT. Zoom info, slides, and the video can be found on Ed
• Jin-Hee, Grant, and Lauren's Assignment 6 YEAH Slides
• The CS106B Style Guide
• 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
• Section: Trees
• Textbook Chapter 16 Trees

Getting help

With lots of pointers flying around, drawing diagrams and lots of debugger time are key skills to rely on. As always, we're here to help you if you get stuck. You can reach out with a post on Ed, email your section leader, join in at office hours, or sign up for one-one-one help at the LaIR here. For questions specific to your code, coming to Lair is your best bet. If you cannot attend LaIR due to timezone issues, you may post your question on Ed. 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 [submit checklist][submit_checklist] to be sure all your t's are crossed and i's dotted. Then upload your completed files to Paperless for grading.

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

• huffman.cpp
• short_answer.txt
• secretmessage.txt.huf, an encoded message for your section leader

🏁 Submit to Paperless

Note: On Paperless, all due dates and submission times are expressed in [Pacific time][PT].