Held: Wednesday, 19 November 2014

Back to Outline 43 - Analyzing Procedures. On to Outline 45 - Pause for Breath.

Summary

We consider association lists, a simple, but useful, technique for organizing tables of information.

Related Pages

• Reading: Association Lists
• Lab: Association Lists
• EBoard 44 (Source 44) (HTML 44)

Overview

• Storing information in tables.
• Representing table entries as lists.
• Representing tables as lists.
• Association lists: Scheme's standard table representation.
• Implementing key association list procedures.

Administrivia

• Continue lab partners. Friday wiil be with project group.
• Quiz topics: Randomized drawing, Higher-order procedures, analysis, association lists.
• Reminder: Review sessions on Wednesday (8pm) and Thursday (10am and 8pm)!

Upcoming Work

• Lab writeup: Exercises 1 and 4c: http://bit.ly/151-2014F-w44
• No reading for Friday. Friday is a project work day.
• Part two of the project due next Tuesday.
• Nothing due the week after Turkey break.
  
  • We may distribute exam 4 next Wednesday for those who want to use break time to work on the exam. But it will be designed as if we distributed it immediately after break.

Extra Credit Opportunities

Academic

• CS Extras Thursday (tomorrow): Text Recognition in Maps
• CS Table Friday: One Year After Healthcare.gov
• CS Extras Tuesday the 25th: Summer Opportunities in CS

Peer Support

• Karan's radio show 11pm Thursday nights on KDIC
• Evan's radio show 5pm Friday nights on KDIC
• Donna's radio show Sunday midnight on KDIC
• One acts, coming soon
• Swimming and Diving at Loras on Saturday

Miscellaneous

• VP Student Affairs Candidate Open Sessions
  • Wednesday, 4:15, JRC 209
  • Friday, 4:15, JRC 209

Simple Database Problems

• Databases are among the most common applications of computers.
  • After all, there's a reason that Larry Ellison is nearly as rich as Bill Gates.
• A database is a mechanism for storing data so that you can easily access the data you need.
• One simple database activity is looking up values by keys.
• Databases that provide only that activity are called dictionaries.

Association Lists

• In Scheme, dictionaries are typically implemented with a data structure known as the association list.
• An association list is a list of elements each of which has a key as its car.
• You can use the (assoc *key* *list*) procedure to look up values by key.

Searching in Association Lists

• Suppose Scheme didn't include assoc. How would you write it? Probably recursively.
• If the list is empty, it does not contain the value.
• If the key of the first element in the list is the key we're looking for, return the corresponding value.
• Otherwise, look in the rest of the list.
• This technique is called sequential search.

Variants of Association Lists

• Given that we can write our own assoc procedure, we can easily implement a number of interesting variants of association lists.
• For example, if the same key appears multiple times in the association list, we might return all matching values (rather than the first matching value).
• Similarly, instead of searching by key, we might search by predicate.

Lab

• Do the lab