Fall2005.CSCI221Homework4 History

Show minor edits - Show changes to markup

Added lines 48-51:

Bonus

Here is something extra for bonus points.

Deleted lines 76-97:

Bonus

For bonus points, have ADT TextAnalyzer calculate the Zipf distribution of the words. This is done through the following operations:

  • double getZipfSlope()
    which returns the slope of the Zipf distribution of the word frequencies.
  • double getZipfRSquared()
    which returns the R2 value of the Zipf distribution of the word frequencies. (Note: The R2 value indicates how close the data points are to the trendline, overall. A value of 1 indicates that the data points coincide with the trendline, whereas a value of 0 indicates that the data points are scattered randomly.)

These methods should use ZipfStatistics.class. Download it and save it in the same directory as your source file. It contains the following methods:

  • double slope(double wordFrequencies[])
    which returns the slope of the Zipf distribution of the provided word frequencies.
  • double rSquared(double wordFrequencies[])
    which returns the R2 of the Zipf distribution of the provided word frequencies.

http://www.cs.cofc.edu/~manaris/spring05/cs221/hmwk4_files/image001.gif ZipfStatistics.class is made available under a Creative Commons License. It was developed by Chris Wagner, Charles McCormick, and Bill Manaris.

Deleted lines 47-67:

Bonus:

For bonus points, have ADT TextAnalyzer calculate the Zipf distribution of the words. This is done through the following operations:

  • double getZipfSlope()
    which returns the slope of the Zipf distribution of the word frequencies.
  • double getZipfRSquared()
    which returns the R2 value of the Zipf distribution of the word frequencies. (Note: The R2 value indicates how close the data points are to the trendline, overall. A value of 1 indicates that the data points coincide with the trendline, whereas a value of 0 indicates that the data points are scattered randomly.)

These methods should use ZipfStatistics.class. Download it and save it in the same directory as your source file. It contains the following methods:

  • double slope(double wordFrequencies[])
    which returns the slope of the Zipf distribution of the provided word frequencies.
  • double rSquared(double wordFrequencies[])
    which returns the R2 of the Zipf distribution of the provided word frequencies.

http://www.cs.cofc.edu/~manaris/spring05/cs221/hmwk4_files/image001.gif ZipfStatistics.class is made available under a Creative Commons License. It was developed by Chris Wagner, Charles McCormick, and Bill Manaris.

Changed lines 73-94 from:
to:

Bonus

For bonus points, have ADT TextAnalyzer calculate the Zipf distribution of the words. This is done through the following operations:

  • double getZipfSlope()
    which returns the slope of the Zipf distribution of the word frequencies.
  • double getZipfRSquared()
    which returns the R2 value of the Zipf distribution of the word frequencies. (Note: The R2 value indicates how close the data points are to the trendline, overall. A value of 1 indicates that the data points coincide with the trendline, whereas a value of 0 indicates that the data points are scattered randomly.)

These methods should use ZipfStatistics.class. Download it and save it in the same directory as your source file. It contains the following methods:

  • double slope(double wordFrequencies[])
    which returns the slope of the Zipf distribution of the provided word frequencies.
  • double rSquared(double wordFrequencies[])
    which returns the R2 of the Zipf distribution of the provided word frequencies.

http://www.cs.cofc.edu/~manaris/spring05/cs221/hmwk4_files/image001.gif ZipfStatistics.class is made available under a Creative Commons License. It was developed by Chris Wagner, Charles McCormick, and Bill Manaris.

Changed lines 21-22 from:
  • public TextAnalyzer(), which creates an empty list, i.e., a list with two dummy head and tail Node objects linked appropriately.
to:
  • public TextAnalyzer()
    which creates an empty list, i.e., a list with two dummy head and tail Node objects linked appropriately.
Changed lines 24-41 from:
  • public void add(String word), which adds word into the list, as described above.
  • public void remove(String word), which removes word from the list, as described above.
  • public int getFrequency(String word), which returns the count of the word, or zero if the word is not in the list. (Note: This should not be confused with the meaning of frequency in Physics.)
  • public double getProbability(String word), which returns the probability of the word to appear in the text, or zero if the word is not in the list. The probability of a word is defined as its count divided by the total number of words -- thatís the total number of words added to the list, NOT the number of unique words. (Another term for this is relative frequency.)
  • public void reset(), which resets the current position to the beginning of the list.
  • public String getNextWord(), which returns the current word and advances the current position. It returns null if current position is past the end of the list.
  • public int getUniqueWordCount(), which returns the number of unique words in the list.
  • public int getAllWordCount(), which returns the number of items added to the list (including duplicate word additions).

More to come...

