Review for final -- PIC10C, Spring '98

Below is a list of topics which should serve as a study outline for you as you make sure you've covered all of the bases in studying for the final. It may or may not be completely comprehensive. If you have any questions about any of this, please email me. Where page numbers are given, they are references to Carrano (unless otherwise stated) and refer you to the part of the reading assignments dealing with the particular issue. --Ami

Contents:

Hashing
Heaps, priority queues
Sparse Matrices
Graph algorithms
Pointers to functions
Math stuff

Hashing
Hash Functions
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

Resolving Collisions
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

Effeciency
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

Hash table Traversal: Just say no?
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

Heaps, priority queues

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.

See pp.539-555 for details.
Back to table of contents

Sparse Matrices

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

Graph Algorithms

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

Pointers to Functions

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

Math stuff

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