Program 5 Solution

$35.00

Category: Tag:

Description

Description:

You will code Warshall’s, Floyd’s and then use sorting (std::sort), std::map (self-balancing tree), and unordered_map (hash table) to tell if an input vector of strings contains a pair of anagrams, returning the pair.

Please read, or at least skim, if you haven’t: Segfault troubleshooting strategies

SSH Instructions:

In Putty/MobaXTerm/WinSCP/Bitvise/… or just plain SSH to l-1d43-XY.cse.sc.edu​​on port 222

  • first character is a lowercase L

  • XY=01 | 02 | … | 36

If you’re off campus, you will need to have Duo 2 Factor Authentication setup.

From a non-lab Linux machine can ssh -p 222 <username>@l-1d43-XY.cse.sc.edu

Instructions:

Go to this URL: https://classroom.github.com/a/9IkK2Y8Yskip the e-mail selection… your GitHub and school e-mail addresses should be associate by now) Accept the Assignment

Follow the second link to the assignment.

Click on “Clone or download”

Copy the link

(if you’re remoting into the Linux labs, login and then switch to your ssh connection here) <navigate to wherever you want to work>

git clone <the url>

The assignment repositories are private, so you’ll need to login.

git config –global –editand edit the file (you probably did this already)

You can run the scoring function that builds and runs the tests for you and prints the score for you by running the following command (cdinto the cloned directory first):

python3 score.py

You should see, “SCORE= 0” before you get any work done.

You can run the unit tests directly without using the score function (not necessary) with the following command, also from the downloaded directory.

cd program-_-<username> (written generically)

mkdir build && cd build

cmake ..

make

./runUnitTests

Do amake clean if it seems to be acting “oddly”.

Program 5 – Huffman Trees-specific info

  • Problem Description:

  • Implement getHuffCodes() function.

  • It takes as input a vector of CFreq structs (defined in header) and returns a vector of CCodes (also defined in header).

  • Note that there are two stages to getting character codes for a given set of characters:

      1. Build the Huffman Tree

      1. Assign Codes to each character (some ambiguity here – can always flip 0 and 1 and get another acceptable set of codes). The tests take this into account.

  • The one hard condition for Huffman Codes is that no code is a prefix of another – Huffman codes are prefix-free codes.

  • Read the code – both the unit tests (targetgtest.cpp and program4.cpp)

  • You may put all your code in program4.h or separate into separate files in /src directory.

    • I will overwrite your targetgtest.cpp,score.py, and CMakeLists.txt file.

    • I will not overwrite anything else in the directory (don’t touch googletest, obviously)

  • You may use any standard library function that doesn’t build the Huffman trees or trivialize the problem for you. Specifically, I am suggesting that you remember or consider that:

you may (should) use std::priority_queue

you need to use std::vector at least for input and output

you may use a stack if you like (or recursion, easier) for assigning codes

Committing (backup and submission)

When I’m done or want to backup (git is for version control) I just git add .

git commit -m “<some message>” // “final submission” makes sense if you’re done git push origin master

We will grade the last submission up to the deadline (the very last submission until we won’t accept it anymore, possibly with a late penalty).

No need to submit code to dropbox.