Contents:

A hash function maps a key to an address. Ideally it should be very fast, and produce well-scattered results for both random input data *and* for non-random input data. See p.614-615 for a lengthy discussion of what constitutes a good hash function.

Back to table of contents

We have seen two collision resolution schemes:

- Open Addressing: if a data item needs to be inserted in a location already taken, another location is found in the hash table for the item, using linear/quadratic probing, double hashing, increasing the size of the table, or another scheme.
- Use buckets: Instead of having just one data item at each location, implement the table by having each location of the array point at a linked list (or other variable-size data structure -- trees work well here), and when collisions occur, just throw the new data item into the corresponding list/tree.

Back to table of contents

Seperate chaining comes out on top in almost every respect when comparing the different methods of collision resolution and their effeciency. However, one must remember that there is storage overhead in maintaining the lists/trees that is otherwise negligible for arrays. Make sure you understand the "alpha" analysis of hashing/collision resolution schemes on p.611-614.

Back to table of contents

Any function that is going to need an operation of the type "give me the next item in the table" is going to have very bad performance under a hash-table implementation. This is because the keys used to hash the values are not linearly stored in the array, and there is no way to recover this information quickly. As a result, traversal, range extract, smallest/largest value find, and other operations like these make using hash tables much less attractive than they would otherwise be.

Back to table of contents

- Know how heaps are implemented using array-based storage
- Be able to find children/parent of a given array entry:
Parent(slot n) = floor((n-1)/2) Left_Child(slot n) = 2*n + 1 Right_Child(slot n) = 2*n + 2

- A node at level h (where the root is at h=0) and i'th in its level (where the first node in a level has i=1) will be in slot 2^h-2+i
- Understand Horner's Rule, esp. as it relates to computing hash values of strings
- Understand heapsort.

Back to table of contents

- Implementation details. Sorted list of sorted lists vs. arrays.
- Understand the operator(int i, int j) implementation.
- Which implementation gives immediate access to what stuff?
- Which of Sparse/Dense supports finding all neighbors best? Which is best for finding whether an edge exists?

Back to table of contents

- DFS and BFS traversal algorithms and spanning tree generation.
- element() and operator() functions. Understand symmetry and how it simplifies our lives when using sparse matrices.
- MST -- understand pseudo-code and actual C++ code (from PHW#4) (Prim's algorithm).
- Shortest path -- Dijkstra's Algorithm. Understand WHW#4's proofs and such.
- Understand heap use in MST process.

Back to table of contents

- The name of a function is a pointer to it. So if you declare a function foo(), then foo is the address for it. (foo == &foo)
- Basic usage:
double (*fptr)(char, int, float)

declares fptr as pointer to function (char, int, float) returning double. For a never-ending supply of laughs, run the program "cdecl" on one of the UNIX machines on PICnet, and enter something like:explain void (*fptr)(char, float)

To go from an english description to C code, type:declare fptr as pointer to pointer to function (function returning int) returning double

The output will be:double (**fptr)(int ())

- For more info on this, see p.156ff in Stroustrup.

Back to table of contents

- Horner's rule
- Geometric series: 1+r+r^2+r^3+...+r^n=(1-r^(n+1))/(1-r), 1+r+r^2+r^3+...+r^n+...=1/(1-r), 1^2+2^2+3^2+4^2+...+n^2=(n*(n+1)*(2n+1))/6.
- Understand Gaussian Elimination and how sparse mat's have specialized pivot selection algorithms.
- Know the operation count for Gaussian Elimination for Dense Mat's.

Back to table of contents