"Computer sciency" and "practical" exercices involving dictionaries

Question

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.

Answer 1

Some project ideas:

1. 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...?

2. 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.)

3. 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...

4. 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.)

5. 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...

6. 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.

Answer 2

Perhaps not really a solution to your problem, but definitely an answer to your question: almost anything written in a dynamically typed language, like JavaScript or Python, where dictionaries are ubiquitous.

It's pretty clear how using dictionaries make these languages work, and how they add to code flexibility.

Another very practical use of dictionary is straightforward serialization and de-serialization. Here dictionary allows abstracting all low level stuff to a standard library, and coping only with something reasonably well structured. Again, that's something that works best in dynamically typed languages, which can represent arbitrary JSON with standard structures. The exercise may involve storing some data (e.g. game saves), interacting with a REST API, or just processing some given JSON data.

Even if JavaScript is not the language you use, it may be feasible to run a live exercise simply in a browser console, to get some hands on experience.

Answer 3

Two ideas come to mind. For the CS-y version you could go with creating a file structure based on the MD5 sum of the files. Use the sun as the file name in the index with the given name stores in the attached data. The first two digits of the hex encoded sum, the file name, can be used as the two levels of the directory path where the file is stored. If the top level represents physical devices, then you get a roughly even distribution of files across the devices .

For a more practical, not that the first is not practical,. use Soundex for finding various spellings of the last names of the student body.