Overview

You will write code to read files and store the frequency of each character in a frequency table. To prepare for part b of the assignment you will write a planning document with the pseudocode for your implementation of Huffman’s algorithm and the data structure you plan to use.

Structure

This project is broken up into two parts:

1. Complete the interface to read files and create a character frequency table.

2. Answer the question for the 2b planning document

Complete the Interface

Start by downloading the project zip folder from Canvas and extracting it. You can use any text editor to open the project source files. As with PA1, if you are using an IDE like Visual Studio or CLion, take care that you are only using it to edit the source files, not to compile and run the code. You must do that on the terminal using the provided makefile (covered in the next section).

When completing the interface, you may add new public or private functions or member variables. However, you may not modify or remove existing functions or member variables. Additionally, you may not change the way the tests are written. E.g. You may not modify the tests so that a new function you create is called in the test case. Do not create a main function. The testing framework will generate it automatically.

You may use anything in the C++ STL to complete the assignment. We encourage you to explore the new features added in the C++11, C++14, and C++17 standards.

frequency_table Interface Details The frequency_table class represents a lookup table that stores the frequency of occurrences of each ASCII value.

File Details

To aid in completing the project, we have provided a project skeleton on Canvas. Here is a short description of the files provided:

• frequency_table.h – Contains the declaration of the frequency_table class.

• frequency_table.cpp – Contains the definition of the member functions of the frequency_table class.

• catch.hpp – Catch framework header file. Do not modify this file.

• catch_main.cpp – Separate compilation unit for the catch framework to speed up the compilation process. Do not modify this file.

• frequency_table_tests.cpp – Contains sample Catch unit tests for the frequency_table class. You may add your own test cases to this file.

• makefile – Contains rules for compiling the project. Do not modify this file.

• texts/*.txt – Contains sample text files used in the test cases. Do not modify these files. You may add files to the folder for testing purposes.

Testing

As with PA1, we will use the Catch testing framework to test your implementation. Sample test cases are provided to show how your class will be used and to show how Catch tests are written so you can write your own. See the programming assignment 0 document for more details on structure of a catch test.

Compiling and Running Locally

As with PA1, we have provided a makefile for you to compile your project. For more details on makefiles, see the programming assignment 0 document. To compile, open a terminal, cd to the directory containing the project files, and run make to compile the project. To run the project, run ./build/test_pa2 in your terminal.

The sample tests provided will ensure your implementation correctly conforms to the interface but are not meant to be exhaustive. You are encouraged to write your own test cases to ensure your project works properly under all edge cases.

Compiling and Running Remotely

We will compile and test your project on the CISE servers. This will allow you to test your project on the exact same environment we will use for testing. Compiling and testing the project locally on your machine should give the same result as compiling and testing on the CISE servers, but there is always a small chance for some disparities. Thus, we recommend testing your project on the CISE servers so you can be absolutely sure your code will work when we test it.

If you need a refresher on how to compile and run your project remotely, see the programming assignment 0 document.

Planning Document

For part b of the programming assignment, you will implement Huffman’s algorithm. Complete the following tasks in a planning document:

a) Write pseudocode for your implementation of Huffman’s algorithm.

b) Answer the following: What data structures will you use to implement Huffman's algorithm? Why?

project-files