Fall2005.CSCI221Homework4 History

Hide minor edits - Show changes to output

Added lines 48-51:
!!! Bonus

Here is [[CSCI221Homework4Bonus | something extra]] for bonus points.
Deleted lines 76-97:

----

!!!Bonus

For bonus points, have ADT @@TextAnalyzer@@ calculate the [[ZipfIntro | 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 [[http://stono.cs.cofc.edu/~manaris/spring05/cs221/code/ZipfStatistics.class | 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 [[http://creativecommons.org/licenses/by-nc-sa/2.5/ | 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 [[ZipfIntro | 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 [[http://stono.cs.cofc.edu/~manaris/spring05/cs221/code/ZipfStatistics.class | 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 [[http://creativecommons.org/licenses/by-nc-sa/2.5/ | 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 [[ZipfIntro | 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 [[http://stono.cs.cofc.edu/~manaris/spring05/cs221/code/ZipfStatistics.class | 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 [[http://creativecommons.org/licenses/by-nc-sa/2.5/ | 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 [[ZipfIntro | 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 [[http://stono.cs.cofc.edu/~manaris/spring05/cs221/code/ZipfStatistics.class | 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 [[http://creativecommons.org/licenses/by-nc-sa/2.5/ | 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.
Added line 24:
Added line 26:
Added line 28:
Added line 30:
Added line 32:
Added line 34:
Added line 36:
Changed lines 51-52 from:
# Open your BlueJ project.
to:
# Open your BlueJ project.

# Ensure it contains the following: TextAnalyzer.java and README.TXT
.
Changed lines 23-30 from:
* 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).
to:
* @@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).
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 [[http://www.bluej.org/tutorial/testing-tutorial.pdf | 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'''

# 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''.)

# Right-click on @@CircularQueue.java@@. Select ''Create Test Class''. This will generate file @@CircularQueueTest.java@@.

# 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 [[http://www.bluej.org/tutorial/testing-tutorial.pdf | Unit testing in BlueJ]]).
to:
''More to come...''
Deleted lines 52-57:
# Ensure it contains the following: @@CircularQueue.java@@, @@QueueInterface.java@@, @@CircularQueueTest.java@@, and @@README.TXT@@.
## @@README.TXT@@ should include (in addition to your name and relevant info), a textual description of your test plan.
## @@CircularQueueTest.java@@ should contian the JUnit implementation of your test plan.

# 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 {$LastModified} (see [[http://www.cs.cofc.edu/~manaris/index.php/Fall2005/CSCI221Homework4?action=diff&source=n&minor=n | 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 [[http://www.bluej.org/tutorial/testing-tutorial.pdf | 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'''

# 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''.)

# Right-click on @@CircularQueue.java@@. Select ''Create Test Class''. This will generate file @@CircularQueueTest.java@@.

# 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 [[http://www.bluej.org/tutorial/testing-tutorial.pdf | 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

# Open your BlueJ project.

# Ensure it contains the following: @@CircularQueue.java@@, @@QueueInterface.java@@, @@CircularQueueTest.java@@, and @@README.TXT@@.
## @@README.TXT@@ should include (in addition to your name and relevant info), a textual description of your test plan.
## @@CircularQueueTest.java@@ should contian the JUnit implementation of your test plan.

# 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.)

# Under the Project menu, click ''Create Jar File...'' . In the dialog box that opens, select ''Include Source'', and press ''Continue''.

# Email the generated @@.jar@@ file to ''manaris@cs.cofc.edu'', by the due date and time.