CSC301.01 2015F, Class 10: An Introduction to Trees
===================================================

_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
---------------