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