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; }