CS 70

Homework 8: Words That Don't Exist? Let's Hash it Out!

  • Dog speaking

    I'm starting a company, and it needs a name! Something that sounds like a word, but isn't one yet.

  • Duck speaking

    Like Kodak. Somebody made that up, and now it sounds like it was always a word.

  • Cat speaking

    We could write a program that makes up words. Count which letters follow which in a list of real words, then roll dice.

  • Goat speaking

    Counting things? Meh. Sounds like a lot of counting.

  • LHS Cow speaking

    Exactly! Which is why this homework's hash table is a counter.

In this eighth and final homework, you'll implement your own hash table class, HashMultiset<T>, which counts how many times each key has been inserted (like Python's Counter), and then use it to build a program that invents words: words that sound like they belong in a list of English adverbs, or Welsh villages, or company names, but aren't there. In doing this, you'll get to practice:

  • Analyzing hash functions and choosing the best one for the task.
  • Implementing a hash table using separate chaining.
  • Using a hash table to count a few hundred thousand things quickly.

HashMultiset, and the idea of putting it to work counting things in this assignment, come from Jonathan Chang's Spring 2026 version of Homework 8. The word generator is a letter-by-letter cousin of the text generator in chapter 3 of Brian Kernighan and Rob Pike's The Practice of Programming.

Getting Started

This assignment is paired, and your repository belongs to your pair. We have already made it—there is nothing to accept and no name to agree on. Your pairing (the same pair as Homework 7) came from the pairing board, and the repository is named after your group.

Both of you have push access to that one repository, so you are working in the same place rather than each having a copy to reconcile later.

  • Hedgehog speaking

    The link says the page doesn't exist!

  • LHS Cow speaking

    That usually means you are not in the CS 70 GitHub organization yet, rather than that your repository is missing. GitHub hides what you cannot see rather than admitting it is there.

  • Cat speaking

    So "not found" and "not allowed" look the same on purpose.

  • LHS Cow speaking

    Exactly—so that nobody can go fishing for the names of private repositories. On the server, cs70-fix-access will check your membership and sort most of this out for you.

Clone your repository on the CS 70 server to get started:

git clone https://github.com/hmc-cs70-fall2026/repo.git

Resources

Grading

This assignment is graded in these parts:

  • the written questions;
  • your code: the autograder (it builds without warnings, passes cpplint, has the right files, passes our tests of your hash table and your word generator, and your own tests catch our deliberately broken versions), and a code review of its clarity and style by the course staff;
  • your planning images (for completeness, not correctness);
  • your justification of your hash-function choice;
  • and, if you take one on, the optional bonus work (bonus points).

Each question shows its points beside it, on its own page, so there's only one place to look. Your grade for the assignment is the percentage of its points you earned, which is what the gradebook shows.

(When logged in, completion status appears here.)