Program #4 Solution

Description

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 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:  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/BRKauEJp skip 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 –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.

 

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 a make clean  if it seems to be acting “oddly”.

 

 

 

 

Graph.h

 

Implement Warshall’s and Floyd’s (all your code goes in Graph.h)

 

Things to note:

 

• Fill out getTransitiveClosure() in Graph.h

 

• Make sure you’re looking at the pseudocode on pg 307

 

• Do this “in place” – modify the original Boolean adjacency matrix (book talks about different matrices).

 

• You index a vector just like an array.

 

• The adjacency matrices are in row, column order so R[2] is the third row of R (where R is a (Boolean) adjacency matrix) and R[2][3] is the fourth item on the third row (0-indexed).
• Skim, at least, the Graph code and make sure you know how it works – look at the targetgtest.cpp for more, too.

 

• Code it up and the first two test should pass.

 

• These tests are from the slides (look at the names)

 

Floyd’s – All Pairs Shortest Paths

 

• Code up Floyd’s in getAllPairsShortestPaths()

 

• Pseudocode is on pg. 310

 

• Remember: Floyd’s uses a distance matrix (all 0s on diagonal).

 

• Run the tests and Floyd’s should work as well (it has two tests as well, also from the slides).

 

 

 

 

SBTreeHash.h

 

 

Input to all three functions is a vector<string>.

 

You need to return an  ana_result struct which will have its  found field set to  false if there are no anagrams in the input and  true otherwise. If an anagram is found, then the  s1 and  s2 fields should be set to the strings. For anagram checking, you may just sort the string’s characters and compare for equality (assumption is that there are many  short strings).

 

Note that, for time comparison reasons, there are 4 tests all put together, the first of which generates the problems and the next three which test each approach. If the corresponding test passed, you get that 20 points… we have to look at the code anyway, so the score will be adjusted.

 

anyAnagramsSorting()

 

• Use std::sort to sort the vector of strings and see if there are any anagrams.

 

• There are several strategies here.

 

• It is important to remember that you must return the original ,  unsorted strings if you find anagrams. You are sorting both the entire vector (presorting strategy) and, probably, the strings individually for comparison purposes.

 

• Defining your own comparison function is likely necessary. Lambda functions are desirable here.

 

 

anyAnagramsMap()

 

• As above, except using std::map

 

• My times are somewhat slower than for sorting… but close.

 

 

 

anyAnagramsHash()

 

• As above, except using std::unordered_map

 

• My times are somewhat faster than for either of the above.

 

• My answer is very close to anyAnagramsMap()

 

 

 

 

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.