Question
Need some java help with a question for my program. Im still fairly bad with recognizing order of growth operations in programs so I am
Need some java help with a question for my program. Im still fairly bad with recognizing order of growth operations in programs so I am hoping you can show me the number for each
Question;
1. What is the order of growth of the number of compares (in the worst case) that each of the operations in the Autocomplete data type make, as a function of the number of terms n and the number of matching terms m?
Recall that with order-of-growth notation, you should discard leading coefficients and lower-order terms, e.g., m^2 + m log n.
a)constructor:
b)allMatches():
c)numberOfMatches():
Program
public class Autocomplete {
private Term[] arrayTerms;
// Initializes the data structure from the given array of terms.
public Autocomplete(Term[] terms) {
if (terms == null){
JOptionPane.showMessageDialog(null, "There are no terms", "No Terms", JOptionPane.ERROR_MESSAGE);
throw new NullPointerException("There are no terms");
}
this.arrayTerms = terms;
//orders the array of terms
Arrays.sort(arrayTerms);
}
// Returns all terms that start with the given prefix, in descending order of weight.
public Term[] allMatches(String prefix) {
if (prefix == null){
throw new NullPointerException();
}
Term temp = new Term(prefix, 0);
int begin = BinarySearchDeluxe.firstIndexOf(arrayTerms, temp, Term.byPrefixOrder(prefix.length()));
int end = BinarySearchDeluxe.lastIndexOf(arrayTerms, temp, Term.byPrefixOrder(prefix.length()));
if (begin == -1 || end == -1){
JOptionPane.showMessageDialog(null, "Nothing matches that term", "No Matches", JOptionPane.ERROR_MESSAGE);
throw new NullPointerException("Nothing matches that term");
}
Term[] matches = new Term[end - begin + 1];
matches = Arrays.copyOfRange(arrayTerms, begin, end);
Arrays.sort(matches, Term.byReverseWeightOrder());
return matches;
}
// Returns the number of terms that start with the given prefix.
public int numberOfMatches(String prefix) {
if (prefix == null){
JOptionPane.showMessageDialog(null, "Nothing with that prefix", "No Matches", JOptionPane.ERROR_MESSAGE);
throw new NullPointerException("Nothing with that prefix");
}
Term temp = new Term(prefix, 0);
int begin = BinarySearchDeluxe.firstIndexOf(arrayTerms, temp, Term.byPrefixOrder(prefix.length()));
int end = BinarySearchDeluxe.lastIndexOf(arrayTerms, temp, Term.byPrefixOrder(prefix.length()));
return end - begin + 1;
}
public static void main(String[] args){
// read in the terms from a file
String filename = "wiktionary.txt";
In in = new In(filename);
int N = in.readInt();
Term[] terms = new Term[N];
for (int i = 0; i < N; i++) {
long weight = in.readLong(); // read the next weight
in.readChar(); // scan past the tab
String query = in.readLine(); // read the next query
terms[i] = new Term(query, weight); // construct the term
}
// read in queries from standard input and print out the top k matching terms
int k = Integer.parseInt("10");
Autocomplete autocomplete = new Autocomplete(terms);
while (StdIn.hasNextLine()) {
String prefix = StdIn.readLine();
Term[] results = autocomplete.allMatches(prefix);
for (int i = 0; i < Math.min(k, results.length); i++)
StdOut.println(results[i]);
}
}
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started