Could you have a dictionary of dictionaries? If so, how would that work and what is it good for?

Yes! You can have a key that maps to a dictionary value. They can be useful when a key is going to be pretty complex, or if you have a hierarchy of information. Graph data structures (for example, to describe airline routes or social networks) are often represented as a dictionary of dictionaries. Your Facebook account would have a key (your name) mapping to a dictionary of all of your friends. That dictionary would have a key (friend’s name) and a value (profile of your friend, or a dictionary of their friends).

Another example is to represent geographic locations. I could have a dictionary of countries, where the value is a dictionary of states (e.g., countries["United State"] = states). The states would be a dictionary of state names (the key) and values (a dictionary of cities). And so on. You could index through all of these countries["United States"]["Michigan"]["Ann Arbor"] to arrive at some value that we want to store (e.g., population size or name of Mayor).

When would a list be more preferable to a dictionary?

The sequential aspect is important. Maybe we need to know the order values were entered. Or enumerating a list is more important than searching through the list. If searching and pairs of information are not important, dictionaries are probably overkill.

why didn’t we use dictionaries instead of lists of lists/parallel lists before?

Dictionaries are better suited for showing relationships between items. However, most pieces of data are more appropriately stored under the random access model (i.e., lists). Lists (or arrays) are fundamental to computation at different levels, so being able to think about lists, and multi-dimensional lists (list of lists) is an essential skilling to mastering topics that come later in the curriculum. This is the first time I’ve taught dictionaries, which are very powerful, but not as fundamental to the field.

Why does checking for a key have a fixed time (i think you said that) ?

This requires a lot of discussion. But a dictionary is actually built on top of an array (which is very similar to a list). Rather than add items one at a time, we write a function called a hash that converts are key into a numeric value. This conversion is stable - the hash function will always return the same integer if you give the same input. For example, it might hash “Swarthmore” to the number 287610. It will then place “Swarthmore” at index 287610 is in the array. This process was done irrespective of the number of other items already in the dictionary.

This is a little hand wavy because there are more details that need to be dealt with (what if a hash function gives two different keys the same numeric value? Doesn’t this require a huge list to be created? What if we run out of room?). It takes a whole week in CS35 to cover!

How does searching in a dictionary work?

It’s pretty cool, but really advanced for an intro class. But I encourage you to read further about hash tables

Is there a way to sort a dictionary

No; we’d have to use the keys() method to get the keys as a list and then sort that.

What fields, other than biology, can computer science be applied to?

All of them. I’m applying for a digital humanities grant for a course I’m teaching philosophy next semester. Prof. Rachel Buurma in English does some pretty cool stuff with students that requires programming. The Linguistics department uses computer science to be understand language (Prof. Wicentowski teaches a course in our department on how to get computers to understand language). All science disciplines generate data and require tools to process and understand that data. The internet was invented because physicists created more data than they could carry back after an experiment was done!

What is bioinformatics?

The study of algorithms for modeling biological systems. This is now a huge umbrella term, but most of the core topics in this field deal with trying model similarity and evolution.

What are some examples of dictionaries providing an easier option than lists?

I think the examples we are doing this week work. The counting example is very similar to Lab 9, where you needed to keep track of the cumulative rating. We could have used dictionaries for that.

Are there any major downsides to using dictionaries?

Random access is impossible, so if iterating over the items or keeping track of the order of items is important, dictionaries are not a great choice.

So would this accumulation aspect of dictionary values suggest that they are mutable?

Great question! Yes, dictionaries are mutable.