Final 2020, questions PDF

Preview

Summary

Download Final 2020, questions PDF

Description

SUMMER 2020: FINAL EXAM (Take-Home) COMP-2120 Object-Oriented Programming Using Java Saturday, August 22, 2020 School of Computer Science University of Windsor

READ THE FOLLOWING INSTRUCTION BEFORE GOING TO THE QUESTIONS • The time limit is 5 hours. • The exam is out of 80 marks. • Before starting this exam, make sure that you download, complete the SignaturePage file, and include it with your submitted files to Blackboard. • For every problem: o You should download its corresponding java tester program to test your code with it. o Use an IDE on your local computer. DO NOT USE ONLINE COMPILERS OR NOMACHINE. O THOROUGHLY AND CAREFULLY READ THE DESCRIPTION OF THE QUESTION. o Develop the required program by creating a separate java file for each required class. o Note that this course is about developing Object-Oriented programming and not just writing a procedural code that you do in a programming language like C. Therefore, you must create required java classes for the concepts you have been asked for. Otherwise, You will lose the significant part of the mark assigned to the problem. Page 1 of 7

o You might need to create one or more java classes, separately, and use object(s) of one in another one, to fulfill the problem requirements. o Compile your java files. Then using the corresponding tester class provided, test your code. Compare the output of your program with the one provided. If it is not similar to it, go back and fix your code and test it again. o After making sure about the correctness of your code, in terms of compile-time, runtime fatal, and non-fatal run-time errors, include the Java file into your final submission. • FOR ANY QUESTION, IF YOUR JAVA FILE HAS COMPILE-ERRORS, YOU WILL LOSE HALF OF THE ORIGINAL MARK. THEN, YOUR CODE WILL BE CHECKED LOGICALLY. • DO NOT USE ANY NON-STANDARD LIBRARY. • DO NOT CHANGE THE NAMES OF THE JAVA FILES THAT ARE INDICATED. • DO NOT ALTER THE TESTER CLASS FILES. • When you are done, SUBMIT the Java files, INDIVIDUALLY, on Blackboard, along with the completed SignaturePage file. • DO NOT SUBMIT ZIP FILES. • DO NOT SUBMIT COMPILED FILES FOR ANY PROBLEM. OTHERWISE, YOU WILL RECEIVE ZERO FOR THAT PROBLEM. • ONLY SUBMIT JAVA FILES. • YOU SHOULD SUBMIT YOUR FILES BEFORE THE DEADLINE.

GOOD LUCK!

Page 2 of 7

Problem 1 (60 marks) Part A: Create a class HugeInteger which uses a 40-element array of digits to store integers as large as 40 digits each. Provide the following public methods in this class: • parse: It receives a String, that only contains digits and possibly a negative sign, extracts each digit using method charAt and places the integer equivalent of each digit into the integer array. • add: It returns the addition of two huge integers, the implicit object parameter and explicit object parameter, as a HugeInteger object. • subtract: It returns the subtraction of two huge integers, the implicit object parameter and explicit object parameter, as a HugeInteger object. • You might want to create some private helper methods. For instance, you can develop a method addPositive to add two positive numbers and call it when needed from the add method. Note that in this case, these helper methods are private and can't be used outside of the class. Note 1: Create a final static variable, set it to 40, to keep the maximum length of a huge number. Therefore, we can change this value and recompile the code to have different length, if needed. Note 2: For each of the two methods, add and subtract, if an overflow happens, i.e. the result has more than 40 digits, you must properly handle the exception by providing a message, skip the operation, and send back the control to the caller to show the message. The execution of the program should not be terminated in this case. You can simply throw the RuntimeException in this case and catch it properly in the main method of the tester class. Also, for comparing HugeInteger objects, provide the following methods: • isGreaterThan • isGreaterThanOrEqualTo • isLessThan • isLessThanOrEqualTo Each of the above four methods is a predicate method that returns true if the relationship holds between the two implicit and explicit HugeIntegers object arguments and returns false otherwise. Also develop the method: • isZero: It will return true if the huge number is zero, false otherwise. that will return true if the number is zero, and false otherwise. Also, override the two following standard methods: • toString: It will return string representation of the number, without leading zeros. • equals: It will return true if two huge numbers are equal, false otherwise. Also, Implement the Comparable interface for the HugeInteger class and therefore implement the required method for it. Inside this method, for simplicity, you can use the two methods, isGreaterThan and isLessThan, for the comparison. Note that the return value of this method should be standard. Page 3 of 7

