The purpose of this lab is to give students more exposure to object oriented des
ID: 3765095 • Letter: T
Question
The purpose of this lab is to give students more exposure to object oriented design and programming using classes in a realistic application that involves objects, strings, arrays, and searching and sorting algorithms.
A concordance is a unique list of words for a given document along with the frequencies of occurrence for each word. You are to design and develop an application which will create a concordance with frequencies for given text document and output the results, sorted either alphabetically or by frequencies (user specified).
Test your program with the following flat text files:
. Obama (2009) inaugural address (http://eve.kean.edu/~jryder/cps2231)
. Buch (2005) inaugural address (http://eve.kean.edu/~jryder/cps2231)
. Pride and Prejudice by Jane Austen (http://www.gutenberg.org/ )
. Communist Manifesto by Engels and Marx (http://www.gutenberg.org/ )
. The Holy Bible - King James Version (http://www.gutenberg.org/ )
. Huckleberry Finn by Mark Twain (http://www.gutenberg.org/ )
Program requirements:
A “Concordance” class - that contains: the unique word list, frequency for each word, total word count, a unique word total, a source input file reference, a method for populating frequencies, methods for constructing, sorting and reporting the concordance,…….
A “TestConcordance” class for running the concordances.
Arguments will be passed to the main method (in TestConcordance) using command line arguments with parameters for: 1) file containing the text, 2) alpha vs. numeric sort report (possibly a or n).
Explanation / Answer
The sorting problem is to rearrange a set of items in ascending order. One reason that it is so useful is that it is much easier to search for something in a sorted list than an unsorted one. In this section, we will consider in detail two classical algorithms for sorting and searching, along with several applications where their efficiency plays a critical role.
Binary search.
In the game of "twenty questions", your task is to guess the value of a hidden number that is one of the N integers between 0 and N-1. (For simplicity, we will assume that N is a power of two.) Each time that you make a guess, you are told whether your guess is too high or too low. An effective strategy is to maintain an interval that contains the hidden number, guess the number in the middle of the interval, and then use the answer to halve the interval size. Questions.java implements this strategy. It is an example of the general problem-solving method known as binary search.
The PhiInverse() method in Gaussian.java implements this strategy. In this context, binary search is often called bisection search because we bisect the interval at each stage.
Insertion sort.
Insertion sort is a brute-force sorting algorithm that is based on a simple method that people often use to arrange hands of playing cards: Consider the cards one at a time and insert each into its proper place among those already considered (keeping them sorted). The following code mimics this process in a Java method that sorts strings in an array:
public static void sort(String[] a) {
int N = a.length;
for (int i = 1; i < N; i++)
for (int j = i; j > 0; j--)
if (a[j-1].compareTo(a[j]) > 0)
exch(a, j, j-1);
else break;
}
The outer for loop sorts the first i entries in the array; the inner for loop can complete the sort by putting a[i] into its proper position in the array.
Mergesort.
To develop a faster sorting method, we use a divide-and-conquer approach to algorithm design that every programmer needs to understand. To mergesort an array, we divide it into two halves, sort the two halves independently, and then merge the results to sort the full array. To sort a[lo, hi), we use the following recursive strategy:
Merge.java is an implementation of this strategy. Here is a trace of the contents of the array during a merge.
Frequency counts.
FrequencyCount.java reads a sequence of strings from standard input and then prints a table of the distinct values found and the number of times each was found, in decreasing order of the frequencies. We accomplish this by two sorts.
to be or not to be to
then the result of the sort is
be be not or to to to
with equal strings like the three occurrences of to brought together in the array. Now, with equal strings all together in the array, we can make a single pass through the array to compute all the frequencies. The Counter.java data type that we considered in Section 3.3 is the perfect tool for the job.
Longest repeated substring.
Another important computational task that reduces to sorting is the problem of finding the longest repeated substring in a given string. This problem is simple to state and has many important applications, including computer-assisted music analysis, cryptography, and data compression. Think briefly about how you might solve it. Could you find the longest repeated substring in a string that has millions of characters? LRS.java is a clever solution that uses suffix sorting.
***************************
// precondition array a in ascending order
public static int binarySearch(long[] a, long key) {
int bot = -1;
int top = a.length;
while (top - bot > 1) {
int mid = bot + (top - bot) / 2;
if (key > a[mid]) bot = mid;
else top = mid;
}
if (a[top] == key) return top;
else return -top - 1;
}
**************
public static int binarySearch(long[] a, long key) {
int bot = 0;
int top = a.length - 1;
while (bot <= top) {
int mid = bot + (top - bot) / 2;
if (key < a[mid]) top = mid - 1;
else if (key > a[mid]) bot = mid + 1;
else return mid;
}
return -1;
}
public static void sort(String[] a) {
int N = a.length;
for (int i = 1; i < N; i++)
for (int j = i; j > 0; j--)
if (a[j-1].compareTo(a[j]) > 0)
exch(a, j, j-1);
else break;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.