Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Hash Tables: Semi-Formal Analysis
• Hash Functions and Hash Tables: Other Applications
• Trees: The Basics
• Balancing Trees

Preliminaries

Admin

• Have a good weekend!

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.
• Monday 7-10 Sound Art Projects in JRC
• EE Show in Smith starts Monday!

Questions

• Picnic is in ground-floor lobby.

Hash Tables: Semi-Formal Analysis

With a good hash function, set is expected O(1); worst case is O(n), where n is the number of slots in the hash table.

Assumption one: Hash function distributes things appropriately. For any input, there are equal odds that it goes in any of the n slots.

Assumption two: There are no more than n/2 values in the hash table. (Alternately: n values in the hash table, at least 2n slots in the hash table.)

Assumption three: Probed hash table.

First time we look in the hash table: 50% we find an empty slot

• 1 step * 1/2
• 2 step * 1/4
• 3 step * 1/8
• 4 step * 1/16

Average number of steps

    1*n/2 + 2*n/4 + 3*n/8 + 4*n/16 + 5*n/32 + ...
    Average = ^/n
    1*1/2 + 2/4 + 3/8 + 4/16 + 5/32 + ...

    Sum from k = 1 to infinity of k/2^k

    1/2 + 1/2 + 3/8 + 4/16 + 5/32 + ...
    1 + 3/8 + 4/16 + 5/32 + ...
    1 + 10/16 + 5/32 + ...
    1 + 25/32 + 6/64 + ...
    1 + 56/64 + 7/128
    1 + 119/128 + 8/256

    1 + (2^k-(k+2))/2^k

Never reaches 2, although gets arbitrarily close

The stuff before the ellipses 1 + 56/64 + 7/128...

Hash Functions and Hash Tables: Other Applications

I have a string, big, of length n. I have another string, small, of length k < n. Does small appear as a substring of big?

What's your strategy?

What's a really bad input for your strategy?

Strategy O

• See if it matches at position 0
• See if it matches at postiion 1
• See if it matches at position 2
• See if it matches at position 3
• Bad case: big is aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab small is aaaaab
• O(n*k)

Strategy H

• Compute the hash code of each substring of big of length k and shove into a hash table
• Compute the hash code of small, see if it's there
  • k steps to compute each hash code
  • approximately n different hash codes
    • O(n*k)

With the cool Skiena hash function, what do we know about hash(substring(str, 0, k)) vs hash(substring(str, 1, k+1))

• We found a cool formula

  hash(substring(str, 1, k+1) =
    (hash(substring(str, 0, k) - str[0]*alpha^k )* alpha + str[k+1]
  

So we can compute the n different hash codes in O(n + k) time = O(n) time

But ... we have to use a hash table. And if we have to create a hash table, We're using a lot of extra space! (Probably O(n) space.)

There's often a time/space tradeoff in your algorithms

Trees: The Basics

A tree is "a graph with no cycles"

A tree is "a collection of values such that with a hierarchial relationship"

Each value may have one or more children (child values) and at most one parent value. The relationship is symmetric relationship: if a is a child of b, then b is a parent of a.

Goal for Monday: Work on terminology and notation; Think about traversal; Think about balancing techniques

Balancing Trees