Difference between revisions of "CISC220 F2021 Lab8"

From class_wiki
Jump to: navigation, search
(Created page with "==Lab #8== ===1. Written problems=== Suppose you want to ''hash'' words into a hash table of size ''m''. Let ''v_i'' be the English alphabet place value of the ''i''th lett...")
 
Line 1: Line 1:
 
==Lab #8==
 
==Lab #8==
  
===1. Written problems===
+
==Project #2==
  
Suppose you want to ''hash'' words into a hash table of size ''m''.  Let ''v_i'' be the English alphabet place value of the ''i''th letter in a q-letter word W, where the value of 'a' = 0, 'b' = 1, ..., 'z' = 25.  One possible hash function is
+
===1. Maze generation using union/find===
  
h(W) = [v_0 + v_1 + ... + v_(q-1)] mod m
+
As discussed in class, the union/find data structure can be used to generate rectangular mazes using grid cells as the set elements and connectivity as the equivalence relation. Three approaches were outlined:
  
For example, if m = 11 and W = "abc", then h("abc") = [0 + 1 + 2] mod 11 = 3
+
* Knock down random walls one at a time until the START and FINISH are connected.  Nothing else is considered
 +
* Same as above, but now only knock down a wall if the cells on either side of it are NOT already connected
 +
* Same as above, but only stop on the condition that the maze is solvable AND that every cell in it is connected to every other cell 
  
