CSc 22000: Algorithms

Lab 3: Huffman Coding

[ Introduction | Setup | Specification | Guidelines | Collaboration Policy | Submission and Grade ]

Introduction

In this lab, you will implement the Huffman coding algorithm using C++. Please read Chapter 16.3 of the textbook to review Huffman coding.

Setup

We have prepared skeleton files to help you get started with the lab. To set up the lab workflow on your computer, download lab3.tgz and type the following commands to extract the files:

% tar -xf lab3.tgz
% cd lab3

Specification

Inside the lab3 directory, you will find the following files:

% ls
grader.py      huffman.h           makefile               test_data
huffman.cpp    huffman_test.cpp    output_required.txt

Once you've completed the lab by editing the huffman.cpp file, you can test it as follows:

% python grader.py
Score: 3 out of 3 = 100%
--------------------------------------------- Summary ----------------------------------------------
All tests passed.
------------------------------------------ Builder Output ------------------------------------------
g++ -Wall -c huffman.cpp
g++ -Wall -c huffman_test.cpp
g++ -Wall huffman.o huffman_test.o -o solution

rm -f *.o solution

Guidelines

Now that you've seen how you can test your solution, let's go through some of the guidelines you should follow when implementing the lab.

First and foremost, this lab is designed to be completed on a machine in NAC7105 Linux Lab. Please make sure your solution executes as expected on those machines since your solution will be graded on one of those machines as well.

We have provided a skeleton file huffman.cpp as a starting point. Your task is to only complete the following functions found inside huffman.cpp file.

1. HuffmanNode::HuffmanNode(char character, int frequency);
2. HuffmanNode::HuffmanNode(int frequency, HuffmanNode *left, HuffmanNode *right);
3. HuffmanNode **genHuffmanNodes(char *characters, int *frequencies, int length);
4. HuffmanNode *genHuffmanTree(HuffmanNode **nodes, int length);
5. void MinHeap::exchange(int firstIndex, int secondIndex);
6. void MinHeap::minHeapify(int index);
7. HuffmanNode *MinHeap::extractMin();

Remarks:

Testing:

The grader.py script grades your solution by running the following tests:

  1. Compute the Huffman code for: abbbb
  2. Compute the Huffman code for: accbbdabddaaadaafaefcdbcadaaaadaaabdfaaaaaaaeadaaceabbcddaebccccadaadaaabbaeeadaaaaeefaabcfacdeababd
  3. Compute the Huffman code for: cbefaacdcfafbccccadafcaaaebecfafffccdcefccfcffccaccfafeccffccffcaacfffdfcdaededefdffecccbddacdb

After running all the test cases, the script

  1. Shows your grade,
  2. For each test that failed, shows the result computed from your implementation and the required result from the output_required.txt file.

Feel free to examine the output_required.txt file yourself, but make sure not to edit it. This file contains multiple sections separated by the @ symbol with each section describing the required output of a single test case. The sections are ordered in the same order as the test cases above.

Before you submit the lab, try to pass all the test cases shown above. You will be graded on those test cases as well as another set of 3 test cases.

Collaboration Policy

You must write all the code you hand in for the programming assignments, except for code that we give you as part of the assignment. You are not allowed to look at anyone else's solution. You may discuss the assignments with other students, but you may not look at or copy each others' code. You may not use code that might be available online.

Submission and Grade

The deadline for the lab is May 4, 2016 11:59 PM.

Please submit only the completed huffman.cpp file to the Submission Server. The submission server will stop accepting solutions after the deadline.

Once the lab has been graded, you can retrieve your grade from the Grade Server. You will be notified when the grades will be available during the class.


© 2016: Nelly Fazio and Milinda Perera.