to:
  • public void add(String word)
    which adds word into the list, as described above.
  • public void remove(String word)
    which removes word from the list, as described above.
  • public int getFrequency(String word)
    which returns the count of the word, or zero if the word is not in the list. (Note: This should not be confused with the meaning of frequency in Physics.)
  • public double getProbability(String word)
    which returns the probability of the word to appear in the text, or zero if the word is not in the list. The probability of a word is defined as its count divided by the total number of words -- thatís the total number of words added to the list, NOT the number of unique words. (Another term for this is relative frequency.)
  • public void reset()
    which resets the current position to the beginning of the list.
  • public String getNextWord()
    which returns the current word and advances the current position. It returns null if current position is past the end of the list.
  • public int getUniqueWordCount()
    which returns the number of unique words in the list.
  • public int getAllWordCount()
    which returns the number of items added to the list (including duplicate word additions).

Bonus:

For bonus points, have ADT TextAnalyzer calculate the Zipf distribution of the words. This is done through the following operations:

  • double getZipfSlope()
    which returns the slope of the Zipf distribution of the word frequencies.
  • double getZipfRSquared()
    which returns the R2 value of the Zipf distribution of the word frequencies. (Note: The R2 value indicates how close the data points are to the trendline, overall. A value of 1 indicates that the data points coincide with the trendline, whereas a value of 0 indicates that the data points are scattered randomly.)

These methods should use ZipfStatistics.class. Download it and save it in the same directory as your source file. It contains the following methods:

  • double slope(double wordFrequencies[])
    which returns the slope of the Zipf distribution of the provided word frequencies.
  • double rSquared(double wordFrequencies[])
    which returns the R2 of the Zipf distribution of the provided word frequencies.

http://www.cs.cofc.edu/~manaris/spring05/cs221/hmwk4_files/image001.gif ZipfStatistics.class is made available under a Creative Commons License. It was developed by Chris Wagner, Charles McCormick, and Bill Manaris.

Changed lines 21-22 from:
  • public TextAnalyzer(), which creates an empty list, i.e., a list with two dummy head and tail Node objects linked appropriately.
  • public void add(String word), which adds word into the list, as described above.
to:
  • public TextAnalyzer(), which creates an empty list, i.e., a list with two dummy head and tail Node objects linked appropriately.
  • public void add(String word), which adds word into the list, as described above.
Changed lines 31-75 from:

Design and implement a CircularQueue ADT using a circular linked implementation (as shown in Figure 5.13 of the textbook). Your ADT should implement QueueInterface.

(:source lang=Java header="Interface for a class that implements a queue of Objects." tabwidth=3 -trim :)

public interface QueueInterface {

  public void enqueue(Object item); 
  // Effect:         Adds item to the rear of this queue.
  // Precondition:   This queue is not full.
  // Postcondition:  item is at the rear of this queue.

  public Object dequeue();
  // Effect:         Removes front element from this queue and returns it.
  // Precondition:   This queue is not empty.
  // Postconditions: Front element has been removed from this queue.
  //                 Return value = (the removed element)

  public boolean isEmpty();
  // Effect:         Determines whether this queue is empty.
  // Postcondition:  Return value = (this queue is empty)

  public boolean isFull();
  // Effect:         Determines whether this queue is full.
  // Postcondition:  Return value = (queue is full)

}

(:sourcend:)

Test Plan

Read the short tutorial Unit testing in BlueJ.

Develop a test plan to test your implementation (see the test plan developed in Chapter 4). Your test plan should include one or more tests for each Queue operation -- tests should be thorough and not redundant.

Details

  1. Use BlueJ to create a test class. (Within BlueJ, you may need to show unit testing tools. Go to Preferences-->Miscallaneous and check Show Unit Testing Tools.)
  2. Right-click on CircularQueue.java. Select Create Test Class. This will generate file CircularQueueTest.java.
  3. Right-click on CircularQueueTest.java. Select Create Test Method. Give it a descriptive name, e.g., TestIsEmpty. This will create the method and start recording your actions... (for the rest, see Unit testing in BlueJ).
to:

More to come...

Deleted lines 52-57:
  1. Ensure it contains the following: CircularQueue.java, QueueInterface.java, CircularQueueTest.java, and README.TXT.
    1. README.TXT should include (in addition to your name and relevant info), a textual description of your test plan.
    2. CircularQueueTest.java should contian the JUnit implementation of your test plan.
  2. Open (edit) each source file and generate the class interface (javadoc). This can be done within the editor window either by pressing CTRL/J , or selecting the Interface drop-down menu item (on the right). (Note: This is necessary to generate your documentation for grading.)
Added lines 1-105:

