CS 201 - 12/4/14
Final Exam: Monday 12/8/14 at 10:30am in SH 304
You are allowed to bring two sides of 8.5x11 inch paper
with whatever notes you deem proper
Topics:
Data Structures: Hash tables
- Closed hash Table
- Open hash Table / hash Table with chaining
- collisions (probing for unused positions in
a closed hash table)
- clustering - the use of a hash function that
does not give an even distribution
of array indices
Coding Question:
write the exists() function for a hash table with
chaining
Given: linked list structure
struct list
{
dataType data;
struct list *next;
}
hash table structure
struct Hash
{
int arraySize;
struct list **hashArray;
}
in the above hashArray is a dynamic array
of pointers to a linked list
Run Time of Algorithms
O ( 1 ) or O(C) - best
O ( log(n) )
O ( n )
O ( n log(n) )
O ( n * n ) "n squared"
O ( n * n * n )
O ( 2 ^ n ) " 2 to the n " / exponential -worst
linear search O( n )
binary search O( log(n) )
selction sort O( n*n )
quicksort O( nlog(n) )
Logic, propositional and predicate
propositional - statement are symbolized
with a single term
predicate - statement are smbolized
with a function and argument
Dave is tall
-proposition: t
-predicate: t(D)
Advantage: predicate logical allows for
univeral instantiation (for all...) and
existential instantiation (There exists ...)
Write out symbolized forms of statements
Rules of Inference
Use in a logic proof
Difference between inference statements and
the contrapositive (valid)
the converse (invalid)
the inverse (invalid)
In the past, I have given some statements
get to a particular conclusion
======================================
tree
struct tree
{
dataType data;
struct tree* left;
struct tree* right;
}