There is a more recent offering of this course. This is an archive of the course which was offered in Spring 2016-2017.

Lab 4

Get started now

## Overview For this assignment you must implement a simple `Dictionary` class which will hold a collection of correctly spelled words. You are given three text files. You must make predictions about the relative speed at which various tasks will be performed and write a program to collect a number of benchmarking statistics using three text files. ## Assignment ### Dictionary Class For this assignment you must implement a simple `Dictionary` class which will hold a collection of correctly spelled words. The words should be stored in a `Collection<String>`. It should be easy to change the actual collection used from `ArrayList` to `LinkedList` or some other class that implements the `Collection` interface. The `Dictionary` must have the following four methods: * **Constructor** — The constructor should accept a `Collection<String>`. If the argument passed is `null`, the method should throw a `NullPointerException`. Otherwise, it should ensure that the collection is empty (emptying it if it is not empty). * **`load(String filename)`** — This method accepts a filename and adds each word found in the file to the dictionary. The method returns the number of nanoseconds to add all of the words in the file to the dictionary (as a `long`). This method should add to the words already in the dictionary (if any). It is optional for this method to ignore duplicate words. * **`contains(String target)`** — returns `true` if and only if `target` is in the dictionary. You should make use of the underlying collection's `contains()` implementation in order to take advantage of any performance enhancements it may have. * **`clear()`** — Removes all words from the dictionary. (returns nothing) ### Main Program You will be working with the following three text files: * [story.txt](/taylor/files/story.txt) — A short story containing a bit over one thousand words. * [words.txt](/taylor/files/words.txt) — A list of a bit over one hundred thousand words. * [kjv10.txt](/taylor/files/kjv10.txt) — The contents of the King James Bible containing a bit under one million words. You will be performing a number of passes with the data. In each pass you will select three things: 1) the dictionary file, 2) the document file, and 3) the collection to be used. For example, with 1) `words.txt`, 2) `story.txt`, and 3) `ArrayList`, you need to load all of the words in `words.txt` into your dictionary that uses an `ArrayList` to store words and then read each word out of `story.txt` and check to see if it is in the dictionary. You may ignore complications like punctuation. For each pass you should determine the number of misspelled words and benchmark two things: the amount of time to add all the words into the dictionary and the amount of time to check all of the words in the document to see if they are in the dictionary. __You should not include file access time in your timings.__ You must write a program that can be used to generate the data needed to fill in the following table: | Dictionary | Document | Collection | Number Not in Dictionary | Time to Add | Time to Spell-Check | | ---------- | -------- | ---------- | ------------------------ | ----------- | -------------- | | `words.txt` | `story.txt` | `ArrayList` | | | | | `words.txt` | `story.txt` | `LinkedList` | | | | | `words.txt` | `story.txt` | `SortedArrayList` | | | | | `story.txt` | `words.txt` | `ArrayList` | | | | | `story.txt` | `words.txt` | `LinkedList` | | | | | `story.txt` | `words.txt` | `SortedArrayList` | | | | **Run your tests using this [SortedArrayList.java](SortedArrayList.java) class.** Your program output __must be formatted neatly__ (consider using `format()`, see [here](http://msoe.taylorial.com/se1011/Format), or `DecimalFormat`). For example, your program output may look something like this: <pre> | Dictionary | Document | Collection | Misspelled | Time to add | Time to spell-check | | words.txt | story.txt | ArrayList | XXXXX | X mins XX.XXXXXXXXXX secs | X mins XX.XXXXXXXXXX secs | | words.txt | story.txt | LinkedList | XXXXX | X mins XX.XXXXXXXXXX secs | X mins XX.XXXXXXXXXX secs | | words.txt | story.txt | SortedArrayList | XXXXX | X mins XX.XXXXXXXXXX secs | X mins XX.XXXXXXXXXX secs | | story.txt | words.txt | ArrayList | XXXXX | X mins XX.XXXXXXXXXX secs | X mins XX.XXXXXXXXXX secs | | story.txt | words.txt | LinkedList | XXXXX | X mins XX.XXXXXXXXXX secs | X mins XX.XXXXXXXXXX secs | | story.txt | words.txt | SortedArrayList | XXXXX | X mins XX.XXXXXXXXXX secs | X mins XX.XXXXXXXXXX secs | </pre> Once you have run all of you tests for the above table, you should use your findings to predict which of following will run fastest/slowest. Place a **1** the location that will run the fastest, a **2** in the next fastest, ..., and **12** in the location that you believe will run the slowest. | Dictionary | Document | Collection | Time to Add | Time to Spell-Check | | ---------- | -------- | ---------- | ------------------------ | ----------- | -------------- | | `words.txt` | `kjv10.txt` | `ArrayList` | | | | `words.txt` | `kjv10.txt` | `LinkedList` | | | | `words.txt` | `kjv10.txt` | `SortedArrayList` | | | | `kjv10.txt` | `words.txt` | `ArrayList` | | | | `kjv10.txt` | `words.txt` | `LinkedList` | | | | `kjv10.txt` | `words.txt` | `SortedArrayList` | | | ### Instructor Specific Deliverable Your instructor may require that you run the following tests also. Keep in mind that these tests will require more time to run. Therefore, make sure you budget sufficient time so that you are not waiting on results while your submission deadline passes. | Dictionary | Document | Collection | Number Not in Dictionary | Time to Add | Time to Spell-Check | | ---------- | -------- | ---------- | ------------------------ | ----------- | -------------- | | `words.txt` | `kjv10.txt` | `ArrayList` | | | | | `words.txt` | `kjv10.txt` | `LinkedList` | | | | | `words.txt` | `kjv10.txt` | `SortedArrayList` | | | | | `kjv10.txt` | `words.txt` | `ArrayList` | | | | | `kjv10.txt` | `words.txt` | `LinkedList` | | | | | `kjv10.txt` | `words.txt` | `SortedArrayList` | | | | ## Lab Deliverables > See your professor's instructions for details on submission guidelines and due dates. > * Dr. Taylor's students: See below > * All other students should refer to Blackboard > >If you have any questions, consult your instructor. ## Acknowledgements This assignment was written by [Dr. Chris Taylor](/taylor).

Thursday, 30-Mar-2017 10:56:15 CDT

Submission Form for Dr. Taylor

Submission due 11pm, Tuesday of week 5

You must use this file as a starting point for your report. Please ask if you have questions about how to use this file. Your report should consist of three sections. The third section is optional (excluding it will result in 95/100 as your best possible grade).

Section I

Copy and paste the results from running the six tests using the words.txt and story.txt files. Your results should replace the following line in the file:

FIX your results related to story.txt go here FIX

Section II

After completing the benchmarking required for section I, you should guess how long you think it will take each of the benchmarks to take using the words.txt and kjv10.txt files. Using the 1 - 12 rankings completed as part of the assignment, you should group the different operations into three different categories: fastest, middle, and slowest. Place all of the ones that you think will take a long time to run in the slowest category, etc.... You can just cut/paste the lines of text into the appropriate grouping.

In addition to grouping the different operations, you should explain your reasons in a paragraph.

Section III

Copy and paste your results from running the six tests using the words.txt and kjv10.txt files. Your results should replace the following line in the file:

FIX your results related to kvj10.txt go here FIX

Submission

Each student must submit their report file and source code which must follow the SE1021 Coding Standards.