Problem Set 2: Using Abstract Datatypes

Procedural Abstraction and Using Abstract Datatypes

Due: Thursday, 9 September (beginning of class)

Purpose

• Learn to reason about and develop good procedural specifications.
  
• Learn to use an abstract data type by reading its specification.

• Think about how to test a procedure.
  

This assignment is significantly longer than PS1 and you have over a week to complete it. Please don’t wait to get started. You are strongly encouraged to take advantage of the scheduled office and help hours for this assignment.

Specifying Procedures

For the next two questions, consider these two specifications for the
public static void sort(int[ ] a) procedure:

Specification A. From the Java SE 6 Platform API documentation (java.util.Arrays):

Sorts the specified array of ints into ascending numerical order. The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy’s “Engineering a Sort Function”, Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

Parameters:
   a – the array to be sorted.

Specification B. From the textbook (p.46):

MODIFIES: a
EFFECTS: Rearranges the elements of a into ascending order.
   e.g., if a = [3, 1, 6, 1], a_post = [1, 1, 3, 6]

Consider the histogram prodecure defined (but not specified!) below:

public static int [] histogram (int [] a)
// unspecified
{
   int maxval = 0;
   for (int i = 0; i < a.length; i++) {
      if (a[i] > maxval) {
         maxval = a[i];
      }
   }
   int histo [] = new int [maxval + 1];
   for (int i = 0; i < a.length; i++) {
      histo[a[i]]++;
   }
   return histo;
}

For example,

   int [] test = { 1, 2, 3, 4, 6, 4, 3, 3, 0 } ;
   int [] hist = histogram (test);

the value of hist will be [1, 1, 1, 3, 2, 0, 1].

Part II: Document Similarity Analysis

For the second part of this problem set, you will build a program for finding similarities between documents. This might be used to try to determine authorship of an anonymous writing, detect instances of plagiarism, or identify unexpected influences. The basic approach we will use is to count the number of common short sequences of words in pairs of documents. Documents with more common sequences are likely to be related.

As an example, if you extract the three documents in this zip file and run your program with command line arguments declaration.txt constitution.txt universityact.txt, your program should output something like:

[constitution.txt - universityact.txt: 82, declaration.txt - constitution.txt: 33, declaration.txt - universityact.txt: 16]

(indicating that the US Constitution and Act founding the University of Virginia are more similar than the Declaration of Independence and the Act). Obviously, there are some flaws with this approach, in particular, not normalizing for the relative lengths of the documents. Ambitious students will attempt to improve the analysis to produce better results, but simple sequence counts are enough for full credit on this assignment.

We have provided several datatypes that you may find helpful in solving this problem. Their specifications are available here:

Specifications

Download ps2.jar and install it to incorporate these types in your project.

The first is the WordWindow datatype for representing a fixed-length sequence of n words. WordWindow provides methods for inserting a word, and for retrieving the current sequence of the last n words as a single String.

The TallyTable datatype provides an abstraction that maps a String to an integer value. It provides the void tally(String) method that increases the tally associated with its input string, as well as methods for getting the tally associated with a string and a list of all the strings in the TallyTable.

The Document datatype provides an abstraction that represents a document and its associated word sequence tally. It provides a constructor that takes a String representing a file name as its input, and constructs a Document object that represents the document in that file. It uses the WordWindow and TallyTable datatypes to do this:

	/**
	 * Creates a new document from the file identified by fname, using window size window.
	 * @param fname
	 * @param window
	 * @throws FileNotFoundException
	 */
	public Document(String fname, int window) throws FileNotFoundException {
		name = fname;
		Scanner s = new Scanner(new File(fname)).useDelimiter("[^A-Za-z]");
		WordWindow w = new WordWindow(window);
		tt = new TallyTable();

		while (s.hasNext()) {
			String word = s.next().toLowerCase();
			w.insert(word);
			tt.tally(w.currentWindow());
		}

		for (int i = 0; i < window; i++) {
			w.insert(null);
			tt.tally(w.currentWindow());
		}
	}

If you use the provided Document class, you should not need to use TallyTable or WordWindow directly in your implementation.

The LabeledGraph datatype provides an abstraction for a labeled, undirected graph. It provides methods for adding nodes and labeled edges to a graph, and ArrayList getSortedEdges() for getting a list of the edges in the graph sorted by their labels. The EdgeRecord datatype is a record type for describing an edge in a graph (two nodes and a label).

You should feel free to use (or not use) these datatypes as you see fit.

Print PDF