PROJECT #4 Using Data Structures for a Dictionary Application
By Sandino Vargas-Pérez, edited by Pamela Cutter

---

Consider the task of implementing a Data Structure that holds all of the entries in a Dictionary of Synonyms and Antonyms. This structure will be composed by Entry objects. The Entry object contains the KEY or word and its synonyms and antonyms, SYN and ANT, respectively, like this:

KEY: justice
SYN: impartiality, fairness, right, reasonableness, propriety, uprightness…
ANT: injustice, partiality, unfairness, unreasonableness, unlawfulness…

Choosing a Data Structure

The main operation of this structure will be searching: Given a word, return whether the word exists or not. If the word exists, then also return its synonyms and antonyms. A secondary operation will be adding new words to the dictionary or removing deprecated ones. Given all the ADTs discussed during the quarter (Arrays, ArrayLists, LinkedLists, Queues and Stacks, Binary Trees, BSTs, Minheaps, HashMaps, HashSets, HashTables), choose the one you considered to be the most appropriate for the task.

Think About:

• Whether or not it will be a good fit to use it as the underlying data structure of the Dictionary of Synonyms and Antonyms.
• How Java implements this data structure and its operations (from what you can gather from the documentation or Internet forums).
• Building the structure (how would you implement the dictionary using the particular data structure).
• Time complexity of searching for a given word, adding or removing words.
• Efficiency in terms of memory space for the data structure.

Exploring Solutions

Download the following file: Final Project Code and Dictionaries.zip. This zip file contains a BlueJ project with 2 different implementations (the "SearchEngine" classes) of such a dictionary; one uses a HashMap, the other uses an ArrayList. You will use this code to validate and compare your answer. You can also use one of the “Search Engines” classes and construct another search engine using a different data structure, such as the TreeMap or a LinkedList (or your OrderedList from mini-lab #4).

Structure of the Report

This final project is also an opportunity for you to reflect about the different ways of organizing data in memory, the different operations they will enable, the different levels of efficiencies you will achieve, the applications to everyday life problems, and most importantly to see if you were able to achieve some (or all) of the goals of this course.

Your report should be organized into the following sections:

• Section 1: Introduction: Introduce the main problem of this project (in your own words) that you are about to work with.
• Section 2: Analysis and Solutions: Discuss the following questions providing a good sounding, in-depth analysis of your answers:
  • Which data structure did you choose (in Section 1) as the most appropriate for this problem? Explain why you chose this structure. For at least two other data structures, explain why you thought they were either not good choices, or could be a good second choice.
  • Did either of the SearchEngines that were provided match your data structure selection? Did you expect this? Why or why not? How did they compare with your thoughts on how to implement the dictionary with your selected data structure? Were your expectations, based on the time complexity of these data structures, satisfied?
  • How does Java implement these data structures and its operations (from what you can gather from the Java documentation or Internet forums and from class)?
  • (If you built a third search engine) How did you implement the dictionary using that data structure? Discuss time complexity of searching for a given word, adding or removing words when the dictionary size increases. Does this analysis correlates to the execution times you’ve got? (Note: The dictionary files vary in size: dictionary.txt is the smallest and dictionary3.txt is the biggest.)
  • What’s the efficiency in terms of memory space for these data structures?
  • Add graphs or charts depicting time taken to find words in two of the dictionaries using two of the search engines. If you want to append timing results between the different implementations, or if you generated plots from it to show how the data structures behave as the dictionary entries increase in size, you should add them to your document as well.
• Section 3: Conclusions and Personal Reflection: Write your conclusions about the use of data structures to solve specific problems in CS (what did you learn while working on it). Also, you will use this section to personally reflect about the following:
  • Your understanding of common data structures and algorithms.
  • Are you able to apply that understanding to the implementation of new data abstractions, using existing library components?
  • Are you a stronger programmer? Do you feel more comfortable programming in Java?
  • Do you understand how to measure an algorithm’s efficiency in terms of running time?
  • Are you knowledgeable enough to choose the appropriate algorithms and data structures to solve a given problem?

Prepare a document (2-pages min, 4-pages max) with your answers and submit to Kit in PDF format, under Project 4: Dictionary Application.

Have fun! And if you have any questions remember that you can ask questions via email, Teams, and/or the Collaboration Center!