Problem: Mispellings (Part 2)

This course’s philosophy on academic honesty is best stated as "be reasonable." The course recognizes that interactions with classmates and others can facilitate mastery of the course’s material. However, there remains a line between enlisting the help of another and submitting the work of another. This policy characterizes both sides of that line.

The essence of all work that you submit to this course must be your own. Collaboration on problems is not permitted (unless explicitly stated otherwise) except to the extent that you may ask classmates and others for help so long as that help does not reduce to another doing your work for you. Generally speaking, when asking for help, you may show your code or writing to others, but you may not view theirs, so long as you and they respect this policy’s other constraints. Collaboration on quizzes and tests is not permitted at all. Collaboration on the final project is permitted to the extent prescribed by its specification.

Below are rules of thumb that (inexhaustively) characterize acts that the course considers reasonable and not reasonable. If in doubt as to whether some act is reasonable, do not commit it until you solicit and receive approval in writing from your instructor. If a violation of this policy is suspected and confirmed, your instructor reserves the right to impose local sanctions on top of any disciplinary outcome that may include an unsatisfactory or failing grade for work submitted or for the course itself.

Your work on this problem set will be evaluated along four axes primarily.

To obtain a passing grade in this course, all students must ordinarily submit all assigned problems unless granted an exception in writing by the instructor.

Let’s brush up on a few recent topics before diving in. First, join Jackson and Lauren for tours of singly linked lists and hash tables.

Then, brush up your valgrind knowledge with Nate!

If still desiring more practice with linked lists or hash tables, Doug is here to help!

Below are two options for getting started with this problem. The first option is for those who wish to start with the staff’s implementation of the features from Problem 5-5 already implemented for them. The second option is for those who wish to complete their own implementation of the spell checker, relying on their own solution to the first part of the problem as their foundation. Only choose one of the below two options.

Regardless, log into CS50 IDE and, in a terminal window, execute

to ensure that your workspace is up-to-date!

Alright, the challenge now before you is to implement load and size as efficiently as possible, in such a way that TIME IN load, TIME IN check, TIME IN size, and TIME IN unload are all minimized. To be sure, it’s not obvious what it even means to be minimized, inasmuch as these benchmarks will certainly vary as you feed speller different values for dictionary and for text. But therein lies the challenge, if not the fun, of this problem set. This problem set is your chance to design and optimize for the real world! Although we also invite you to minimize space, your ultimate enemy is time. But before you dive in, some specifications from us.

Alright, ready to go?

As before, be sure that your spell-checker doesn’t leak any memory at all. Know that valgrind watches for leaks while your program is actually running, so be sure to provide command-line arguments if you want valgrind to analyze speller while you use a particular dictionary and/or text, as in the below.

If you run valgrind without specifying a text for speller, your implementations of load and unload won’t actually get called (and thus analyzed).

And don’t forget about your other good buddy, gdb.

How to check whether your program is outting the right misspelled words? Well, you’re welcome to consult the "answer keys" that are inside of the keys directory that’s inside of your spelling directory. For instance, inside of keys/austinpowers.txt are all of the words that your program should think are misspelled.

You could therefore run your program on some text in one window, as with the below.

And you could then run the staff’s solution on the same text in another window, as with the below.

And you could then compare the windows visually side by side. That could get tedious quickly, though. So you might instead want to "redirect" your program’s output to a file (just like you may have done with generate in Problem Set 3), as with the below.

You can then compare both files side by side in the same window with a program like diff, as with the below.

Alternatively, to save time, you could just compare your program’s output (assuming you redirected it to, e.g., student.txt) against one of the answer keys without running the staff’s solution, as with the below.

If your program’s output matches the staff’s, diff will output two columns that should be identical except for, perhaps, the running times at the bottom. If the columns differ, though, you’ll see a > or | where they differ. For instance, if you see

that means your program (whose output is on the left) does not think that EVIL’s is misspelled, even though the staff’s output (on the right) does, as is implied by the absence of EVIL’s in the lefthand column and the presence of EVIL’s in the righthand column.

To test your code less manually (though still not exhaustively), you may also execute the below.

Note that check50 does not check for memory leaks, so be sure to run valgrind as prescribed as well.

How to assess just how fast (and correct) your code is? Well, as always, feel free to play with the staff’s solution, as with the below, and compare its numbers against yours.

This was Misspellings (Part 2).