Assigned Date: Wednesday, Nov. 16, 2005 (sec 2 +1 day)
Due Date: Thursday, Dec. 1, 2005 (sec 2 +1 day)
Due Time: Noon

Last modified on November 17, 2005, at 03:32 PM (see updates)

Purpose

This assignment focuses on linked lists.

Assignment

Implement a TextAnalyzer ADT in Java. This ADT encapsulates a list of items stored using a sorted doubly-linked list with dummy head and tail nodes. The list contains unique words sorted lexicographically (case insensitive) and corresponding counts. Adding a duplicate word simply increments the corresponding count. Deleting a word, decrements the corresponding count. Deleting the last instance of a word, completely removes that word (and corresponding count) from the list.

In terms of implementation, TextAnalyzer objects should have three Node references, head, tail, and currentPosition. There should NOT be a numItems (or similar) variable, i.e., the length of the list will be calculated dynamically whenever it is needed.

Class Node should be implemented as an internal class. It should encapsulate a word and a count, as well as a prev and next link.

TextAnalyzer has the following API:

  • public TextAnalyzer(), which creates an empty list, i.e., a list with two dummy head and tail Node objects linked appropriately.
  • public void add(String word), which adds word into the list, as described above.
  • public void remove(String word), which removes word from the list, as described above.
  • public int getFrequency(String word), which returns the count of the word, or zero if the word is not in the list. (Note: This should not be confused with the meaning of frequency in Physics.)
  • public double getProbability(String word), which returns the probability of the word to appear in the text, or zero if the word is not in the list. The probability of a word is defined as its count divided by the total number of words -- thatís the total number of words added to the list, NOT the number of unique words. (Another term for this is relative frequency.)
  • public void reset(), which resets the current position to the beginning of the list.
  • public String getNextWord(), which returns the current word and advances the current position. It returns null if current position is past the end of the list.
  • public int getUniqueWordCount(), which returns the number of unique words in the list.
  • public int getAllWordCount(), which returns the number of items added to the list (including duplicate word additions).

Design and implement a CircularQueue ADT using a circular linked implementation (as shown in Figure 5.13 of the textbook). Your ADT should implement QueueInterface.

(:source lang=Java header="Interface for a class that implements a queue of Objects." tabwidth=3 -trim :)

public interface QueueInterface {

  public void enqueue(Object item); 
  // Effect:         Adds item to the rear of this queue.
  // Precondition:   This queue is not full.
  // Postcondition:  item is at the rear of this queue.

  public Object dequeue();
  // Effect:         Removes front element from this queue and returns it.
  // Precondition:   This queue is not empty.
  // Postconditions: Front element has been removed from this queue.
  //                 Return value = (the removed element)

  public boolean isEmpty();
  // Effect:         Determines whether this queue is empty.
  // Postcondition:  Return value = (this queue is empty)

  public boolean isFull();
  // Effect:         Determines whether this queue is full.
  // Postcondition:  Return value = (queue is full)

}

(:sourcend:)

Test Plan

Read the short tutorial Unit testing in BlueJ.

Develop a test plan to test your implementation (see the test plan developed in Chapter 4). Your test plan should include one or more tests for each Queue operation -- tests should be thorough and not redundant.

Details

  1. Use BlueJ to create a test class. (Within BlueJ, you may need to show unit testing tools. Go to Preferences-->Miscallaneous and check Show Unit Testing Tools.)
  2. Right-click on CircularQueue.java. Select Create Test Class. This will generate file CircularQueueTest.java.
  3. Right-click on CircularQueueTest.java. Select Create Test Method. Give it a descriptive name, e.g., TestIsEmpty. This will create the method and start recording your actions... (for the rest, see Unit testing in BlueJ).

Documentation

Your code should be fully documented via javadoc. Your code should throw approppriate runtime exceptions to test preconditions and handle errors.

Include the following in each class:

       Certification of Authenticity:

       I certify that this submission is entirely my own work, 
       as per course collaboration policy.


       Name: ________________________ Date: ___________

Submission

  1. Open your BlueJ project.
  2. Ensure it contains the following: CircularQueue.java, QueueInterface.java, CircularQueueTest.java, and README.TXT.
    1. README.TXT should include (in addition to your name and relevant info), a textual description of your test plan.
    2. CircularQueueTest.java should contian the JUnit implementation of your test plan.
  3. Open (edit) each source file and generate the class interface (javadoc). This can be done within the editor window either by pressing CTRL/J , or selecting the Interface drop-down menu item (on the right). (Note: This is necessary to generate your documentation for grading.)
  4. Under the Project menu, click Create Jar File... . In the dialog box that opens, select Include Source, and press Continue.
  5. Email the generated .jar file to manaris@cs.cofc.edu, by the due date and time.