Held: Friday, 18 September 2015

Back to Outline 09 - Hash Tables. On to Outline 11 - Binary Search Trees.

Summary

We consider some basic issues of the tree ADT and data structure.

Related Pages

Overview

• Hash Tables: Semi-Formal Analysis.
• Hash Functions and Hash Tables: Other Applications.
• Trees: The Basics.
• Balancing Trees.

Administrivia

Upcoming Work

• For Monday
  • Finish Skiena Chapter 3.
• For next Wednesday: HW 3a Implement chained/bucketed hash tables
  • In Scheme
  • With strings as keys
  • An arbitrary values as values
  • That grow when more than 50% full
  • And use the Skiena "sum of powers" for the hash function
  • Ideally, parameterize the "constructor" to allow changing some of these policies.
  • Ideally, with unit tests.
• For next Wednesday: HW 3b Design SetOfStrings Implementations
  • A SetOfStrings ADT provides
    • add(set,val), remove(set,val), contains(set,val)
    • union(set,set), subtract(set,set)
  • Describe three different reasonable implementations of SetofStrings. (You need not write code; just describe memory arrangement and related issues.)
  • For each, indicate the asymptotic cost of each method. In writing this, reflect on both the size of the set (n,m) and the size of the string (s).
    • This is an informal analysis question; no proofs necessary

Extra Credit

Academic

• Art opening (or any visit to the art show): Friday and beyond
  • Talk, 4pm, Sept. 18
  • Opening Reception, 5:00-6:30 p.m., Sept. 18
• John Gerrard talk, "Corn Bomb", Monday at 8pm
• No CS Table next week - It's advising week!
• Wednesday CS Extra Next week, 4:15 in 3821: Ursula Wolz on Building Coding Communities
• Thursday CS Extra Next Week, 4:15 in 3821: SamR on The Architecture of Mediascript

Peer

• DNP radio show at 11pm.

Hash Tables: Semi-Formal Analysis

• Proving that a hash function distributes values well is hard. Every hash function will have some sets of values for which it does poorly.
• One trick: If we have some randomization in our choice of good hash functions, we can argue that we are unlikely to get one that distributes our current input badly.
• So, given a good hash function, a probed hash table, and a requiremnt that the hash table is no more than half full, what can we say?
• Half the time, we'll find an empty spot. So 1/2 of the values take 1 step.
• In the other half, we rehash. Half the time, we'll find an empty spot. So 1/2 of the values take 2 steps
• In the other half, we rehash. Half the time, we'll find an empty spot. So 1/4 of the values take 3 steps.
• In the other half, we rehash,
• So 11/2 + 21/4 + 31/8 + 41/16 + 5 1/32 + 6/64 + ....

Hash Functions and Hash Tables: Other Applications

• What did you think about the examples from Skiena?

Trees

• What's a tree?
• What orders can we process the values in a tree?

Balancing Trees

• How might you balance an unbalanced tree?