Country : Canada
Assignment Task
 



The dictionary implementation given assumes each word is a lowercase letter from "a" to "b". Suppose you were to change the implementation of the dictionary to include any unicode character. How would you change the Node definition to accommodate the extra characters?
Suppose you use a binary search tree to store the words from the dictionary.txt file. In the worse case scenario, how many comparisons would it take to find out if a word is in the dictionary?
Your answer here
Suppose you use a prefix tree to store the words from the dictionary.txt file. In the worse case scenario, how many comparisons would it take to find out if a word is in the dictionary using the Dictionary class?
Your answer here
Why is the prefix tree better than a binary search tree for implementing Boggle?
Your answer here
Suppose you do not use IsPrefix in your SolveBoard implementation.How would that affect the program?
Your answer here
Recommended Implementation Order
Dictionary Class (Part A)
This is the recommend implementation order for the Dictionary class.
Dictionary()
WordCount()
AddWord(string word)
IsWord(string word)
IsPrefix(string word)
LoadDictionaryFile()
Dictionary(string filename)
SaveDictionaryFile(string filename)
MakeEmpty()
Dictionary& operator=(const Dictionary& otherDict)
Boggle Class (Part B)
This is the recommended implementation order for the Boggle class.
The Dictionary class needs to work!
Boggle()
SetBoard(string board[BOARD_SIZE][BOARD_SIZE])
SolveBoard(printBoard, outfile)/SolveBoardHelperBoggle Solver
The Boggle board is a 4x4 grid onto which you shake and randomly distribute 16 dice. These 6-sided dice have letters rather than numbers, creating a grid of letters from which you can form words. In the original version, the players start simultaneously and write down all the words they can find by tracing by a path through adjoining letters. Two letters adjoin if they are next to each other horizontally, vertically, or diagonally. There are up to eight letters adjoining a cube. A grid position can only be used once in the word. When time is called, duplicates are removed from the players' lists and the players receive points for their remaining words based on the word lengths. In this assignment, you will be creating a program that will find all the words on a boggle board. Any word found in the dictionary will count as a word on the boggle board.
Boggle Game: https://www.youtube.com/watch?v=fQ9CRLVvl6oThis assignment is broken into two parts. The first part of the program will be creating a dictionary that can be used to store and look up words. This dictionary implementation will use a special tree called a prefix tree.
Part A: Dictionary
To store the words in this assignment, you will be creating dictionary using a data structure called a prefix tree (also known as a Trie). This data structure allows for the quick lookup of whether or not a word is valid. It will also allow you to find all words with a specific prefix. Rather than store each word individually, we instead store the words using a tree:

The example above shows two how the words "a" and "axe" are represented using a tree.
Each node holds 26 pointers to other nodes; each of these nodes corresponds to a specific letter.
Each node also holds a single boolean flag.
Essentially, each word is represented by a path down the tree.
If the path ends with a "false", then the path does not represent a valid word.
For example, the root node has a path from the first Node* pointer (i.e. the pointer representing 'a') to another Node. Notice that this first level node has a "true" flag. This indicates that "a" is a valid word. If we examine the pointer for the second level "x" position, we find that a path exists for "ax" to another node. When we examine this second level node, we find that the pointer for the 'a' position is NULL. This indicates that "aa" is not a valid word or prefix. If we examine the pointer for the 'e' position, we see that another node exists. When we look at this 3rd level node, we find that the flag for this position is true; this make sense since "axe" is a valid word. Notice that the 'a' Node pointer at the third level is NULL; this means that there is no word with a prefix of "axea". Similarly, since the node for 'z' at the third level is NULL, this means there is no word with the prefix "axez".
HINT: I highly suggest using the following tool to help you get a feel for how the data structure works.
https://www.cs.usfca.edu/~galles/visualization/Trie.htmlBigger Example: This is an example of the prefix tree with all of the words starting with the letter x from the boggle dictionary. The green nodes indicates that the path to that node is a word. For example, "xebec" is a word. (See the trie_x.pdf in the readme_images folder for a higher resolution image).

Prefix
A prefix is a valid path down the tree. A prefix may or may not be a valid word. For the example below, "a" and "ax" are valid prefixes since there are words starting with these letters. However, "aaa" is not a valid prefix. This because the path ends with a NULL.
Basic_Dictionary.cpp
The Basic_Dictionary.cpp can be used for development. It will not be used for grading. I suggest using this program first before running the Dictionary_tests.
Note: This program is a CMake Application. It will not show up as a Catch Application.


struct Node
Your Node structure should contain an array of pointers. The node can be a struct or class. The size of the array should be NUM_CHARS (ie 26). The struct/class should also contain a boolean flag called isWord to indicate if the path to this node represents a word.
HINT: You may want to consider having a default constructor for your node. This will decrease the amount of code you will need later. You can create a default constructor for a struct the same way you would for a class.
Dictionary() Default Constructor
The default constructor should establish a root node and make each position of the branch array null. It should also set the root isWord to false. The total number of words should be 0.
Hint: Having a default constructor for your node will reduce the code required for this function and other functions.
Dictionary& operator=(const Dictionary& otherDict)
This function should copy all of the values from otherDict to this instance of the dictionary. It will serve as a wrapper for copyHelper in a similar way we recursively copied a binary tree in class. The only difference is we have 26 children instead of two. Here is a rough algorithm:
operator=(const Dictionary& otherDict):
Make this of the instance empty copy over the numWords from otherDict
for each letter
call copyHelper with the correct parameters