Assume m = 11 and you have the following list of words, in order:
+
Two classes are provided in starter code [http://nameless.cis.udel.edu/class_data/220_f2014/code/maze.tar here]: Maze and UnionFind.  UnionFind is a stub for the union/find data structure which uses an array to represent the equivalence class trees, and Maze is just a data structure to represent and draw N x M grids with walls (see the comments in maze.hh for details).  A sample 3 x 4 maze is shown below:  
  
# dog
+
#########
# duck
+
#S|    #
# cow
+
# +-+ + #
# mouse
+
#  | |F#
# horse
+
# +-+ +-#
# sheep
+
#      #
# goat
+
#########
# chicken
 
# pig
 
  
Please answer the following questions about the hash function, table, and list of words above.  Feel free to write a short program to ensure that your calculations are correct. 
+
You have several programming tasks:
  
* '''(2 points)''' What are the "home positions" of every word?  That is, what indices do they hash to before collisions are resolved? Either show your work or include your program code in the PDF.
+
* '''[0.5 points]''' Fill in the ''find()'', ''union_sets()'', and ''union_sets_by_size()'' functions in unionfind.hh. All of these functions were given in class (the last two were called union() and union_by_size(), but ''union'' is a reserved keyword in C++).
* '''(1 point)''' Show the final hash table if the words are inserted in the order above using ''separate chaining'' for collision resolutionEach chain should be an unordered, singly-linked list with the newest item being inserted at the head of the list.
+
* '''[1 point]''' There's a starter function called ''knock_down_all_walls()'' already provided in main.cppThis simply knocks down random walls one at a time until they're all gone, drawing the current "maze" M after each step.  The union/find data structure U which is associated with M is NOT updated, however.  Fill in appropriate calls to find() and union_sets() in knock_down_all_walls() so that U IS updated after each wall is removed (this is called "option 1" in the code).
* '''(1 point)''' Show the final hash table if the words are inserted in the order above using ''linear probing'' with a step size of 1What is the total number of probes beyond the home position for each word?
+
** Take a look at the helper functions in maze.hh called ''UF_index_to_rowcol()'' and ''row_to_UF_index()'' for going back and forth between referring to a grid cell by its row and column vs. by its index in the union/find array.
* '''(1 point)''' Suppose the table is ''rehashed'' during linear probing when the load factor exceeds 0.5. Let the new table size be 23, the smallest prime number greater than 2m.  Show the new hash table both right after rehashing AND after all the words have been inserted.
+
* '''[1 point]''' Write ''knock_down_til_solvable'' in main.cpp (first bullet above, but "option 2" in the code).   
 +
* '''[1 point]''' Write ''knock_down_til_solvable_better'' in main.cpp (second bullet above, "option 3" in the code)
 +
* '''[0.5 points]''' Write ''knock_down_til_all_connected'' in main.cpp (last bullet above, "option 4" in the code)
  
===2. Submission===
+
===2. Testing===
  
* Make a '''PDF file''' <Your Name>_Lab8_README.pdf with your answers to the written exercises
+
* '''[0.5 points]''' Show sample mazes generated by YOUR solutions to options 2, 3, and 4 for the 5 x 5 default option and something larger, like 8 x 16.  You do not need to show intermediate versions of the mazes as they are generated--just the final version.
* No need to compress or archive the PDF, since that's all you're turning in.
+
* '''[0.5 points]''' Generate (but don't show) a 100 x 100 maze 10 times using option 4, WITH and WITHOUT smart union.  What is the min, max, and average '''height''' of the one remaining equivalence class tree over those 10 runs (again, with and without smart union)?  '''NOTE: height is not the same as size!  You will need to write your own function to compute the height of your final tree'''
* Submit it in Canvas by ''midnight at the end of Thursday, November 20''
+
 
 +
===3. Submission===
 +
 
 +
* Make a '''PDF file''' <Your Name>_Lab8_README.pdf with your output mazes (clearly labeling which option gave rise to which) and answers to the height questions above
 +
* Rename your code directory <Your Last Name>_Lab8 and create a single tar/zip/rar file out of it named <Your Last Name>_Lab8.tar (or .zip or .rar, etc.).  
 +
* Submit it in Canvas by ''midnight at the end of Tuesday, November 9''

Revision as of 12:34, 3 November 2021

Lab #8

Project #2

1. Maze generation using union/find

As discussed in class, the union/find data structure can be used to generate rectangular mazes using grid cells as the set elements and connectivity as the equivalence relation. Three approaches were outlined:

  • Knock down random walls one at a time until the START and FINISH are connected. Nothing else is considered
  • Same as above, but now only knock down a wall if the cells on either side of it are NOT already connected
  • Same as above, but only stop on the condition that the maze is solvable AND that every cell in it is connected to every other cell

Two classes are provided in starter code here: Maze and UnionFind. UnionFind is a stub for the union/find data structure which uses an array to represent the equivalence class trees, and Maze is just a data structure to represent and draw N x M grids with walls (see the comments in maze.hh for details). A sample 3 x 4 maze is shown below:

#########
#S|     #
# +-+ + #
#   | |F#
# +-+ +-#
#       #
#########

You have several programming tasks:

  • [0.5 points] Fill in the find(), union_sets(), and union_sets_by_size() functions in unionfind.hh. All of these functions were given in class (the last two were called union() and union_by_size(), but union is a reserved keyword in C++).
  • [1 point] There's a starter function called knock_down_all_walls() already provided in main.cpp. This simply knocks down random walls one at a time until they're all gone, drawing the current "maze" M after each step. The union/find data structure U which is associated with M is NOT updated, however. Fill in appropriate calls to find() and union_sets() in knock_down_all_walls() so that U IS updated after each wall is removed (this is called "option 1" in the code).
    • Take a look at the helper functions in maze.hh called UF_index_to_rowcol() and row_to_UF_index() for going back and forth between referring to a grid cell by its row and column vs. by its index in the union/find array.
  • [1 point] Write knock_down_til_solvable in main.cpp (first bullet above, but "option 2" in the code).
  • [1 point] Write knock_down_til_solvable_better in main.cpp (second bullet above, "option 3" in the code)
  • [0.5 points] Write knock_down_til_all_connected in main.cpp (last bullet above, "option 4" in the code)

2. Testing

  • [0.5 points] Show sample mazes generated by YOUR solutions to options 2, 3, and 4 for the 5 x 5 default option and something larger, like 8 x 16. You do not need to show intermediate versions of the mazes as they are generated--just the final version.
  • [0.5 points] Generate (but don't show) a 100 x 100 maze 10 times using option 4, WITH and WITHOUT smart union. What is the min, max, and average height of the one remaining equivalence class tree over those 10 runs (again, with and without smart union)? NOTE: height is not the same as size! You will need to write your own function to compute the height of your final tree

3. Submission

  • Make a PDF file <Your Name>_Lab8_README.pdf with your output mazes (clearly labeling which option gave rise to which) and answers to the height questions above
  • Rename your code directory <Your Last Name>_Lab8 and create a single tar/zip/rar file out of it named <Your Last Name>_Lab8.tar (or .zip or .rar, etc.).
  • Submit it in Canvas by midnight at the end of Tuesday, November 9