What is meant by an immutable data type?
An object is immutable if its data-type value (state) never changes once it is constructed.
A data type is immutable if every object of that type is immutable.
For example, to make the
Autocomplete data type immutable, you must make a
defensive copy of the
terms array in the constructor (because the client
might change one of the entries in the original
terms array after constructing the
Can my methods have side effects that are not described in the API?
No. For example, the
Autocomplete data type should not
change one of the entries in the
(or it could have a serious side effect on the client).
should not change the entries in their argument arrays.
We usually allow methods to have benign side effects,
such as changing the state of a random number generator.
What is the meaning of the modifier
static in the following function declarations?
It means that there is one (static) method for the entire class, as opposed to one (instance) method per object. Since there is a single total order (by weight), the static modifier is appropriate.public static Comparator<Term> byReverseWeightOrder()
Can a nested class have a constructor and instance variables?
Recall your nested iterator class in
What is lexicographic order?
(or alphabetical order) is a total order in which strings of characters are ordered
based on the position of the characters in the underlying alphabet (such as the Roman alphabet, ASCII, or Unicode).
To determine which of two strings comes first, you compare the first characters of the two strings.
If they differ, the string whose first character appears earlier in the alphabet comes first.
If the first characters are the same, you compare the second characters, and so forth.
If you reach a position where one of the two strings has no more characters, the shorter string comes first.
"cat" is less than
"dog" is less than
How can I compare two strings lexicographically?
Lexicographic order is the natural order for Java strings, so you can use the
String to do so.
What exactly does it mean to compare two string by their first r characters?
You should compare the two strings lexicographically, as in the
for Java strings, but you should never examine beyond the first r characters
of either string. For example, if r = 3, then
"cat" is less than
"dog" is equal to
"do" is less than
Note that in the last example,
"do" has fewer than 3 characters, so we compare the
"do" to the first 3 characters of
What is the meaning of the type parameter
Key in the following function declaration?
This is an example of a generic method, which introduces its own type parameterpublic static <Key> int firstIndexOf(Key a, Key key, Comparator<Key> comparator)
Key. The type parameter serves as a placeholder for the argument types that are passed to the generic method. In this case, it enforces the constraint that the type of the elements in the array
amust match the type of the search key
key(so that the compiler would allow
Orange). This bit of Java minutiae is necessary to enable the program to compile without warnings.
When I compile
BinarySearchDeluxe.java I get the compiler warning
"unchecked call to compare(T, T) as a member of the raw type java.util.Comparator."
Is that OK?
No, your program should compile without any errors or warnings.
Can I use
Arrays.binarySearch() returns the index of any matching key—not
necessarily the first or last such key. So, it will not be of much help.
Can I assume that the weights are all distinct?
No. However, if there are two terms with equal weights, the
can return them in arbitrary order.
Can I assume that the
Autocomplete constructor receives the
terms in descending order by weight?
No. While many of the sample input files are in descending order by weight, do not
make any assumptions about the order.
allMatches() return if there are no matching terms?
It should still return an array containing all of the matching terms—an array of length 0.
Autocomplete be case sensitive? For instance,
if I enter in the prefix "prince" and if one of my terms has a query "Princeton",
should "Princeton" be included among the matches?
On this assignment, case matters. In a real application, you might want a case-insensitive
or diacritic-insensitive order.
Can a prefix or query string be the empty string?
Yes and yes. For example, the empty-string prefix
return all queries, in descending order by weight.
It might be harder to think of an application for an empty-string query, but the
API does not exclude this possibility.
What do I need to do to handle Unicode characters and UTF-8 encoding?
You shouldn’t need to do anything special:
String data type handles Unicode naturally;
The supplied test files are encoded using UTF-8.
When reading input or writing output,
StdOut assume UTF-8 encoding.
Why do I get a
when I run the sample client?
Did you cut-and-paste the file instead of downloading it? Your text editor may have corrupted
the file by changing the encoding from UTF-8 to something else.
How can I view the Unicode characters that my program prints out?
chcp 65001. Use the font Lucida Console (or some other font that supports Unicode).
AutocompleteGUI: should work without adjustment.
Input files. Below are some input files for testing. Each input file consists of an integer n followed by n pairs of terms and integer weights, one pair per line, with the term and weight separated by a tab. The terms can be arbitrary strings consisting of Unicode characters, including spaces (but neither tabs nor newlines).
file number term weight source pu-buildings.txt 166 Princeton buildings age (in Y10K) pokemon.txt 729 Pokemon popularity Allen Qin fortune1000.txt 1,000 company revenue Fortune 1000 nasdaq.txt 2,658 NASDAQ market cap nasdaq.com metal-albums.txt 3,000 metal albums votes Metal Storm pu-courses.txt 6,771 course enrollment Princeton Registrar wiktionary.txt 10,000 word frequency Wiktionary redditors.txt 10,000 reddittor subscribers redditlist.com baby-names.txt 31,109 first name frequency U.S. Social Security trademarks.txt 92,254 company U.S. trademark number USPTO cities.txt 93,827 city population geoba.se mandarin.txt 94,339 Mandarin word frequency Invoke IT bing.txt 250,000 word Bing search frequency Microsoft Web N-gram 2grams.txt 277,718 2-gram frequency Google Web Trillion Word Corpus 3grams.txt 1,020,009 3-gram frequency Corpus of Contemporary American English 4grams.txt 1,034,308 4-gram frequency Corpus of Contemporary American English 5grams.txt 1,044,269 5-gram frequency Corpus of Contemporary American English words-3333333.txt 333,333 word frequency Google Web Trillion Word Corpus artists.txt 43,849 music artist familiarity Million Song Dataset songs.txt 922,230 song hotttnesss Million Song Dataset alexa.txt 1,000,000 web site frequency Alexa imdb-votes.txt 82,455 movie number of votes Internet Movie Database movies.txt 229,447 movies revenue (USD) Internet Movie Database actors.txt 2,875,183 actors revenue (USD) Internet Movie Database
These are purely suggestions for how you might make progress. You do not have to follow these steps.
implements Comparable<Term>to the class declaration and implement the
byReverseWeightOrder(). In support of this method, you will need to define a private static nested class, as in the lecture slides.
byPrefixOrder(). In support of this method, you will need to define another private static nested class. Since you will need to create a comparator that depends upon an integer parameter r, the nested class should have a constructor that takes r as an argument and saves it in an instance variable.
BinarySearchDeluxe.java. Binary search is a deceptively simple algorithm. Jon Bentley reports that in an experiment at Bell Labs and IBM, only about 10% of professional programmers got it right; so, test, debug, test.
BinarySearchDeluxe.java, you need a data type with an associated comparator. You could use
Termand one of its comparators. Note that the
compare()method associated with this comparator may return a value other than –1, +1, and 0.
hito see where it stalls.
Autocomplete. You will need to use all three orders defined in
Term: the natural order, reverse order by weight, and lexicographic order based on the first r characters.
Comparator<Term> comparator = Term.byReverseWeightOrder();
Arrays.sort(terms)to sort the array
termsaccording to the natural order (by query string) and
Arrays.sort(terms, comparator)to sort the array
A video is provided for those wishing additional assistance. Be forewarned that video was made in early 2014 and is somewhat out of date. For example the API has changed.
Suppose that I want to find only the top-k matching terms (instead of all matching terms). Are there better algorithms? Yes. The problem of finding the top term matching a given prefix can be formulated as a range maximum query problem or equivalently as a lowest common ancestor problem. Here are some lecture notes by Erik Demaine on the equivalence.
Any way to find the range of words that start with a given prefix in time proportional to the length of the prefix (in the worst case)? Yes, use a suffix tree (or a suffix array with the lcp array), where the terms are separated by a word-separation symbol and concatenated together. To use space proportional to the number of terms consider a suffix array on words. Or consider a compact DAWG.