Frequently Asked Questions (WordNet)

Can I read the synset or hypernym file twice? No. File I/O is very expensive; read each file only once and organize the data in appropriate data structures.

Any advice on how to read and parse the synset and hypernym data files? Use the readLine() method in our In library to read the data one line at a time. Use the split() method in Java's String library to divide a line into fields. You can find an example using split() in Domain.java. Use either Integer.parseInt() to convert String id numbers into int values or Integer.valueOf() to convert into Integer objects.

Which data structures should I use to store the synsets, synset ids, and hypernyms? This part of the assignment is up to you. You must carefully select data structures to achieve the specified performance requirements.

I want a symbol table that maps each key to multiple values. How can I accomplish that? You can use a standard symbol table whose value type is a collection (such as a queue).

What should sca() return if there is a tie for the shortest common ancestor? The API does not specify, so you are free to return any shortest common ancestor.

Should nouns() return each distinct noun once? Or multiple times if the noun appears in multiple synsets? The API says to return the set of nouns, so no duplicates.

Can I assume that the nouns in a synset appear in the file in alphabetical order? No. Do not make this assumption.

Should nouns() return the nouns in alphabetical order? The API does not specify, so you are free to return them in any order.

Do I need to store the glosses? No, you won't use them on this assignment.

How large is the WordNet DAG? The WordNet DAG has 83,127 synsets, 85,441 hypernyms, and 120,119 distinct nouns. Your program must work for any valid synset and hypernym files, so do not hardwire these constants in your program.

What is the root synset for the WordNet DAG?

38938,entity,that which is perceived or known or inferred to have its own distinct existence (living or nonliving)

Can a synset contain more than one noun? Yes, a synset is a set of one or more nouns that are interchangeable in some context. For example ASL American_sign_language is a synset containing the two nouns ASL and American_sign_language.

Can a noun contain underscore characters? Yes. For example, American_sign_language is one noun.

Can a noun contain spaces? No.

Can a noun appear in more than one synset? Yes, absolutely. It will appear once for each of the noun’s distinct meanings. For example, the noun word appears in these 8 synsets:

36467,discussion give-and-take word,an exchange of views on some topic; "we had a good discussion"; "we had a word or two about it"
57522,news intelligence tidings word,information about recent and important events; "they awaited news of the outcome"
60202,parole word word_of_honor,a promise; "he gave his word"
60400,password watchword word parole countersign,a secret word or phrase known only to a restricted group; "he forgot the password"
82510,word,a brief statement; "he didn't say a word about it"
82511,word,a string of bits stored in computer memory; "large computers use words up to 64 bits long"
82512,word,a unit of language that native speakers can identify; "words are the blocks from which sentences are made"; "he hardly said ten words all morning"
82513,word,a verbal command for action; "when I give the word, charge!"
Do not assume that the number of synsets in which a noun participates is bounded by a constant. The noun head appears in 33 synsets.

Can a synset consist of exactly one noun? Yes. Moreover, there can be several different synsets that consist of the same noun, each corresponding to a distinct meaning of that noun.

66,Aberdeen,a city in northeastern Scotland on the North Sea
67,Aberdeen,a town in northeastern Maryland
68,Aberdeen,a town in northeastern South Dakota
69,Aberdeen,a town in western Washington

I'm an ontologist and I noticed that your hypernyms.txt file contains both is-a and is-instance-of relationships. Yes, you caught us. This ensures that every noun (except entity) has a hypernym. Here is an article on the subtle distinction.

Frequently Asked Questions (ShortestCommonAncestor)

Can I use my own Digraph class? No. You must use Digraph.java. That is the type of the argument to the constructor.

How can I make the data type ShortestCommonAncestor immutable? You can (and should) save the associated digraph in an instance variable. However, because Digraph is mutable, you must first make a defensive copy (e.g., by calling the copy constructor in Digraph).

Is a vertex considered an ancestor of itself? Yes.

What should ancestor() return if there is a tie for the shortest common ancestor? The API does not specify, so you are free to return any shortest common ancestor.

