Program 2 350 Solution

(second GitHub assignment… putting instructions on Google Drive so I can edit quickly)

Please e-mail me if you don’t see your e-mail in the list and do it from your USC e-mail. Also, include your GitHub Username. 
Description:
You will code Heapsort, an Anagram checker, and three binary search tree algorithms.
This is a shorter than usual because you may need more time to get your environment setup (you need Linux).Your code must run on the department Linux machines (1D43). If you have a separate Linux installation that you want to use, ssh over to the department machines to make sure nothing breaks or just go visit them.

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:
Create an account on Github, if you haven’t already.

Go to this URL: https://classroom.github.com/a/tv_3kuxq
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 --edit  and 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 (cd into the cloned directory first):
python3 score.py

You should see, “SCORE= 0” before you get any work done (one basic test will pass and, well, welcome to Git(Hub) if you’ve never been here before). 

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-2-<username>
mkdir build && cd build
cmake ..
make
./runUnitTests

    • Question 1: Implement Heap Sort (algs.h)
        ◦ You should use std::priority_queue (already #included from <queue>)
        ◦ See: https://en.cppreference.com/w/cpp/container/priority_queue
        ◦ See: http://www.cplusplus.com/reference/queue/priority_queue/priority_queue/
        ◦ My implementation, including a closing brace, is 5 lines. DRTW
    • Question 2: Implement an Anagram Checker (algs.h)
        ◦ Your function, given two strings, should return true if two strings could be anagrams of one another or false otherwise
        ◦ You can assume all strings are composed of characters ‘A’..’Z’
        ◦ Your answer must run in O(m+n+k) time, where m and n are lengths of the two strings and k is the number of characters in the character set (26, here). This means:
            ▪ You cannot sort the strings with a typical sort
            ▪ You cannot traverse the strings more than a fixed number of times (you can do this by visiting each string character exactly once)
            ▪ A helper function is a good idea here (to convert characters to something…)
    • Question 3: Implement num_nodes(tree.h)
        ◦ It returns the number of nodes in the tree
    • Question 4: Implement has_duplicate_val(tree.h)
        ◦ It returns true if the tree has duplicate values/keys in it, false otherwise
    • Question 5: Implement trees_identical(tree.h)
        ◦ It returns true if the two trees, passed as pointer parameters are the same in structure and node values, false otherwise.

Test as above, one last time all five tests should pass.

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.