CSC122F2021Lb6 < CenterForComputing

Tags: view all tags
---+ Hash lab
---++ Learning Objective(s)
   1 Expand knowledge about organizing and searching data to hashing
   1 See the implications of Big O on real data, esp. on large amounts of data
   1 Learn to write a quality report analyzing amount of work.
---++ Overview of the problem
You are to expand the previous lab to also study hash tables.
---++ Specifics
   * Implement a hash table (including add and find methods).
   * Compares are the number of times an element in the hash table is accessed.
   * The hash function should be more complex than just mod'ing by table size
   * The data is in similar format to previous lab.  Use first file to build the hash table.  Use the second file to look for numbers in the hash table.
   * The integer is the key.
   * You may pick any collision handling method you wish.
   * Run the tasks on a decent number of cases including:
      * data that is almost in order
      * data that is almost in reverse order
      * data that is in random order
      * tiny amount of data in the first file (&lt; 100)
      * small amount of data in the first file
      * medium amount of data in the first file
      * large amount of data in the first file
      * a few numbers in the second file
      * a medium number of numbers in the second file
      * a large number of numbers in the second file
   * Number of classes
---++ Report
   * Run enough examples of each type to get a good set of data points.  (3 or 4 data points per type is not enough!)
   * Plot them on a graph (with the horizontal axis being the size of the data and the vertical being the number of comparisons and/or swaps)
   * Compare the generated results to the expected Big O results
   * Discuss the following:
      * How each algorithm compared to its Big O
      * When sorting first then searching is better than just searching
      * A comparisons of the sorts with each other
   * It is recommended that you use graphs in a spreadsheet to visualize the data
---++ Optional improvements
   * Compare results with different sizes of the table (related to the size of the input)
   * Compare different hashing routines
   * Compare different collision handling routines
Topic revision: r1 - 2021-11-10 - cathybareiss