return this instancecopyHelper(Node*& thisTree, Node*& otherTree):
This code is very similar to a binary tree.
The only difference is you need to copy 26 branches instead of 2 branches.
Make sure you also copy the isWord parameter over too.
WARNING: DO NOT JUST SET THE ROOTS EQUAL!
In other words, DO NOT do the following:
root = otherDict.root; // DON'T DO THIS!!!
This will cause both dictionaries to share the same root!
void MakeEmpty()
The MakeEmpty function should destroy all the nodes in the tree. After destroying all the nodes in the tree, the root should be remade and the number of words should be set back to 0. MakeEmpty mainly serves as a wrapper function for the destroyHelper. The MakeEmpty and destroyHelper functions work very similarly to the binary tree deconstructor covered in class. The only difference is that you need to destroy 26 branches before deleting the current node.
Dictionary(string filename)
This constructor should establish a root node similar to the default constructor. After that, it should open the file filename and add all the words in this file to the dictionary.
HINT: There may be a function that you already wrote to help you with this. This constructor should have very few lines of code.
void LoadDictionaryFile(string filename)
This function should open the file filename and add all the words in this file to the dictionary. This function does NOT reset the words in the dictionary. It just adds to the words already in the tree.
void SaveDictionaryFile(string filename)
The SaveDictionaryFile function should use a recursive function to find every word in the tree and save it to a file. This function mainly serves as a "Wrapper" for the SaveDictionaryHelper function. The following is a rough algorithm:
SaveDictionaryFile(filename):
Open the file if the file fails to open:
throw a DictionaryError with the message filename+"failed to open"
Call SaveDictionaryHelper with the appropriate arguments
HINT: What should the prefix be at the root? A path down the tree represents a word. If you have a path that ends at the root node, what word does that represent? Think about this when you set your prefix in the first call to SaveDictionaryHelper called in SaveDictionaryFile.
SaveDictionaryHelper(curr, currPrefix, outFile):
Basecase (for you to figure out)

if the current node represents a word
output the word to the file
for each letter:
Call SaveDictionaryHelper with the appropriate arguments
HINT: How should the prefix change in each call to SaveDictionaryHelper? Be sure to look at how we tracked the path in the maze example. This strategy can also work here.
void AddWord(string word)
This method adds a word to the tree. This is accomplished by reading the word character by character and creating a path in the tree for the word if it doesn't exist. Below is the pseudocode for this method:
currNode = root;for (each character c of the word) {
if (the branch for character c is NULL) {
set the branch of character c = new Node.
set flag of this new Node to false }
currNode = the pointer index of character c
}
Set the flag at the currNode to trueHere is some code that will help you loop through each character of a string.
// How to loop through each letter of a word
string str = "hello";for (int i = 0; i < str.size(); i++) {
cout << str[i] << endl;}
While processing the characters, if you encounter a character that is not between 'a' and 'z', you should throw a DictionaryError with the message "Invalid character".
bool IsPrefix(string word)
This method returns true if a path down the branches exists for a word. This method will have an implementation very similar to the AddWord method for traveling down the tree. It should return false if it runs into a NULL. If it manages to get through the entire loop without hitting a NULL, it should return true.
While processing the characters, if you encounter a character that is not between 'a' and 'z', you should throw a DictionaryError with the message "Invalid character".
bool IsWord(string word)
This method is very similar to the AddWord and IsPrefix method. If you have already implemented the IsPrefix method, then it should be fairly trivial to implement isWord. The main difference is you should return the isWord flag found of the node found at the end of the path.
While processing the characters, if you encounter a character that is not between 'a' and 'z', you should throw a DictionaryError with the message "Invalid character".
 

 

 


This Academic Assignment has been solved by our Academic Experts at UniLearnO. Our Assignment Writing Experts are efficient to provide a fresh solution to this question. We are serving more than 10000+Students in Australia, UK & US by helping them to score HD in their academics. Our Experts are well trained to follow all marking rubrics & referencing style.
    
Be it a used or new solution, the quality of the work submitted by our assignment Experts remains unhampered. You may continue to expect the same or even better quality with the used and new assignment solution files respectively. There’s one thing to be noticed that you could choose one between the two and acquire an HD either way. You could choose a new assignment solution file to get yourself an exclusive, plagiarism (with free Turnitin file), expert quality assignment or order an old solution file that was considered worthy of the highest distinction.

Eureka! You've stumped our genius minds (for now)! This exciting new question has our experts buzzing with curiosity. We can't wait to craft a fresh solution just for you!

  • Uploaded By : Roman
  • Posted on : September 07th, 2019

Whatsapp Tap to ChatGet instant assistance