"Computer sciency" and "practical" exercices involving dictionaries I am teaching a course in data structures to a 2o semester.

We hear often that the dictionary is a very versatile data structure, and solves quite so many problems. I'd like to illustrate that, but, unfortunately, find myself lacking some interesting problems.

I am looking for two kinds of problems: "computer sciency" and more "practical".

For a "computer sciency" example, I already have "anagrams", in which you count the letters of two strings to check if they are anagrams of each other.

For a more "practical" example, I already have a dependency tree: You have a discipline, and it lists its name, its code and the codes of its dependencies, and the point is to print a tree of dependencies, using indentation.

I'd love more ideas, though.
Some project ideas:


Implement a very basic programming language. Write the parser for them, but have them manipulate the AST (eval expressions, perform constant folding, etc). (So hey, trees are a thing...) And of course, all programming languages have variables. How do we store variables? Hey, wouldn't having dictionaries be useful...?
Use dictionaries to implement a "sparse vector" class. Use the sparse vector class to implement TF-IDF and cosine similarity. Then, use TF-IDF/cosine similarity to implement a search engine. If the students are unfamiliar with linear algebra, you can skip the "sparse vector" bit and have them implement TF-IDF directly.

Bonus! Have the students also implement page rank, which ties in to graphs. 

(Want to integrate even more concepts? Have them write their own sorting algorithms to sort the final results. Go even further? Rather then using a sorting algorithm, have them implement top-k-sort on top of a heap so they efficiently select just the top k results in worst-case O(nlog(k)) time.)
Have them implement literally anything related to graphs. After all, you can pretty much always get away with implementing an adjacency list as just a dictionary of keys to some collection (a list or a set). This means that any problem where you manipulate an adjacency list can also be a dictionary assignment in disguise.

And there's a huge wealth of interesting graph problems out there -- have them implement pathfinding on a map of your local city using Dijkstra's, have them generate interesting and randomized mazes by adapting some MST algorithm, have them analyze a DAG, etc...
If you also want to integrate a bit of systems, you could maybe have the students implement a simplified version of Git. After all, git is just a DAG and all graph problems can be turned into dictionary problems. (It's also an interesting application of hashing!)

You'll probably need to give them code to do file IO for them, and maybe handwave or simplify the whole merge business, depending on how complicated it ends up being. (Or maybe not? I don't know much about the merge algorithms git uses, but it's entirely possible they could end up being interesting applications of dictionaries in their own right.)
A simpler assignment (more for CS 2 students): have the students read in simplified grammars in BNF format. Then, recursively (and randomly) traverse that grammar and generate some output. Have the students invent their own grammar -- there's room for creativity here. You could generate randomized poetry, randomized programs, etc... 
Have the students do something with n-grams and Markov chains. As before, this is really just a graphs assignment in disguise -- each node is an n-gram; you store a weighted edge from one n-gram to the next.

If you want to stick with the whole "secretly a graphs" thing but keep the math part light, have the students use Markov chains to generate text. You can have a lot of fun with this -- feed in Shakespeare to generate vaguely Shakespeare-ish text, feed in your Facebook data to generate text that sounds like you... You can also experiment with doing this on a character level and try feeding in corpuses from different languages. As it turns out, auto-generated English is pretty distinct from auto-generated French.

The algorithm to do this ends up being pretty similar to how you do the BNF thing since it's just randomized graph traversal. If you wanted to make a point about the importance of abstracting and refactoring code/adapting to sudden changes in the project spec, you could perhaps tie it in here (though tbh it feels a little contrived/might be more trouble then it's worth though).

Alternatively, if you want to avoid graphs but don't mind bringing in some stats, have them do basic basic classification instead, and give them a taste of machine learning. (E.g. can you classify spam emails vs non-spam emails? Can you classify which human language some text likely came from based on letter frequencies, character n-grams, and so forth?). 

My memory is a little hazy here, but I think you don't really need a graph (explicit or implicit) and just need a way of storing a discrete probability distribution. (And a dictionary is great way of doing that -- map n-grams to the probability that n-gram occurs.)


Disclosure: I did variations of assignments 1, 2, and 3 for a data structures course I just finished teaching + made them multi-week partner projects. They went reasonably well, though #1 may have been a tad ambitious.