Held: Friday, 15 November 2013

Back to Outline 40 - Designing a Dictionary API. On to Outline 42 - Implementing Dictionaries with Binary Search Trees.

Summary

We consider some basic implementations of dictionaries.

Related Pages

• Lab: Linked Dictionaries
• Code: https://github.com/Grinnell-CSCS207/linked-dictionaries
• EBoard (HTML) (PDF)

Overview

• Implementing dictionaries, mark I.
• Looking ahead: A better implementation.

Administrivia

• Have you decided upon a site for the course and who gets to make the site?
• Reminder: Next Tuesday we're going to the Digital Commons roundtable.
• I'm going to drop the homework due the week after Thanksgiving so that you can have a better Thanksgiving break.
• I thought it would be useful to remind you of why I teach the way I do.
  • I think you learn a technique better if you've thought about the problem before hearing/reading a solution. (And you learn it even better if you develop it yourself.)
  • While I think it's important that you know how to implement and use key data structures and algorithms, I think it is equally important that you learn techniques that you can apply as you design and build your own algorithms and data structures. (Yes, even though there are many built in to Java and other languages, sometimes efficiency is such a concern that you'll really want to implement a structure that is tuned to your usage.
    • Plus, interviewers expect that you have these skills.
• Upcoming extra credit opportunities:
  • National Philanthropy Day, today (Donate to a charity of your choice)
  • NO CS TABLE THIS WEEK!
  • Innovation Class, Friday, 12:45, ARH 302, Hilary Mason '00
  • Career Connections with Hilary Mason '00, Friday, 4:15-6:30 Burling Lounge
  • Swim meet, Saturday, 3pm
  • Digital Commons talk, Monday, November 18, 7:00 p.m. or so
  • CS Department Talk, Wednesday, November 20, noon
  • "Data Sovereignty: The Challenge of Geolocating Data in the Cloud", November 25, 4:15 JRC 101
  • "Gold Fever" by Andrew Sherburne '01 or so, 7:00 p.m., Monday, November 25, ARH 302
  • Tuesday, November 26, 4:15 p.m., JRC 209 a gaming event with the game [d0x3d!]

Implementing dictionaries, Mark 1

• The simplest approaches: Store key/value pairs in a list or array.
• Some of the same design questions as priority queues: Do we store them in order or unordered.
• For our sample version, we'll store them unordered.
  • get involves searching until you find a key or run out of elements
  • put involves adding it at an available spot
• We'll use linked nodes, with a dummy node at the front

Looking ahead: Implementing dictionaries, Mark 2

• Can we do better than O(n) for get? (Or, alternately, O(n) for for put, which still requires O(logn) for get?)
• What are techniques we've used for improving algorithms in the past?
  • Divide and conquer
  • Randomness and luck
  • Thinking outside of the box
  • ...
• What's a divide-and-conquer approach?
  • Looking up elements is like binary search
  • Can we build an easy to extend structure that mimics binary search?
  • Idea: Instead of having one link from each node, we have two: One for the smaller keys, one for the larger keys.
• We'll return to this approach on Monday.