Sets and Dictionaries
Almost everyone who has ever programmed has met arrays and lists, but many people have never met their associative cousins, sets and dictionaries. This lecture shows how they can simplify many common programming tasks.
Requires: basic programming
Introduces: sets; dictionaries; hash tables
Problem: What Molecules Can We Make?
Molecules’R'Us has hired you to write a simple inventory management program for them. Your program is supposed to read in a file describing how many atoms of various kinds are required to make different molecules, and another file describing how many atoms the company actually has in its teeny tiny warehouse, and then print out a list of the molecules the company could make.
Lectures:
- Introduction (pdf, ppt)
- Unordered collections
- Set operations
- Finding unique values
- Storage and Tuples: short version (pdf, ppt), long version (pdf, ppt)
- How sets are stored
- Why lists cannot be put in sets
- Using tuples instead of lists
- Dictionaries (pdf, ppt)
- Key/value pairs
- Dictionary operations
- Counting birds
- Examples (pdf, ppt)
- Using dictionaries to process data
- Nanotech Example (pdf, ppt)
- Using dictionaries to solve the original motivating problem
- Phylogenetic Trees (pdf, ppt)
- Using dictionaries to reconstruct the evolutionary history of a group of organisms
Exercises
Reading