I understand how to compute the length() method in \(\Theta(E+V)\) time in the worst case but my lengthSubset() method takes \(\Theta(a \times b \times (E + V))\) time, where a and b are the sizes of the two iterables. How can I improve it to be \(\Theta(E + V)\) time? The key is to use a multi-source version of breadth-first search, as in the constructor in BreadthFirstDirectedPaths that accepts an iterable of sources as an argument (instead of a single source).

Should I construct a new ShortestCommonAncestor object for each call to sca() and distance()? No. You need only one ShortestCommonAncestor object per WordNet object. The methods sca() and distance() should make one call to either lengthSubset() or ancestorSubset().

How can I determine whether a digraph is a rooted DAG? This is a challenge for you to solve. Hint: break it up into two parts: (1) check if a digraph is a DAG and (2) check if a DAG is a rooted DAG.

Should I re-implement depth-first search to find directed cycles? No. Instead, use either DirectedCycle.java or Topological.java.

Should I re-implement breadth-first search to compute shortest common ancestors? Unless you are attempting the extra credit, you should use BreadthFirstDirectedPaths.java. To earn the extra credit, however, you'll need to re-implement breadth-first search.

Do I need to throw exceptions explicitly with a throw statement? No, it's fine if they are thrown implicitly. For example, you can rely on any method in Digraph.java to throw an IllegalArgumentException if passed a vertex argument outside of the prescribed range. A good API documents the requisite behavior for all possible arguments but, hopefully, you should not need much extra code to deal with these corner cases.

For the extra credit, do length(), lengthSubset(), ancestor(), and ancestorSubset() need to take time proportional to the number of vertices and edges reachable from the argument vertices in the worst case? Or, may I use hashing? You can make standard technical assumptions (such as the uniform hashing assumption).

Frequently Asked Questions (Outcast)

What should outcast() return if there is a tie for the outcast? The API does not specify, so you are free to return any outcast.

My algorithm computes the distance between every pair of nouns. Is that okay? Yes, that's fine.

Input, Output, and Testing

Shortest Common Ancestor. The following describes a test that creates a particular digraph whose lengthSubset() is known. Before describing the unit test, we will remind you of a definition.

A directed path of length \(\ell\) is a sequence of \(\ell\) directed edges that connect \(\ell + 1\) vertices. The starting vertex of a path is the vertex from which the path starts, i.e., the sole vertex with one outgoing and no incoming path edges. The ending vertex of a path is the vertex at which the path ends, i.e., the sole vertex with one incoming and no outgoing path edges. (All other vertices have one outgoing and one incoming edge each.)

The unit test is the following:

As an example, suppose \(n = 2\), \(m = 3\), pathsA = {3, 1}, and pathsB = {2, 2}. Then the following image represents this instance, with the colored vertices representing the two subsets.

Note that the number of vertices and edges in this rooted DAG is \(\Theta(nm)\) in expectation, so a correct implementation should take no more than a few seconds when \(n\) and \(m\) are 1,000.

Additional tests. The following ShortestCommonAncestor test client takes the name of a digraph input file as a command-line argument; creates the digraph; reads vertex pairs from standard input; and prints the length of the shortest ancestral path between the two vertices, along with a shortest common ancestor:

public static void main(String[] args) {
    In in = new In(args[0]);
    Digraph G = new Digraph(in);
    ShortestCommonAncestor sca = new ShortestCommonAncestor(G);
    while (!StdIn.isEmpty()) {
        int v = StdIn.readInt();
        int w = StdIn.readInt();
        int length   = sca.length(v, w);
        int ancestor = sca.ancestor(v, w);
        StdOut.printf("length = %d, ancestor = %d\n", length, ancestor);
    }
}

Here is a sample execution (the yellow text indicates what you type):

~/Desktop/wordnet> more digraph1.txt
12
11
 6  3
 7  3
 3  1
 4  1
 5  1
 8  5
 9  5
10  9
11  9
 1  0
 2  0
~/Desktop/wordnet> java-algs4 ShortestCommonAncestor digraph1.txt
3 10
length = 4, ancestor = 1
8 11
length = 3, ancestor = 5
6 2
length = 4, ancestor = 0

WordNet. Here are some interesting examples that you can use to test your code.

Possible Progress Steps

Enrichment