CS 70

Written Questions

  • Pig speaking

    I already played with wordgen in Phase 8, but I want to play with it MORE!

  • LHS Cow speaking

    You're in luck!

In this week's written questions, you'll listen to your word generator more carefully, and look at what its hash table is doing.

  • RHS Cow speaking

    There'll also be some more "traditional" questions that ask you to look at and interpret graphs. After all, this assignment is still (ostensibly) about building data structures...

Exploration: Listening to the Model

All of these questions use wordgen from Phase 8, with your own WordModel and HashMultiset. Use -n to get more than ten words when you want a better sense of what a model does.

2 points

Question 1.1

Question 1.1 – By Ear

Run wordgen on the English list (ispell.words) with each context length from 1 to 5; for example,

./wordgen -k 1 -s 127 -n 20 /cs70/data/ispell.words

For each value of \( k \), describe in a sentence what the invented words are like, and give your favorite one. Then say what goes wrong when \( k \) is small, and what goes wrong when it's large. (Count the *s.)

  • Horse speaking

    Hay, wait! I trained a model on the verbs, and it "invented" band and rump. Those aren't new!

  • LHS Cow speaking

    They're new to the verbs list, which is all the model, and its words_ multiset, knows about. A word without a * is only "not in the list you trained on". Whether rump counts as an invention is up to you.

2 points

Question 1.2

Question 1.2 – What Makes a Word Sound Like That?

/cs70/data/wordlists has English words sorted by part of speech. Train one model on the adverbs and another on the adjectives, with the default \( k = 3 \):

./wordgen -s 86 -n 20 adverbs
./wordgen -s 86 -n 20 adjectives

What did each model learn about how its kind of word is built, especially how it ends? Give two invented words from each that show it.

Now pick another list (another part of speech, one of the other lists in /cs70/data/wordlists, or a list you make yourself) and do the same: what does a word need, to sound like it belongs on that list?

Deeper Dive: The Vollantry

Years ago, Prof. O'Neill wrote a story opening in which nearly every important word is invented, and the story still makes sense, because the invented words follow English's rules for building words:

Traspard Polinson was the son of a crearter, the great Grufough Polinson. In the family tradition, and his father's ablently tortered shadow, he had taken up scriting, loddying and perlying. For scriting, his favorite ablizer was a set of brass trempons. Those who knew enough not to mistake them for cievions or tringons thought them ophously Norgical, what with the Crellesic trussings, but few could have found something better for quirfing with acrinity. No trempons were better suited to Posson's Catraver, but these days that syclaria was frowned on as being too inglatic and relegory. Now, gesility was in, and sellazed tringons trumped brass trempons among the lagiggly femiline wheigmen of Curtland.

You know that ablently and ophously are adverbs, that Norgical and inglatic are adjectives, and that scriting, loddying and quirfing are things a person does, without knowing what any of them mean. That's the same knowledge your adverb and adjective models picked up from their counts.

Her own continuation was a love story:

His beloved, Ethertra Claremez had grown up plocking for moadwage on the streets of Baysweld, and had risen to being a conapper for the Rebroper Syndicate, which she later described as "musledge, mazzling and malifece". But somehow she had met Cariette Rouseley, herself a mere cimper's daughter, who had risen to being a grativer's suittess, and with her help she had escaped the Rebroper Syndicate, free of mulation. It was Cariette who introduced Ethertra to Traspard, a match surely entabled by the Gods of Auscrole. Initially, she regarded him as entirely joutable, "as coagless as a matilder's foreecat" were her exact words, but she grew to find him not as cogibled and insiumsy as she had thought, and seeing his maristic side, soon they were beflumed in love.

A few years ago, she gave the first paragraph to a large language model of the time (OpenAI's text-davinci-002) and asked it to continue. It, too, followed the rules, and found the jokes:

Loddying was a whole other mire of worgles. His father had always used a blatherwhip, but that had fallen out of favor since the Skellic Uprising. The new thing was the kippler, but Traspard found that to be more trouble than it was worth. The kippler was always getting tangled in his hair, and when it did work it was so loud that it gave him a headache. So, he stuck with the blatherwhip.

  • Cat speaking

    Our model only knows letters, and it already knows what an adverb sounds like.

  • Dog speaking

    Could we write a Vollantry with our own invented words?

  • LHS Cow speaking

    That's one of the More Fun options!

1 point

Question 1.3

Question 1.3 – The Table Behind It

Look at the statistics wordgen prints for the English list, for each \( k \) from 1 to 5. Why is the number of n-grams counted the same for every \( k \), while the number of different n-grams grows so fast? And what does that growth do to your hash table?

Now try your table with a bad hash function: make myhash in stringhash.cpp return str.length() for a moment (as Phase 8 suggests), and run ./wordgen -s 127 /cs70/data/ispell.words again. What happens to your table's statistics, and to how long wordgen takes, and why? (Then put your own hash function back.)

Comparisons

1.5 points

Question 2.1

Here's a plot of the time performance of insert, adding \( n \) ints to a set. The numbers are inserted in increasing order. The myhash function is trivial, just returning the unmodified integer.

The plot shows time per item, with lines for two variants of HashMultiset<int> (our sample solution, with maximum load factors of 0.75 and 2.0) and for std::unordered_set<int>, which is also a hash table. For contrast, we have also included std::set<int>, which is based on a red-black tree. (The \( n \) axis has a log scale.)

Time per insert, in nanoseconds, against n on a log scale, for n ints inserted in increasing order: HashMultiset with maximum load factors 0.75 and 2.0, std::unordered_set, and std::set

What can you conclude about the performance of all three hash table implementations? (std::set uses a tree, not a hash table)

The graph is consistent with a single insert in a hash table with \( n \) items requiring (expected amortized) …

1.5 points

Question 2.2

The above test filled the hash table buckets rather unrealistically, as they were filled sequentially due to the trivial hash function and the sequence of increasing integers.

If we used a better hash function or inserted random integer values, values would be distributed randomly across buckets and it would be a more realistic test.

The graph below shows the results of such a test:

Time per insert, in nanoseconds, against n on a log scale, for n random ints: HashMultiset with maximum load factors 0.75 and 2.0, std::unordered_set, and std::set, on the same scale as the previous plot

Notice that, apart from std::set on the very smallest sets, all the methods are running more slowly in this graph. (Compare the scales on the two vertical axes.)

Which explanation for this graph seems most plausible:

1 point

Question 2.3

Why do you think languages like Python use hash tables to implement their dictionaries rather than trees?

To Complete This Part of the Assignment…

You'll know you're done with this part of the assignment when you've done all of the following:

(When logged in, completion status appears here.)