Difference between revisions of "CISC220 F2023 Lab10"
From class_wiki
(→1. Hash tables) |
(→1. Hash tables) |
||
| Line 8: | Line 8: | ||
The executable is called as follows: <tt>hashcheck <command filename></tt>. Each command file initializes a hash table from a dictionary on the first line: | The executable is called as follows: <tt>hashcheck <command filename></tt>. Each command file initializes a hash table from a dictionary on the first line: | ||
| − | * <tt>CHAIN filename</tt>: Count words in <tt>filename</tt>, compute appropriately-size hash table, call constructor of <tt>Chain_String_HT</tt> class which uses ''separate chaining'' for collision resolution, and insert every word into that hash table. Chains are implemented with STL <tt>vector</tt> class. Only output is printing <tt>WORD_COUNT TABLE_SIZE</tt> | + | * <tt>CHAIN filename</tt>: Count words in <tt>filename</tt>, compute appropriately-size hash table, call constructor of <tt>Chain_String_HT</tt> class which uses ''separate chaining'' for collision resolution, and insert every word into that hash table. Chains are implemented with STL <tt>vector</tt> class. Only output is printing the dictionary hash table's <tt>WORD_COUNT TABLE_SIZE</tt> followed by a newline |
* <tt>PROBE filename</tt>: Same as previous command but call constructor for <tt>Probe_String_HT</tt> class which uses ''quadratic probing'' for collision resolution. This scheme should use lazy deletion and follow the probing sequence ''f(1) = +1'', ''f(2) = -4'', ''f(3) = +9'', ''f(4) = -16'', and so on. | * <tt>PROBE filename</tt>: Same as previous command but call constructor for <tt>Probe_String_HT</tt> class which uses ''quadratic probing'' for collision resolution. This scheme should use lazy deletion and follow the probing sequence ''f(1) = +1'', ''f(2) = -4'', ''f(3) = +9'', ''f(4) = -16'', and so on. | ||
The initialization line is followed by 0 or more 1-argument "commands" (one per line) which will trigger calls to member functions of the hash table object: | The initialization line is followed by 0 or more 1-argument "commands" (one per line) which will trigger calls to member functions of the hash table object: | ||
| − | * <tt>INSERT word</tt>: Insert <tt>word</tt> into hash table following appropriate collision scheme. Update word count and table size variables as necessary. Once again, only output (after the insertion and bookkeeping) <tt>WORD_COUNT TABLE_SIZE</tt> | + | * <tt>INSERT word</tt>: Insert <tt>word</tt> into hash table following appropriate collision scheme. Update word count and table size variables as necessary. If the <tt>word</tt> is already in the table, don't insert a duplicate. Once again, only output (after the insertion and bookkeeping) <tt>WORD_COUNT TABLE_SIZE</tt> |
| − | * <tt>REMOVE word</tt>: | + | * <tt>REMOVE word</tt>: Remove <tt>word</tt> from hash table if it is there. Again output (after the removal and bookkeeping) <tt>WORD_COUNT TABLE_SIZE</tt> |
* <tt>FIND word</tt>: Using BFS, print length of shortest path connecting <tt>w1</tt> and <tt>w2</tt>. If they are not connected, print "NOT CONNECTED" | * <tt>FIND word</tt>: Using BFS, print length of shortest path connecting <tt>w1</tt> and <tt>w2</tt>. If they are not connected, print "NOT CONNECTED" | ||
* <tt>SPELLCHECK filename</tt>: Using BFS, print sequence of words on that path (one per line starting with <tt>w1</tt> and ending with <tt>w2</tt>). If they are not connected, print "NOT CONNECTED" | * <tt>SPELLCHECK filename</tt>: Using BFS, print sequence of words on that path (one per line starting with <tt>w1</tt> and ending with <tt>w2</tt>). If they are not connected, print "NOT CONNECTED" | ||
Revision as of 13:43, 30 November 2023
Lab #10
1. Hash tables
Starter code for an abstract class String_HT and two derived classes Chain_String_HT and Probe_String_HT is provided here. Several dictionaries ranging in size from 100 to ~84K English words, as well as text files for testing spellchecking, are also supplied along with the code.
The executable is called as follows: hashcheck <command filename>. Each command file initializes a hash table from a dictionary on the first line:
- CHAIN filename: Count words in filename, compute appropriately-size hash table, call constructor of Chain_String_HT class which uses separate chaining for collision resolution, and insert every word into that hash table. Chains are implemented with STL vector class. Only output is printing the dictionary hash table's WORD_COUNT TABLE_SIZE followed by a newline
- PROBE filename: Same as previous command but call constructor for Probe_String_HT class which uses quadratic probing for collision resolution. This scheme should use lazy deletion and follow the probing sequence f(1) = +1, f(2) = -4, f(3) = +9, f(4) = -16, and so on.
The initialization line is followed by 0 or more 1-argument "commands" (one per line) which will trigger calls to member functions of the hash table object:
- INSERT word: Insert word into hash table following appropriate collision scheme. Update word count and table size variables as necessary. If the word is already in the table, don't insert a duplicate. Once again, only output (after the insertion and bookkeeping) WORD_COUNT TABLE_SIZE
- REMOVE word: Remove word from hash table if it is there. Again output (after the removal and bookkeeping) WORD_COUNT TABLE_SIZE
- FIND word: Using BFS, print length of shortest path connecting w1 and w2. If they are not connected, print "NOT CONNECTED"
- SPELLCHECK filename: Using BFS, print sequence of words on that path (one per line starting with w1 and ending with w2). If they are not connected, print "NOT CONNECTED"
2. Programming tasks
These are core String_HT functions that are required but not directly tested. Since they don't generate output but have side effects on the data structures above, every print function should either call one of these or use the modified data structure(s).
- calculate_neighbor_words(string &)
- DFS_traversal(string &)
- BFS_traversal(string &)
These String_HT functions will be directly tested and correspond one-to-one with the commands listed above:
- [0.5 points] print_num_neighbors(string &)
- [0.5 points] print_neighbors(string &)
- [1 point] DFS_print_connected(string &, string &)
- [1 point] DFS_print_num_connected(string &)
- [0.5 points] BFS_print_path_length(string &, string &)
- [1 point] BFS_print_path(string &, string &)
- [0.5 points] BFS_print_longest_path()
You may use AI on any part of this lab, but no human partner.
3. Submission
Submit 2 files to Gradescope: (1) your README and (2) your modified main.cpp. The README should contain your name, complete declarations of AI use, notes on any limitations or issues with your code, and your interpretation of any ambiguities in the assignment instructions. main.cpp should also contain your name and per-function comments on AI usage.
