Computer Science 15-111 (Sections A & B), Spring 2007

Class Notes:  23-Apr-2007

 

Logistics:

1.      Welcome to the homestretch!  (Whew!)

Topics:  Applications

1.      Hashtables Redux

a.      Chaining

                                                   i.      Each bucket contains a linked list (“chain”) of elements with same hash value

                                                 ii.      Worst-case depends on bucket-length, which can be fixed, so: O(1)

                                                iii.      If bucket length is not fixed, worst-case can be O(N) (with lousy hash function – would never happen in practice)

b.      Linear Probing

                                                   i.      No buckets, just an array

                                                 ii.      Hash value à index in array to start at

                                                iii.      Keep searching until you find the element or “null”

                                               iv.      Easier (though not much) to implement than chaining

                                                v.      For sparse enough hash table with good has function:  O(1) average case (good)

                                               vi.      However:  O(N) worst-case (bad).

2.      Heap Redux

a.      Build a heap of N elements with N inserts:  O(NlogN)

b.      Build a heap of N elements by bottom-up “build-heap” algorithm:  O(N)

c.      But heapsort is still O(NlogN),  as removing all N elements is O(NlogN) in any case.

3.      Prefix Dictionary Redux

a.      Vocabulary:  this is a trie  (see Wikipedia’s page on tries)

b.      But this is a 15-111 implementation, not a 15-211, so many simplifying assumptions allowed in your implementation.

4.      Problem-Solving with Search Redux

a.      Express a problem as a State Space:

                                                   i.      An Initial State, s0

                                                 ii.      A set of Goal States (g0,…gN)

                                                iii.      A function that takes a state and generates its children states (that is, the states that result from legal “moves” from the given state)

                                               iv.      And, sometimes (but not for depth-first or breadth-first search):  A Heuristic Function that computes how “good” a state is (you may think of this as how “far” the state is from a solution state).

b.      Generally, use a HashSet to avoid expanding duplicate states.

c.      State Space Search Algorithms:

                                                  i.      Depth-First Search  with a Stack

                                                ii.      Breadth-First Search with a Queue

                                              iii.      Best-First Search with a Priority Queue

1.      Uses the Heuristic Function’s value as the priority.

                                              iv.      A* Search

1.      An improvement over a simple Best-First Search

2.      Covered in an AI course (or on Wikipedia, of course!)

5.      Final Topics and Projects

a.      Othello?

b.      Lisp?

c.      Excel?