Description
Objects and Data Abstraction
Q1. You are asked to design and implement a binary search tree that simulates a dictionary.
This tree is used to store definitions of words. Each definition has two parts, a word and its description (explanation) both of which are strings. The program starts by displaying the following menu:
1. Create the dictionary
2. Add a definition
3. Remove a definition
4. Search for a definition
5. Print Dictionary
6. Exit
———————————–
Enter your choice:
Create the dictionary (recursive): The program prompts the user for the name of a text file where word definitions are stored. Each word definition is stored on a line in the file. The definition has two parts, the word and its description separated by a colon ( : )
Following is an example of how the text file should look like:
Human Being: Evolved homosapien
Pen: Tool used to write
Couch potato: Potato sitting on a couch
The text file is then parsed and the definitions are extracted and stored in appropriate objects. A binary search tree containing all the definitions is then constructed according to the order of appearance of the definitions in the text file. Definitions are compared by their word field hence, the word “animal” is smaller than the word “job”. “Human Being” is smaller than “Pen”. If the text file is not found, the program should prompt for the name again. This is repeated three times, if after three times, the file with the specified name is still not found, the menu is displayed again.
Add a definition (recursive): This option allows the user to enter new definitions in the tree. A definition can appear only once in the tree. We assume one word has one description only i.e. no two definitions will have the same word.
Remember to maintain the binary search nature of the tree when you add new elements.
Remove a definition: This option prompts the user for a word to remove. The definition with this word is deleted. If no definition with this word is found, an appropriate message is displayed.
Remember to maintain the binary search nature of the tree when you add new elements.
Search for a definition: This option allows the user to search for the definition of a word in the tree.
Remember to maintain the binary search nature of the tree when you add new elements.
Print Dictionary: This prints all the definitions sorted lexicographically by word.
Remember to take advantage of the binary search nature of the tree while doing the search.
Exit – Terminates the program after saving all the tree in another text file.
Notes:
• All methods listed above except the delete option should be written recursively. If a method is not written recursively, you will get partial credit for it.
• Define the tree from scratch. Do not re-use JAVA APIs for any sort of trees.
• Make sure the tree is a binary search tree and remains so throughout the execution of the program.
Q2. Implement a directed graph using adjacency lists. The nodes in the graph store int values. Implement the following methods in class Graph:
addVertex (int i): creates a new vertex with value i and adds it to the graph
deleteVertex (int i): removes vertex i with all edges incident at it.
degree(int i ): computes and returns the degree of vertex i
adjacent (int u, int v): returns true if edge (u, v) exists in the graph.
connected (int u, int v): returns true if there is path from u to v or one from v to u.
reverseGraph(): returns graph G’ where all edges in the graph are reversed
complement(): returns another graph G’ that is the complement of the graph.
WARNING
Cheating is a very serious offense and will not be tolerated. Copying someone else’s material or supplying others with material will be equally penalized. The policy is that, as a minimum, both, the supplier of the material and the receiver will get a zero grade on the assignment or exam in question. This could result in a failing grade for the course and suspension or expulsion from the university. The same applies to plagiarism (presenting someone else’s work as being one’s own work).
DEADLINE POLICY
Deadlines for submitting assignments will be announced in class or on the assignments. They are firm. Students must respect them. A student failing to meet the deadline will get 5% of the grade deducted per day late. A student cannot replace an assignment with another one. If he or she fails to submit an assignment, a zero will be scored on the missed assignment. To illustrate, if the student submits assignments 1 and 3 only, he or she will get a 0 on Assignment 2, Assignment 1 or 3 cannot compensate for the missed assignment. This assignment cannot be submitted beyond May 4, 2022.
