Homework answers / question archive / CMSC 350 Project 3 The third programming project involves writing a program that allows the user to enter a binary tree in a parenthesized prefix format and then allows it to be categorized and allows various features of that tree to be displayed

CMSC 350 Project 3 The third programming project involves writing a program that allows the user to enter a binary tree in a parenthesized prefix format and then allows it to be categorized and allows various features of that tree to be displayed

Computer Science

Share With

CMSC 350 Project 3 The third programming project involves writing a program that allows the user to enter a binary tree in a parenthesized prefix format and then allows it to be categorized and allows various features of that tree to be displayed. An example of a tree written in the input format is the following: (A(G(j)(1))(z(5))) In the above example, data in each node of the tree contains a single alphanumeric character. No spaces are permitted. Each tree is enclosed in parentheses. Inside those parentheses, after the single character are either zero, one or two subtrees also enclosed in parentheses. When only one subtree is present, it is the left subtree and when two are present, they represent the left and right subtrees. So the above string represents the following binary tree: A G j z 1 5 The various categorizations include the following: 1. Whether the binary tree is balanced, which means for each node in the tree, the absolute difference between the height of its left and right subtrees is at most 1. The above binary tree is balanced. 2. Whether the binary tree is full. A full binary tree has the maximum number of nodes for a tree of its height. The above tree is not full because a tree of that height can contain 7 nodes, but the above tree only has 6. 3. Whether the binary tree is proper. In a proper binary tree, every node has either 0 or 2 children. The above tree is not proper because the node containing z has only one child. In addition, the program should allow the user to request that each of the following features of the tree be displayed: 1. The height of the tree. The height of a tree is the maximum level of all of its nodes. The root node containing A is at the level 0. Because all three leaf nodes in the above tree are at level 2, its height is 2. 2. The number of nodes in the tree. As previously mentioned, the above tree has 6 nodes. 3. An fully parenthesized inorder traversal of the tree. The following should be displayed as the inorder traversal of the above tree: ((( j ) G ( 1 )) A (( 5 ) z )) This project should consist of three classes. The main class should create a GUI that allows the user to input a tree in the above described format and then construct the tree once the Make Tree button is clicked. The GUI should look as follows: The GUI must be generated by code that you write. You may not use a drag-and-drop GUI generator. The second class should be the BinaryTree class, which should contain a static nested class to define the nodes of the binary tree, together with a constructor that is called when the Make Tree button is clicked and is supplied the string representation of the tree and constructs the actual tree from that string. In addition, it should have public methods that are called when each of the remaining six buttons are clicked. All of those public methods should have corresponding private methods that accomplish their tasks using recursion. The third class should be named InvalidTreeSyntax, which defines a checked exception. It should be thrown when a invalid string is supplied and the Make Tree button is clicked. It should be caught in the main class and a JOptionPane window should be displayed that describes the reason for the invalid syntax. You are to submit two files. 1. The first is a .zip file that contains all the source code for the project. The .zip file should contain only source code and nothing else, which means only the .java files. If you elect to use a package the .java files should be in a folder whose name is the package name. Every outer class should be in a separate .java file with the same name as the class name. Each file should include a comment block at the top containing your name, the project name, the date, and a short description of the class contained in that file. 2. The second is a Word document (PDF or RTF is also acceptable) that contains the documentation for the project, which should include the following: a. A UML class diagram that includes all classes you wrote. Do not include predefined classes. You need only include the class name for each individual class, not the variables or methods b. A test plan that includes test cases that you have created indicating what aspects of the program each one is testing c. A short paragraph on lessons learned from the project Grading Rubric Criteria Design Meets Does Not Meet 20 points 0 points GUI is hand coded and matches required design (5) GUI is generated by a GUI generator or does not match required design (0) BinaryTree class contains a static nested class to define the nodes and all the required methods (5) BinaryTree class does not contain a static nested class to define the nodes and all the required methods (0) InvalidTreeSyntax class defines a checked exception as specified (5) InvalidTreeSyntax class does not define a checked exception as specified (0) Recursion is used to accomplish each binary tree operation (5) Recursion is not used to accomplish each binary tree operation (0) 60 points Functionality Correctly builds a binary tree from its parenthesized representation (10) Does not correctly build a binary tree from its parenthesized representation (0) Correctly detects syntax errors in the parenthesized representation, and throws an exception, catches it and displays an error (10) Does not correctly detect syntax errors in the parenthesized representation, or does not throw an exception, catch it and display an error (0) Correctly determines whether a binary tree is balanced (10) Does not correctly determine whether a binary tree is balanced (0) Correctly determines whether a binary tree is full or proper (10) Does not correctly determine whether a binary tree is full or proper (0) Correctly calculates the height and number of nodes in a binary tree (10) Does not correctly calculate the height or number of nodes in a binary tree (0) Correctly displays the binary tree with an inorder representation (10) Does not correctly display the binary tree with an inorder representation (0) 10 points Test Plan Documentation 0 points 0 points Test cases include balanced and unbalanced binary trees (3) Test cases do not include balanced and unbalanced binary trees (0) Test cases include binary trees that are full and trees that are not (2) Test cases do not include binary trees that are full and trees that are not (0) Test cases include binary trees that are proper and trees that are not (2) Test cases do not include binary trees that are proper and trees that are not (0) Test cases include a variety of input strings with syntax errors (3) Test cases do not include a variety of input strings with syntax errors (0) 10 points 0 points Correct UML diagram included (3) Lessons learned included (4) Comment blocks included with each Java file (3) Correct UML diagram not included (0) Lessons learned not included (0) Comment blocks not included with each Java file(0) CMSC 350 Project 4 The fourth programming project involves writing a program that accepts information contained in a file about the class dependencies in a Java program and creates a directed graph from that information. From the directed graph, it produces two different kinds of displays of those dependency relationships. A sample input file is shown below: ClassA ClassB ClassC ClassE ClassJ ClassI ClassC ClassE ClassJ ClassD ClassG ClassA ClassB ClassF ClassH ClassB ClassC The first name of each line of the file is a Java class upon which other classes depend. The remaining names are the classes that depend upon the first class on that line. The first line of the above file, for example, indicates that ClassA has three classes that depend upon it, ClassC, ClassE and ClassJ. A class that have does any classes that depend on it, need not appear at the head of any line. The main method in the class for this project should allow user select the input file from the default directory by using the JFileChooser class. It should then add the edges to a directed graph that defines these class dependencies. A second class, DirectedGraph, should be a generic class, whose generic parameter specifies the type of the labels that are associated with the vertices of the graph. The internal representation of the graph should be the alternate adjacency list representation illustrated in Figure 10.7 of our textbook Object-Oriented Data Structures Using Java. Unlike that graph, however, this graph will not be a weighted graph. It should contain a method that allows edges to be added to the graph, which is how the main method will initially build the graph. It should also contain a method that performs a depth-first search of that graph. The pseudocode for that search is show below: depth_first_search(vertex s) if s is discovered perform cycle detected action return perform add vertex action mark s as discovered perform descend action for all adjacent vertices v depth_first_search(v) perform ascend action mark s as finished When the method in the DirectedGraph class that initiates the depth first search is called, it should first initialize all the vertices to the undiscovered state and begin the search at the vertex that corresponds to the first name in the input file. Another method in the DirectedGraph class should then allow the main method to display any unreachable classes by examining all the vertices of the graph to see which remain undiscovered. This project should contain a generic interface named DFSActions, whose generic parameter again specifies the type of the labels that are associated with the vertices of the graph. It should contain four method signatures that correspond to the four actions performed in the depth first search: cycle detected, process vertex, descend and ascend. There should be two additional classes that both implement the aforementioned interface. The first, Hierarchy, should produce a hierarchical representation of the class dependencies. Circular dependencies should be flagged. For the above input file, the following hierarchical representation should be produced: ClassA ClassC * ClassE ClassB ClassD ClassG ClassF ClassH ClassJ ClassB ClassD ClassG The asterisk after ClassC results from the fact that ClassC depends upon ClassA and ClassA depends upon ClassC. The Hierarchy class should override the toString method, which should return a string that contains the above, after having performed the depth-first search. The other class that implements the DFSActions interface should be ParenthesizedList. It should produce an alternate representation that is also returned by its toString method. For the above input file, the following hierarchical representation should be produced: ( ClassA ( ClassC * ClassE ( ClassB ( ClassD ClassG ) ClassF ClassH ) ClassJ ( ClassB ( ClassD ClassG )))) The main method should produce both representations. In addition it should display the unreachable classes by calling the previously mentioned method. For the above input file, the following unreachable class should be identified: ClassI is unreachable Code duplication should be avoided. In particular, the depth first code should not be duplicated. You are to submit two files. 1. The first is a .zip file that contains all the source code for the project. The .zip file should contain only source code and nothing else, which means only the .java files. If you elect to use a package the .java files should be in a folder whose name is the package name. Every outer class should be in a separate .java file with the same name as the class name. Each file should include a comment block at the top containing your name, the project name, the date, and a short description of the class contained in that file. 2. The second is a Word document (PDF or RTF is also acceptable) that contains the documentation for the project, which should include the following: a. A UML class diagram that includes all classes you wrote. Do not include predefined classes. You need only include the class name for each individual class, not the variables or methods b. A test plan that includes test cases that you have created indicating what aspects of the program each one is testing c. A short paragraph on lessons learned from the project Grading Rubric Criteria Design Meets Does Not Meet 20 points 0 points Includes a generic DirectedGraph class that represents the graph with the alternate adjacency list representation (6) Does not include a generic DirectedGraph class or does not represents the graph with the alternate adjacency list representation (0) Includes a generic class DFSActions that Does not include a generic class contains methods for four actions DFSActions that contains methods for performed in the depth first search (4) four actions performed in the depth first search (0) Includes required two class that implement the DFSActions interface (5) Does not include required two class that implement the DFSActions interface (0) Avoids duplication of the depth-first search code (5) Does not avoid duplication of the depth-first search code (0) 60 points Functionality Test Plan 0 points Reads in file and produces graph representation as specified (10) Does not read in file or does not produce graph representation as specified (0) Displays correct hierarchical representation of class hierarchy (15) Does not display correct hierarchical representation of class hierarchy (0) Displays correct parenthesized representation of class hierarchy (15) Does not display correct parenthesized representation of class hierarchy (0) Correctly annotates circular dependencies (10) Does not correctly annotate circular dependencies (0) Correctly lists unreachable classes (10) Does not correctly list unreachable classes (0) 10 points 0 points Test cases include a graph with circular dependencies (3) Test cases do not include a graph with circular dependencies (0) Test cases include a graph with no circular dependencies (2) Test cases do not include a graph with no circular dependencies (0) Test cases include a graph with unreachable classes (3) Test cases do not include a graph with unreachable classes (0) Test cases include a graph with no unreachable classes (2) Test cases do not include a graph with no unreachable classes (0) 10 points 0 points Documentation Correct UML diagram included (3) Correct UML diagram not included (0) Lessons learned included (4) Comment blocks included with each Java file (3) Lessons learned not included (0) Comment blocks not included with each Java file(0) 1:53 1 All LTE learn.umgc.edu Store. View Graded Rubric 73% Overall Feedback Good solution as far as what you presented. But missing the variety of output test cases that needed to be demonstrated to adequately demonstrate the code in this case. If you expand your output to show a more complete set of testing and execute your code to ensure you meet the required testing then I can upgrade to show you have the required functionality demonstrated and the required testing. Nice UML diagram. Good reflection. * View Graded Rubric 0 % 1:53 1 All LTE learn.umgc.edu Store. View Graded Rubric 73% Overall Feedback Good solution as far as what you presented. But missing the variety of output test cases that needed to be demonstrated to adequately demonstrate the code in this case. If you expand your output to show a more complete set of testing and execute your code to ensure you meet the required testing then I can upgrade to show you have the required functionality demonstrated and the required testing. Nice UML diagram. Good reflection. * View Graded Rubric 0 %