Exam #3 Review: Main Topics 1. Be familiar with the basic operations we have per

Question

Exam #3 Review: Main Topics 1. Be familiar with the basic operations we have performed on tries: insertion, retrieval, and deletion. What is the Big-Oh runtime for each of these operations (best- and worst-case)? When deleting a string from a trie, in what cases can you actually delete nodes from the trie, and in what cases should you only change count/flag variables? Could you write a simple recursive function to traverse a trie? For example: Write a recursive function that determines how many words are represented in a given trie. What advantages does a trie have for storing strings when compared to, say, a binary search tree or a hash table? 2. What does it mean for a binary tree to be "complete?" What is the height of a complete binary tree with n nodes? (Derive an exact answer. Hint: You will need to use either a floor or ceiling.) (Related: What does it mean for a binary tree to be "full," and what does it mean for a binary tree to be "perfect?" (This is a carry-over from Exam #2 material, but is directly related to heaps.) 3. Be familiar with the basic properties of a heap (with respect to structure and ordering). Be familiar with the basic operations associated with heaps, and be prepared to trace through them on the exam. When we remove from a heap, how do we restore its heapiness? When we insert into a heap, where does the new node go, and again, how is heapiness restored? What are the Big-Oh runtimes for insertion into and deletion from a heap? What is the difference between a minheap and a maxheap? 4. How does the array representation for heaps work? How do we find parents, left children, right children and the bottom-right-most non-leaf node of a heap? Could you code up basic heap operations? What are the advantages and disadvantages of using an array instead of a node with left and right child pointers? In contrast, would the array representation be a good choice for a binary search tree? Why or why not? 5. Understand how heapify0 works, conceptually speaking. What is its Big-Oh runtime? 6. What is heapsort, and what is its Big-Oh runtime? What other sorting algorithms have we seen this semester with the same Big-Oh runtime? 7. Be familiar with the three collision resolution policies for hashing that we discussed in class: linear probing, quadratic probing, and separate chaining. What are the advantages and disadvantages of each? What are the best-, worst-, and average-case runtimes (Big-Oh) for insertion and retrieval using these methods? With separate chaining, does it make more sense to insert into the beginning of a linked list or the end? Why? What are the considerations here? 8. Be prepared to trace through insertion of elements into a hash table using these different collision resolution policies, showing where elements end up. Be careful to understand precisely how the probing mechanisms work 9. Be able to point out serious flaws or shortcomings in a hash function if presented with one on the exam. 10. With quadratic probing, how can we guarantee that insertion will find an empty position in the table, if there is one? 11. How does deletion from a hash table affect the algorithm for retrieving or searching for an element in that table? What mechanisms did we see to prevent deletion from being disruptive to our retrieval search algorithm? 12. If a hash table gets full and we decide to expand it, what special considerations are there? How does that process work?

Explanation / Answer

the worst case complexity for insertion is O(M). #M is length of a key
the worst case complexity for search is O(M).
the best case complexity for search is O(M) #Big-O only describes an upper bound on complexity.

following are the complete running code with

#include <iostream>
using namespace std;
#define NO_OF_WORDS 26
#define MAX_WORD_SIZE 100
// TrieNode structure
struct TrieNode
{
TrieNode* child[NO_OF_WORDS];
bool isEndOfWord;

// set(childNodes)-> NULL
TrieNode():isEndOfWord(false){
for(int i=0; i<NO_OF_WORDS; i++)
child[i] = NULL;
}
};
// it insert the word in Trie
void insert(TrieNode* root, char* word)
{
for(int i=0; word[i] != ''; i++)
{
if(root->child[word[i]-'a'] == NULL)
{
root->child[word[i]-'a'] = new TrieNode;
}
root = root->child[word[i]-'a'];
}
root->isEndOfWord = true;
}
// function to print the word found
void printWord(char* str, int n)
{
cout<<endl;
for(int i=0; i<n; i++)
{
cout<<str[i];
}
}
// it prints all words
void printAllWords(TrieNode* root, char* wordArray, int pos = 0)
{
if(root == NULL)
return;

if(root->isEndOfWord)
{
printWord(wordArray, pos);
}
for(int i=0; i<NO_OF_WORDS; i++)
{
if(root->child[i] != NULL)
{
wordArray[pos] = i+'a';
printAllWords(root->child[i], wordArray, pos+1);
}
}
}
// Checking wheather a word is present in the Trie or not
bool isValidWord(TrieNode* r, char* str)
{
if(str == NULL )
return true;
if(*str == '')
return r->isEndOfWord;

if(r->child[*str - 'a'] == NULL)
return false;
else
return isValidWord( r->child[*str - 'a'], str+1);
}
int main()
{
TrieNode* root = new TrieNode;

insert(root, "rad");
insert(root, "red");
insert(root, "read");
insert(root, "reading");
insert(root, "readymade");
insert(root, "readygarments");

char wordArray[MAX_WORD_SIZE];
printAllWords(root, wordArray);
}

// function to print the word found

void printWord(char* str, int n)
{
cout<<endl;
for(int i=0; i<n; i++)
{
cout<<str[i]<<" ";
}
}

// Print all words in Trie
void printAllWords(TrieNode* root, char* wordArray, int pos = 0)
{
if(root == NULL)
return;

if(root->isEndOfWord)
{
printWord(wordArray, pos);
}
for(int i=0; i<NO_OF_ALPHABETS; i++)
{
if(root->child[i] != NULL)
{
wordArray[pos] = i+'a';
printAllWords(root->child[i], wordArray, pos+1);
}
}
}

A Binary Search Tree is a tree data structure where we have constraint that each node can have maximum of two child node and left child will always be smaller than right child and parent node.
In a trie data structure we have maximum of 26 nodes where you can store data. Trie is a data structure with fast retrieval which facilitates faster access of an string/element.
For building a memory-efficient dictionary a Trie is a good data structure with auto-completion and fast lookups.but unlike a hashtable it allows you to iterate over the keys in sorted order.

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.