The University of Western Ontario CS1027 Computer Science Fundamentals II Final Exam April 24, 2020 For the final examination you are required to write two Java classes, specified in the following sections. Several Java classes are provided which you must use to answer the exam. Study these classes to see which public methods you can use. You CANNOT modify in any manner any of the classes provided. If you modify the given classes, you will be penalized. You CANNOT use any other Java classes than the ones provided, this includes any classes from the standard Java libraries. To be clear, you CANNOT use any of the Java classes from the Java libraries. You must submit ONLY Answers.txt, Answers1.java and Answers2.java through OWL by April 28 at 11:00 am Eastern Daylight Time (time zone of London, Ontario). Late submissions will be accepted until April 28 at 11:55 am, but submissions after April 28 at 11:00 am, will receive a late penalty of 1 mark for each 5 minutes that they are late. So, submissions on April 28 between 11:01 am and 11:05 am will receive a late penalty of 1 mark; submissions on April 28 between 11:06 am and 11:11 am will receive a late penalty of 2 marks, and so on. No submissions will be accepted after April 28 at 11:55 am. Your code must be reasonably legible; please add comments to those parts of your code that you think might not be easy to understand. You will not be marked on your comments, but if the marker cannot understand your code you might lose some marks. Question 1 (26 marks) To answer the first question, you will need to use the provided Java classes: Question1.java, ClassA.java, ClassB.java, Exception1.java, Exception2.java and Exception3.java. One of the files provided is called Answers1.java. In the first two lines of this file you need to write your name and student ID. You must implement in this file a class called Answers1 such that when program Question1.java is executed the following output is produced: Test 1 passed Test 2 passed Test 3 passed methodB1 threw the exception methodB2 threw the exception Test 4 passed methodB1 threw the exception Test 5 passed Test 6 passed The output must be exactly as specified above, no additional messages must be printed by your code. Study class Question1.java to understand what functionality Answer1.java is required to provide. Your implementation of Answer1.java must satisfy the following requirements: o You cannot implement a method called m in Answer1.java. Line 7 of Question1.java contains the statement var1.m(1) where var1 is a variable of type Answer1. Explain how method m1 can be invoked in that statement even though method m1 is not implemented in class Answer1.java. Write your answer in Answers.txt. (Hint. Study the java classes provided, one of them implements a method called m.) o You must implement a method called numObjectsAnswer1 with the following signature public int numObjectsAnswer1 () that returns the number of objects of type Answer1 that have been created by program Question1.java. You also need to implement the constructor for the class Answer1.java. How can method numObjectsAnswer1 know how many objects of type Answer1 have been created by another Java class? (Hint. Use an instance variable. What type of variable do you need?) Write your answers in Answers.txt. o You must also implement a method called method1. Study how this method is invoked from Question1.java to determine what the signature of this method must be. In this method you must declare a variable of type ClassB: ClassB var = new ClassB(); Then you must invoke methods methodB1(test) and methodB2(test) of ClassB, where test is the parameter of method1. Since these methods can throw exceptions, their invocations must be placed inside a try-catch block. You can use only ONE try-catch block inside this method, so your code will look like this: try { var.methodB1(test); … var.methodB2(test); } catch (…) {…} … o If an exception of type Exception1 is thrown inside this try-catch block, the exception must be caught and method m(test) must be invoked. o If an exception of type Exception2 is thrown inside this try-catch block the exception must be caught and an exception of type Exception3 must be thrown. o If an exception is thrown by methodB1 then the message “methodB1 threw the exception” must be printed; if an exception is thrown by methodB2 then the message “methodB2 threw the exception” must be printed. Your implementation SHOULD NOT print both messages, only one message must be printed every time that an exception is thrown when running this method. If no exception is thrown by methodB1 or methodB2, then no message must be printed by method1. Since both, methodB1 and methodB2 throw Exception2, how can your implementation of method1 know which of them threw the exception? Write your answer in Answers.txt. Question 2 Walda the Warrior is attempting to walk through the Perdition Forest, which has a lot of forks in the road. The forest is inhabited by two types of monsters: ogres and goblins. The roads that Walda can use to cross the forest are represented with two binary trees with each fork in a road, bend in a road, and end of a road indicated by a node of a tree. At each node of the first tree there is a set of ogres; at each node of the second tree there is a set of goblins. Ogres and goblins try to prevent Walda from getting across the forest. Walda must fight the monsters that she encounters as she traverses a path; if she successfully defeats her foes, she can continue along the path that she has chosen, but if she is defeated, she must turn back and try a different path. Specifications about when Walda will win and when she will lose a battle are given below. One of the files given to you is called Answer2.java. This class contains the signatures of 3 methods that you must implement, and which are explained below. 1. Method mergeToLinkedList (25 marks) This method has the following signature public LinkedList mergeToLinkedList(LinkedList list1, CircularArray list2) Classes LinkedList and CircularArray are provided. Class LinkedList represents a linked list where each node stores an integer value. Values are stored in increasing order in this list. Class CircularArray represents a circular array storing integer values sorted in increasing order. Please study these classes to learn which public methods they provide; you can use any of the public methods in any of the provided classes in your solution. Study also class ListNode. Note that in class CircularArray the value of front is not zero and instance variable rear is the index of the last data item stored in the circular array. Also note method getArray returns a reference to the array where the data items are stored. Method mergeToLinkedList must create and return an object of the class LinkedList containing all values in list1 and list2 stored in increasing order of value. You CANNOT use an auxiliary array, circular array, linked list, stack, or any other data structure to implement this method. The ONLY data structures that you can use are the LinkedList list1 and CircularArray list2. If you use any other data structures you will be heavily penalized. Note that class LinkedList has 3 instance variables: front, rear, and count. Once you have created the new linked list storing in order the values from list1 and list2 you MUST use methods setFront, setRear, and setNumDataItems from class LinkedList to set the values of the aforementioned instance variables. You can assume that list1 and list2 do not have common values. For example, if list1 and list2 are: Then the merged list produced by mergeToLinkedList must be as follows 2. Method mergeTrees (25 marks) This method has the following signature public TreeNode mergeTrees(TreeNode r1, TreeNode r2) Class TreeNode is provided and it represents a node of a binary tree. Please study this class to learn the public methods that you can use. Each TreeNode object stores a data item of type
either LinkedList or CircularArray. The first parameter of method mergeTrees is the root of a binary tree and the second parameter is the root of a second binary tree. Method mergeTrees must merge the two trees with roots r1 and r2 and it must return the root of the merged tree. This method MUST be recursive. The merging must be done in the following manner: • If r1 and r2 are null then the merged tree is null also. • If one of r1 or r2 is null then the merged tree is the tree that is not empty. Note that the non-empty tree might store objects of type CircularArray. • If neither r1 nor r2 is null, then a new node n must be created to be the root of the merged tree. The data stored in n is the combination of the data stored in r1 and the data stored in r2 obtained by invoking method mergeToLinkedList. Note that one of the nodes r1, r2 will store a data item of type LinkedList and the other one will store a data item of type CircularArray. To invoke method mergeToLinkedList, first you 3 7 9 1 5 front rear count = 2 count = 3 0 1 2 3 4 front = 3 rear = 0 array list1 list2 1 3 front rear count = 5 5 7 9 need to determine which node r1 or r2 stores a data item of type LinkedList and which one stores a data item of type CircularArray. To obtain the data stored in a node use method getData from class TreeNode. Observe that class TreeNode has a parameter T specifying the type of data stored in a node; so, it is not obvious whether the data item stored in a node is of type LinkedList or CircularArray. How do you determine this? Write your answer in Answers.txt. Once the data item to be stored in some node n has been computed, the left child of n must be set as the tree obtained by merging the tree whose root is the left child of r1 with the tree whose root is the left child of r2. Finally, the right child of n is the tree obtained by merging the tree whose root is the right child of r1 with the tree whose root is the right child of r2. Note that in the merged tree some nodes will store an object of type LinkedList and some other nodes will store an object of type CircularArray. The following figure shows two binary trees with roots r1 and r2 and the corresponding merged tree with root n. Each node in the first tree stores a LinkedList object and each node in the second tree stores a CircularArray object. Figure 3. 3. Method defeatMonsters (24 marks) This method has the following signature public boolean defeatMonsters(TreeNode r, int attackValue) This is the method that Walda the Warrior uses to determine whether she can cross the Perdition Forest. The first parameter of this method is the root of the tree representing the forest roads and containing information about the ogres and goblins. This tree is obtained by invoking method mergeTrees, so each node of this tree stores an object of the class LinkedList or an object of the class CircularArray. The root of the tree represents the entrance to the forest and each leaf of the tree represents an exit. If the tree is empty or if there is at least one path from the root to a leaf in which Walda is able to defeat all the monsters that she encounters, then the method must return the value true. On the 4 8 12 10 2 4 5 9 r1 r2 n 10 2 10 2 10 2 10 1 4 8 1 2 4 8 10 12 1 4 5 9 10 1 2 4 8 10 A E B C D 10 2 10 2 Merged tree other hand, if there is no path from the root to a leaf that allows Walda to win every battle against the monsters, then the method must return the value false. To implement this method, you are required to perform an iterative preorder traversal of the tree (see below). Whenever a node p of the tree is visited in this traversal, the algorithm will check if Walda can defeat the monsters located there. To check whether Walda will be victorious against the monsters located in this node, this method must do the following. • The second parameter, attackValue, of this method specifies the attack value of Walda. • If node p stores a LinkedList object L, each ListNode object in L contains an integer value specifying the attack value of a monster that Walda must face. Otherwise, if node p stores a CircularArray object L each integer value stored in L specifies the attack value of a monster. • For each attack integer value v in the list L do the following: o If the attack value of Walda is larger than or equal to v, then Walda will win this battle and her attack value will increase by the attack value v of the defeated monster. o However, if the attack value of Walda is smaller than v, then she loses the battle against the monsters in node p and she must turn back. • If Walda wins all the battles against the monsters stored in node p, then she can continue the traversal of the tree. Note that if the list L is empty then Walda also can continue the traversal of the tree. Regardless of whether Walda wins or loses a battle against all the monsters in a node of the tree, after the battle her attack value is restored to its initial value specified by the parameter attackValue. For example, assume that Walda has initially attack value 2 and she faces monsters in some node p with attack values 3, 1, and 5. These attack values are stored in increasing order of value in the nodes of the list stored in node p. Walda will then first face and defeat the monster with attack value 1, after which her attack value increases to 2 + 1 = 3. Then she faces and defeats the monster with attack value 3, thus increasing her attack value to 3 + 3 = 6. Finally, she faces and defeats the last monster as her current attack value is 6 and the attack number of the last monster is 5. After defeating all these opponents Walda can move to the next node of the tree, but her attack value is reset to its initial value of 2. Consider the tree with root n in Figure 3. If the initial attack value of Walda is 2, then she will lose the battles at nodes B, D, and E, so she cannot cross the forest and method defeatMonsters in this case will return the value false. However, if the initial attack value of Walda is 3, she will lose the battle at node B, but she will win the battles at nodes A, C, and D and so in this case method defeatMonsters will return the value true. Your implementation of this method cannot use a recursive algorithm. You are provided with a Java class called ArrayStack that implements a stack. You can perform an iterative preorder traversal of a tree using a stack as follows o Create an empty stack and push into it the root of the tree. o While the stack is not empty perform the following steps: o Pop a node p out of the stack and visit this node p o If p has a right child, push that child in the stack (think about why the right child is pushed first) o if p has a left child, push that child in the stack. Testing your Code You should thoroughly test your code to make sure it works as specified. Read the specifications of all the methods carefully. To help you out and to try to make sure you understand the specifications of the methods that you must implement we provided you with a program called TestQuestion2.java. This program performs the following tests: o Test method mergeToLinkedList by passing as parameter a linked list storing values 4, 8, 12 and a circular array storing values 2 and 10. o Test method mergeTrees by passing as parameters the roots r1 and r2 of the trees in Figure 3. A second test invokes the same method but passing as first parameter r2 and second parameter r1. o Test method defeatMonsters by passing as parameter the root n of the third tree in Figure 3 and attack value 3. A second test of the same method on the same tree uses as attack value 2. Note that the above program was not intended to perform an exhaustive testing of your code. We will perform many more tests on your code, and we will check that you followed all specifications. So even if you pass the tests on TestQuestion2, that does n
ot mean that you will get 100% for this part of the exam.
