Computing and Algorithms III Programming Assignment 2 Word Ladder Again CS-203 Spring, 2021 Problem Description You will write Java programs for the solution to this problem. Write your code with three command line arguments: the name of the dictionary file, the start word for the ladder, the goal word for the ladder. A word ladder is a sequence of words from a given starting word to a given goal word. To move from one word to another on the ladder you must apply one of the given rules. In this project you will actually be writing 2 programs: in one program, your dictionary will be stored as a binary tree, in the second your dictionary will be stored as a red-black tree. An example of a word ladder starting from the word "sick and ending with the goal word "well" is sick silk milk mill will well The above may or may not be the shortest possible word ladder from sick to well. Word Ladder Rules The goal of the word ladder is to find the shortest sequence of words from the starting word to the goal word, in which one word is next to another word in the ladder because it can be created by applying one of the rules to the preceding word in the ladder. The rules are 1. Any one letter may be removed from a word. 2. Any one letter in the word may be changed into any other letter. 3. Any two letters in the word may exchange positions in the word. 4. Any one letter may be added to the word at any location (before the first letter, after the last letter, or between any two letters in the word). For this program, the starting word does not have to be a word in the dictionary; the goal word does not have to be a word in the dictionary, but every word in the ladder between the start and goal must be in the dictionary. Analytical Timing Analysis You will be analyzing the run time efficiency of a worst case runs of your programs where the input size is the number of words in the dictionary. Dictionaries Your first program will read words from the dictionary file and insert each word into a binary search tree. Note that each word will be inserted into a right subtree of the previous word. This will have an impact on the worst case analysis that you do. Your second program will read words from the dictionary file and insert each word into a red- black tree, which we will discuss in class next week. The structure of the red-black tree will have an impact on the analysis that you do. Individual Assignment This is an individual assignment. Do not work with anyone else on this project. If you were part of a team for project 1, the code developed by the team may be used for part of this assignment, but all the new work will be done individually. Required Documents for Grading You will turn in the following three documents, there will be a separate blackboard category for each: 1. Word Ladder Program Using Binary Search Tree Dictionary (a) Required comments include initial class comments naming the author of the class code and the purpose of the class, as will as a comment stating the purpose of each method. (b) Meaningful identifier names are required, naming conventions must be followed. (c) This program is worth up to 25 points. 2. Word Ladder Program Using Red-Black Tree Dictionary (a) Required comments include initial class comments naming the author of the class code and the purpose of the class, as will as a comment stating the purpose of each method. (b) Meaningful identifier names are required, naming conventions must be followed. (c) This program is worth up to 50 points.