Suppose you have a huge list of words (Strings) in an array called words[]. Any
ID: 662639 • Letter: S
Question
Suppose you have a huge list of words (Strings) in an array called words[]. Any given word might appear multiple times in the array.Use the array words[] and array indexing in your pseudocode. For best and worst case questions, we are looking for the number of array elements visited.
a) Write pseudocode for a boolean function that checks if a given word is in the array. What is the best and worst case of your function?
b) Write pseudocode for an integer function that returns the number of times a given word is in the array. What is the best and worst case of your function?
c) Write pdedocode for a function that returns the word that appears the most in the array. You can create temporary arrays in your function but cannot use any other data structures. What is the best and worst case of your function?
Explanation / Answer
(a) Psuedocode
boolean checkIfWordExists(String words[], String givenWord)
{
int n= words.size()
for i=0 to i=n-1
{
if words[i]==givenWord :
return True
}
return False;
}
best Case: The first element in words[] array is the required word. So only one element needs to be checked.
worst case : The required word does not exists in the words[] array. So all the words in the array need to be accessed to return False at the very end as the required word was not found.
(b)
(a) Psuedocode
int checkIfWordExists(String words[], String givenWord)
{
int n= words.size()
int numOfOccurrences=0
for i=0 to i=n-1
{
if words[i]==givenWord :
numberOfOccurences+=1
}
return numberOfOccurences
}
The best and the worst case is the same for the function as for any given word we need to traverse the whole word array as we need to count all the occurences of the given word so we need to check each word of the array.
String mostFrequentWord(String words[])
{
String mostFrequentWord;
int numberOfOccurences=0;
int n=words.size()
for i =0 to n-1
{
int tempNumberOfOccurences=0;
for j=0 to j=n-1
if words[i]==words[j]
tempNumberOfOccurences+=1
if tempNumberOfOccurences>numberOfOccurences
numberOfOccurences=tempNumberOfOccurences
mostFrequentWord=words[i]
}
return mostFrequentWord
}
Both the best and the worst case of the function will take n^2 time as each word is checked.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.