Bonus (5 extra marks): Provide a method multiply for the multiplication operation. Part B: Complete the provided HugeIntegerTester class, which reads some huge integer numbers from an external file "input.txt", that is provided to you, and store them into an ArrayList of HugeInteger objects. Then, do the following operations and print the outputs into an external file "output.txt". • Add the two huge numbers stored in the first and second elements of the ArrayList and print the result into the output file • Add the two huge numbers stored in the third and fourth elements of the ArrayList and print the result into the output file • Create a new HugeInteger number, which is the largest possible number that can fit, i.e. has forty digits of 9 in it. • Add the above newly huge number to the first element and print the result into the output file. You need to check if the result is overflown. • Subtract the huge number stored in the second element from the first element of the ArrayList and print the result into the output file • Subtract the huge number stored in the third element from the fourth element of the ArrayList and print the result into the output file • Check the equality of the fourth and fifth elements and print the result into the output file • Check the equality of the fourth and sixth elements and print the result into the output file • Compare the first two huge numbers with the four comparison methods and print the results into the output file • Check if the sixth element is zero or not and print the result into the output file • Check if the seventh element is zero or not and print the result into the output file • Call the method that you have implemented because of implementing Comparable interface, to compare the first and second elements and print the result into the output file • In the end, make sure you properly close the input and output files. Hints: • You should be able to keep huge integer numbers with a maximum of 40 digits without considering the sign of the number. Therefore, it is better to keep the sign of the number separately in a boolean variable, true for positive and false for negative. • Keep all the java files and input/output files in one folder during the development to not have any file path issues. • You can assume that the content of the input file is valid. Therefore, no need to check the validity of the input values.

You should submit the files HugeInteger.java and

HugeIntegerTester.java as the answer to this problem. Page 4 of 7

The expected outputs of the HugeIntegerTester class, which is stored in the output.txt file, should be similar to the lines on the next page: 1234567890987654321023456789 + 98765432100112233 = 1234567891086419753123569022 ----------9753124680 + -16891034567890987654321023489 = -16891034567890987664074148169 ---------9999999999999999999999999999999999999999 + 1234567890987654321023456789 = Overflow ---------1234567890987654321023456789 98765432100112233 = 1234567890888888888923344556 ----------9753124680 -16891034567890987654321023489 = 16891034567890987644567898809 ----------16891034567890987654321023489 is not equal to 23489 ----------16891034567890987654321023489 is equal to -16891034567890987654321023489 ---------1234567890987654321023456789 is greater than or equal to 98765432100112233 ---------1234567890987654321023456789 is greater than 98765432100112233 ---------1234567890987654321023456789 is not less than or equal to 98765432100112233 ---------1234567890987654321023456789 is not less than 98765432100112233 ----------16891034567890987654321023489 is not zero ---------0 is zero ---------Comparing 1234567890987654321023456789 and 98765432100112233 will result 1

Page 5 of 7

----------

Problem 2 (20 marks) In a paint program, a "Flood Fill" fills all empty pixels of a drawing with a given color, stopping when it reaches occupied pixels. In this problem, you will implement a simple variation of this algorithm, flood-filling a 10 x 10 array of integers that are initially 0: 1. Indicating for the starting row and column 2. Push the (row, column) pair into a stack 3. Repeat the following operations until the stack is empty a) Pop off the (row, column) pair from the top of the stack b) If it has not yet filled, fill the corresponding array location with a number 1, 2, 3, and so on (to show the order in which the square is filled) c) Push the coordinates of any unfilled neighbors in the north, east, south, or west direction on the stack 4. Print the entire array Tasks: • Create a generic class Pair, with: o Two type parameters. o Two instance variables, with the corresponding types from the above two type parameters. o Corresponding getter methods for the two instance variables. • Create a class Grid, with: o A final static variable that indicates the number of rows or columns, with value 10. Note that we assume that the number of rows and columns are equal. o A stack of pairs. The data types of the two type parameters are Integer. o A two-dimensional array of integers, based on the value of the final static variable defined above. o A method called floodfill that receives the starting point and fill the array using the stack, based on the algorithm given above. o A method called reset that resets all the array elements to zero. o Overridden method toString that returns the string representation of the array as a table. • Test your development with the given tester class, FloodFillTester.java, to make sure about the correctness of your code.

Page 6 of 7

You should submit the files Pair.java and this problem. Expected outputs on the next page: 93 92 15 14 16 17 19 21 23 25

91 90 12 11 13 18 20 22 24 26

89 88 9 8 10 59 58 57 28 27

87 86 6 5 7 60 56 55 30 29

85 84 2 1 4 61 54 53 32 31

83 82 81 3 63 62 52 51 34 33

94 80 79 78 65 64 50 49 36 35

95 97 77 76 67 66 48 47 38 37

96 100 98 99 75 73 74 72 69 71 68 70 46 44 45 43 40 42 39 41

1 3 5 7 9 11 13 15 17 19

2 4 6 8 10 12 14 16 18 20

86 85 84 83 54 53 52 51 22 21

88 87 82 81 56 55 50 49 24 23

90 89 80 79 58 57 48 47 26 25

92 91 78 77 60 59 46 45 28 27

94 93 76 75 62 61 44 43 30 29

96 95 74 73 64 63 42 41 32 31

98 100 97 99 72 70 71 69 66 68 65 67 40 38 39 37 34 36 33 35

100 99 62 61 60 59 22 21 20 19

98 97 64 63 58 57 24 23 18 17

96 95 66 65 56 55 26 25 16 15

94 93 68 67 54 53 28 27 14 13

92 91 70 69 52 51 30 29 12 11

90 89 72 71 50 49 32 31 10 9

88 87 74 73 48 47 34 33 8 7

86 85 76 75 46 45 36 35 6 5

84 83 78 77 44 43 38 37 4 3

82 81 80 79 42 41 40 39 2 1

Page 7 of 7

Grid.java as the answer to...