Lab $6$: SpellChecker Dictionary Case Study: Choosing Data Structures for Your Apps $-$

Sets and Lists

Coding Projects$150$ pts

Overview

One of this course's primary goals is to teach students to develop and apply techniques for choosing optimal data structures based on performance metrics and specific application requirements.

Announcing: Fantastic Summer Internship Available with AI writing assistant Grammarly

Test and Develop new SpellChecker software $-$ Apply Here!

image.png

Because of your hard work in this course, let's pretend that you have the fantastic new summer internship opportunity at AI Powerhouse Grammarly to evaluate, compare, and test three alternative algorithms based on a choice of data structures for their new SpellChecker module. Coincidentally, you have recently studied the exact alternative data structures you are asked to evaluate: ArrayLists, HashSets, and TreeSets!

diagram$-$export$-4-6-2024-10\_18\_57-$AM$-1.$png

Your job is to write alternative Spell Checkers using algorithms based on each Data Structure type, write a short theoretical analysis of the predicted efficiency of each data structure using Big$-$O analysis, write test software to measure the actual performance of each using empirical execution timing metric and report your observed theoretical understanding and empirical test results.

Luckily, you are prepared since we have learned that we can compare the relative performance of data structures using mathematical metrics with Big$-$O notation, ranking the performance of algorithms without reference to underlying machine architectures. We haven't previously measured the predicted behavior using actual measured program execution time, but now we will. Will our testing confirm our theoretical expectations for the data structures we are testing?

A Question of War and Peace

warandpeace$-1.$pngalice.png

In addition to studying data structures and algorithms and preparing for your internship, this week, we will also study two great literary works: War and Peace, one of the longest novels ever written, and Alice in Wonderland. Don't worry; you don't have to buy the books.

But you must read both books, not just once, but many times. Luckily, your math homework won't suffer too much since we will allow you to have your computer to do the reading!

So$,$ you won't be tested on your reading comprehension, but you WILL be tested on your spelling. Again your computer will do the spell checking.

That's because, for this assignment, you will be required to write a SpellChecker, not just one, but three, and it will be up to you to determine which SpellChecker works best and why.

So$,$ what do I have to do$?$

Your task is to analyze and test several data structures to spell$-$check large text files against a dictionary. Your analysis should be theoretical, using Big$-$O analysis, and empirical, using timed tests.

Learning Objectives:

In addition to illustrating techniques for comparing algorithms and data structures, For this assignment, you will get additional practice with the Java Collections List and Set classes we have been studying, including Hashset, Treeset, and ArrayList, which we will use to store our dictionaries and documents for our SpellChecker methods, comparing the performance of each data structure we use.

We will also use Java I$/$O reader classes FileReader and BufferedFileReader to input our dictionary and document files into our List and Set data structures.

We will use a custom Timer class to calculate the relative performance of our List and Sets. The class hierarchy of these classes is shown below:

diagram$-$export$-4-6-2024-10\_18\_57-$AM$-1.$png

Finally, you will analyze your results using Big$-$O notation, the mathematical notation we have been studying to describe the time complexity of algorithms. As you recall, this notation allows us to compare algorithms $($without reference to machine architectures$).$ We will supplement this analysis with empirical data derived from the execution time metrics we gather from using the Timer class.

Project Development Process

Step $1$:

SpellCheckApp $-$ Enhancement

Create a new project in IntelliJ called SpellCheck or a name of your choice. Add a Java class to your src directory called SpellCheck.java. Download SpellCheck.java Download SpellCheck.javahere and replace the empty code file in IntelliJ.

Follow the tutorial on setting up a file path in IntelliJ using a resources directory.

Add the words Download wordsand alice$30.$txt Download alice$30.$txtfile to your new resources directory.

In part $2,$ we will use a third file: War$-$and$-$Peace.txt$.$ Download War$-$and$-$Peace.txt$.$ You should download and install this file too in your resources folder while you're here.

Test the SpellCheck executable using the provided data files. This program reads the words $($dictionary$)$ and a document file $($Allice in Wonderland$),$ reports the document and mismatched word counts, and pri