Description

Collaboration
IMPORTANT
1. Collaborative coding is strictly prohibited. Your assignment submission must be strictly your code. Discussing anything beyond assignment requirements and ideas is a strictly forbidden form of collaboration. This includes sharing code, discussing code itself, or modelling code after another student’s algorithm. You can not (even with citation) use another student’s code.
2. Discuss and share ideas with other programmers as much as you like, but make sure that when you write your code that it is your own. A good rule of thumb is to wait 20 minutes after talking with somebody before writing your code. If you exchange code with another student, write code while discussing it with a fellow student, or copy code from another person’s console, then this code is not yours.
4. Cite all sources of code that you hand-in that are not your original work. You can put the citation into comments in your program. For example, if you find and use code found on a web site, include a comment that says, for example:
# the following code is from https://www.quackit.com/python/tutorial/python_hello_world.cfm.
Use the complete URL so that the marker can check the source.

Late Penalty:

LATE ASSIGNMENTS WILL NOT BE ACCEPTED

Goal

Trees are invaluable data structures in software. In this assignment, you will write the code that will create a binary search tree (BST) of unique words from a given input text file, and also keep track of the frequency of the words in the text. For example:

Example 01: Input text file
“example01.txt” Resulting BST

This is a test. This is a test.
This is a test. This is a test.
This is a test. This is a test.
This is a test. This is a test.
This is a test.

Example 02 – Input text file “example02.txt”

The first second was alright, but the second second was tough.

Resulting BST

The nodes from the BST store the word itself and its frequency in the input text file. Using this structure for a tree, it is possible to find if a word occurs in the text in O(log2n) (i.e., if the tree is of minimum height) as well as the number of times the word occurs in the text.

Specifications for reading and processing the input text file:
• All text will be considered to be lower-case, even if the word in the file has an upper-case character as the first character, or even if it is all upper-case, or a mixture of upper- and lower-case.
• Words are delimited with spaces.
• All punctuation will be ignored.
• Hyphenated words will be considered as two words (or stated another way, the hyphen is a delimiter just like a space).
• You should use String[] words = line.replaceAll(“[^0-9a-zA-Z ]”, ” “).toLowerCase().split(“\s+”);
Instructions

Write the Java program that will do the following:
You will be requesting input from System.in, and you will be opening a file in your program to read as input as well. You will be writing output to System.out.
1. Request the user for the name of a text file.
This should be an ASCII text file. Example are given with the assignment on the course website. Example (display screen) for example01.txt:

>java CPSC319W20A3
>Enter the input filename: example01.txt

2. Use the words from the input files to create the BST specified in the previous page. You will obviously have to do the conversions to lower-case and take care of all of the other characters that do not make up the word as defined above.

3. When the tree has been created, it should supply the following information as a display output:
(3.1) The total number of words in the file. (total nodes)
Use either IN-ORDER, PRE-ORDER, or POST-ORDER traversal., counting the number of times you visit each node in the BST.
(3.2) The number of unique words in the file. (total nodes with freq=1)
Use either IN-ORDER, PRE-ORDER, or POST-ORDER traversal., counting the number of nodes visited containing the word with frequency = 1
(3.3) The word which occurs most often and the number of times that it occurs.
Use either IN-ORDER, PRE-ORDER, or POST-ORDER traversal., looking for the word(s) with the largest frequency.
(3.4) The maximum height of the tree.
Implement the algorithm maximumDepth() as given below:

int maxDepth(Node node)
{
if (node == null) return 0; else {
/* compute the depth of each subtree */ int lDepth = maxDepth(node.left); int rDepth = maxDepth(node.right);

/* use the larger one */ if (lDepth > rDepth) return (lDepth + 1); else
return (rDepth + 1);
}
}

Example (display screen for question #3) for example01 using POST-ORDER traversal
(i.e., left, right, node):

Example (display screen for question #3) for example02 using POST-ORDER traversal
(i.e., left, right, node):

4. The user should also be able to request information about any word that is input when requested.
The result should be whether the word exists, and the number of times it
appears (i.e., its frequency). Use binary search.

Example (display screen) for example01:

Hand-In (digitally to D2L dropbox)
1. Your source code file that generates the output in the form requested (in specified format [Java8]). The README.md file should include description of which class begins execution of your submitted code. For example, “CPSC319S21A3.java” is my main class.
2. Include all of the above items in a zipped folder (standard ZIP) titled CPSC319S21A3-LASTNAME-ID.zip before submission to the D2L dropbox for assignment 3.
Grading
• Assignment grades will be base equally on the two submitted components as described on grading summary

• Source code that does not compile or produces run-time errors will receive a grade of 0%.

• Code that produces incorrect output (Ex. wrong format of output) will be penalized appropriately.

Assignment grading specification is as follows.

GRADING SUMMARY

PROGRAM: /20
TOTAL /20

Name:

ID:

PROGRAM

Program builds correctly Yes No
Runs: completes with zero run-time errors Yes No
IMPORTANT: Source code that does not compile or produces run-time errors will receive 0%

Criteria TOTAL
Functionality: produces correct output
Q1 and Q2: (3 marks)
Q3: (15 marks)
Q4: (2 marks)
Traversal (inorder, preorder, postorder) – (12 marks)
Readability: code is clear and easy to read (3 marks)
Generality: handle variety of input and is reasonable error proof (2 marks)
Documented: code classes/functions/inline commented (3 marks)
TOTAL: /40