Huffman Coding

Tuesday, August 13

Due Tuesday, August 13 at 11:59 PM

  • Submit to Paperless. Deadline is 11:59 PM.
  • There are no late days for this assignment. The deadline is firm and no late submissions can be accepted.

The summit of Mount CS106B is now in your sights – many congratulations on the hard work that got you here! In Assignment 7, you'll develop a program that uses the nifty Huffman coding algorithm to compress and decompress files. You will be using concepts from across the entire quarter including ADTs, algorithms, recursion, pointers, and trees, while applying your now-powerful skills for effective development, testing, and debugging to complete an impressive piece of software that serves as a great testament to all that you have learned this 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

📦 Starter project

The starter project is provided as a zip archive. Download the zip, extract the files, and move the project folder to your CS106B folder. Open the .pro file in Qt Creator to get started.

Resources

Here are resources that will be helpful for this assignment:

Getting help

As always, we're here to help you if you get stuck. The Ed forum is open 24/7 for general discussion. Always start by searching first to see if your question has already been asked and answered before making a new post. To troubleshoot a problem with your specific code, your best bet is to bring it to the LaIR helper hours or office hours.

Submit

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