Lecture 27 - December 3 – 2007

Go over quiz from November 28th - there were no questions

Go over quiz from today -         Question 11 from textbook about heaps

  • max heap has every parent greater than either of its children
  • all internal nodes are at the same level
  • leaf nodes are filled from left to right

 

Review graphs

            Parts of a graph

            Is there a path

            What is the shortest path

            What does a depth first search look like

            What does a breadth first search look like

            What does a directed graph look like?  (digraph)

            What does an undirec ted graph look like?

            What is a complete graph  - has an edge connecting every vertex with every other vertex

            What is a weighted graph -  has a value associated with each edge

 

Searching

            Binary search -  O(log2n)

·         the elements  being  looked through had to be ordered –

·          needs a storage structure with random access – an array

 

Sequential search  - O(n)

·         elements don’t have to be in order

·         storage structure can be a linked list or an array

 

            Interpolation Search

·         elements have to be ordered

·         like a binary search but takes advantage of where the element is expected to be found (i.e. towards the end or the beginning rather than starting to look in the middle)

 

I want a search that is O(1)

·         I look for the element  - one step, and find it or not

 

Introduce Hashing

·         uses the idea of key/value pairs

·         the value of the element to be stored determines the location where it is stored.

·         good hash functions are hard to find - where good means amount of unused space is as small as possible

·         when two values "hash" to the same location it is called a collision.

·         There are a number of methods of collision resolution

§         the one we used in class was linear probing

·         when a collision occurs, the value is placed in the first available space passed where it should have been stored.

·         when searching for a value, search until it is found or an empty space is encountered.

§         another one is called chaining

·         a linked list of the elements which hash to a given location is built. 

·         when searching for a value, search until it's found or encounter null.

 

·         In class hash table examples

First

·         we used an array holding 99 values with indexes from 1 to 99 and everyone chose a value. 

·         no collisions occurred because everyone gave a different value.

·         however, there were only 18 values and I used 99 spaces which isn't so good.

Second

·         suppose the keys are the letters of the alphabet and the values are last names

·         Hash example worked out in class (captured from Excel spreadsheet)

o        Note:  The Excel command is Format Cell Alignment (to rotate the text)

o        Note:  Explorer does not support the vertical text.  I'll show it in class on Wednesday or you can look at the spreadsheet.

o        HashExample.xls

·         lots of collisions

·         not so much empty space

 

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

z

akhmetov

bell

bryant

 

 

fujio

 

herman

hartway

jenkins

kelly

 

macdonald

 

 

parent

 

rodgers

stultz

smith

siltz

spiker

ward

sherman

watkins

 

 

Homework: 

  • read the lecture notes
  • read the section in the book on Hashing
  • review the material from the course, come in with questions