Recursion is both a mathematical and a computational concept. The purpose of this assignment is to...

 

Transcribed Image Text:

Recursion is both a mathematical and a computational concept. The purpose of this assignment is to get familiar with the recursive approach. In this assignment, you will involve constructing Java functions that use recursion to perform the same operations multiple times with different inputs, and smaller inputs to make the problem smaller. In data structures, where some operations are conceptually simple when expressed recursively but extraordinarily complex when expressed iteratively. In algorithms, where some are most naturally expressed and analyzed in recursive form. In specific programming languages, notably Erlang and Prolog, that are "pure functional" languages and therefore do not have a loop structure and must rely on recursion for "repititive" tasks. In compilers, where the concept of a recursive descent parser is fundamental. The recursion also allows us to apply an Inductive Solution, since both are practically the same: a base case and the inductive hypothesis. Induction is studied strongly in computer science to solve many problems such as the sorting problem, graphs and many other problems in algorithms. Objectives: There are 4 regular problems in this assignment and 1 bonus problem for extra credit. You may not make use of any Java classes other than incidental use of Strings, calls to System.out.println, and accessing an existing array passed to your method. The tester program will verify that your program contains no imports, no use of new, and the only uses of "." (dot) are within calls to System.out.println, accessing array .length, or followed by a digit (double literals). You are NOT allowed use for or while loops in your solutions. Any looping must be accomplished using recursion. The testing program will check your program to make sure there is no for loop or while loop and get triggered by the word in a comment. You are NOT allowed to declare static or non-static member fields - only local or parameter variables allowed. You may implement additional helper methods to use the "recursive driver" technique. Rules and Explanations: 1. Even Digit Up - Odd Digit Down: Implement the method eduodd that accept an integer (long data type). eduodd(n) returns a value which increases each of the even decimal digits of n by one and decreases each of the odd digits of n by one. Leading zero digits will disappear. The sign of eduodd(n) should be the same as n, unless n is negative and eduodd(n) is zero as seen in the last example below. Here is the examples: n eduodd(n) 0 1 n Here is the examples: 1 fibby(n) 27 36 fibby (0) = 1 3n fibby(n) = fibby([2]) + fibby([]) where n > 0 and [n] is the floor of n 4 4 2 3 2. Fibby: Implement the method fibby that accepts an integer. Fibby is mathematically defined for nonnegative values in the following way: + 987654321 -8443 4 896745230 -9552 6 LO 5 6 7 8 8 11121113 = 30002 9 11 skip this line because fibby (9) 10 11 -> skip this line because fibby (10) = 10 -11 0 3. Sparse Table Generation: Implement the method stg that accept two integers which are lower bound and upper bound. Print all consecutive values of n and fibby(n) (just the two numeric values separated by a space) where n start and n end. However, skip a line of output if the previous row printed has the same fibby value. For example, if you call stg(5, 10), it should internally iterate as below: 5 6 68 7 8-skip this line because fibby (7) 8 11 fibby (6) = 8 20 11 11 11 24 111 100 fibby (8) = 11 = fibby (8) = 11 Hence, the expected output to the console should be: 5 6 68 8 11 4. Median: Implement the method median3 that accepts an array of integers and strictly follows the below strategy. Do not create any new arrays; you will need one or more helper methods that look at portions of the existing array. Consider an array of integers. You wish to find an approximate median. You have an idea: split the array into three pieces, find the approximate median of each piece, and then calculate the median (of the three approximate medians (if you put the three approximate medians in sorted order, the one in the middle). There are a few details to consider: o If the array is one element, that element itself is its own median. o If the array is two elements, take the mean (average) which may be a fractional value. o Otherwise, there are at least three elements in the array. There are three possibilities for the length: the length is divisible by 3, it has a remainder of 1 when divided by 3, or a remainder of 2 when divided by 3. o If the length divided by 3 has a remainder of 0: Each piece should be n/3 elements. o If a remainder of 1: The first piece should consist of the first [n/3] elements The last piece should consist of the last [n/3] elements The middle piece is the remaining [n/3] elements. [n/3] rounds up. (For example, if there were 4 elements, the first piece is the first element, the last piece is the last element, and the middle two elements constitute the middle piece.) o If a remainder of 2: The first piece should consist of the first [n/3] elements The last piece should consist of the last [n/3] elements The middle piece is the remaining [n/3] elements. (For example, if there were 8 elements, the first piece is the first 3 elements, the last piece is the last 3, and the middle two elements constitute the middle piece.) You must name the file MathematicsRec.java that includes the methods as following: Method public static long eduodd(long n) public static int fibby(int n) public static void stg(int start, int end) public static double median3(int[] a) Description The method implement the problem "Even Digit Up - Odd Digit Down". The method implement the problem "Fibby". The method implement the problem "Sparse Table Generation". The method implement the problem "Median". Extra Credit: (1.0% to the final grade) Rewrite the fibby method using iterative approach and make sure it runs and produces the output correctly (you can check with your recursive version). Compare the runtime of both approaches and draw conclusion based on your observation. The extra credits are only considered according to the correctness and the usefulness of your report. Please write your report in readme.txt file that provided in the project skeleton. Implementation Guidelines: 0.8% for representing two plots (one for iteration and one for recursion) on a single graph. The file must be included in the zip file. Note: each plot must have at least 30 data points on the graph and should be consistent with data generated from ExtraCredit.java o 0.2% for conclusion of which approach is better in specific scenario and why. (must have at least 100 words) The program does not compile will receive grade of zero. Place your code in a class named MathematicsRec. Use the file MathematicsTest.java and run to have a local sanity check (please ignore this score): o Please do NOT leave any comment in the file MathematicsRec.java because the class Mathematics Test may detect some illegal restricted uses of for-loop, while-loop, dot reference, etc. and that strongly affect the tentative score (please ignore this score). requirements. Rubric: Points 50 10 5 10 15 5 LO 5 100 Categories Functionality Functionality Functionality Functionality Functionality Functionality Miscellaneous Miscellaneous Comments Compiled Mathematics Rec.java with error(s) will receive a grade of zero Compiled MathematicsRec.java with no error and no infinite run. The class MathematicsRec had method eduodd worked correctly. The class MathematicsRec had method fibby worked correctly. The class MathematicsRec had method stg worked correctly. The class Mathematics Rec had method median3 worked correctly. Compressed files as expected Used spacing, indentation appropriately and consistently Total Download: o MathematicsRec.java o Mathematics Test.java (use this file to test your functions for local sanity check and please ignore this score) o ExtraCredit.java (use this file for extra credit only) Ex Ex Gu Recursion is both a mathematical and a computational concept. The purpose of this assignment is to get familiar with the recursive approach. In this assignment, you will involve constructing Java functions that use recursion to perform the same operations multiple times with different inputs, and smaller inputs to make the problem smaller. In data structures, where some operations are conceptually simple when expressed recursively but extraordinarily complex when expressed iteratively. In algorithms, where some are most naturally expressed and analyzed in recursive form. In specific programming languages, notably Erlang and Prolog, that are "pure functional" languages and therefore do not have a loop structure and must rely on recursion for "repititive" tasks. In compilers, where the concept of a recursive descent parser is fundamental. The recursion also allows us to apply an Inductive Solution, since both are practically the same: a base case and the inductive hypothesis. Induction is studied strongly in computer science to solve many problems such as the sorting problem, graphs and many other problems in algorithms. Objectives: There are 4 regular problems in this assignment and 1 bonus problem for extra credit. You may not make use of any Java classes other than incidental use of Strings, calls to System.out.println, and accessing an existing array passed to your method. The tester program will verify that your program contains no imports, no use of new, and the only uses of "." (dot) are within calls to System.out.println, accessing array .length, or followed by a digit (double literals). You are NOT allowed use for or while loops in your solutions. Any looping must be accomplished using recursion. The testing program will check your program to make sure there is no for loop or while loop and get triggered by the word in a comment. You are NOT allowed to declare static or non-static member fields - only local or parameter variables allowed. You may implement additional helper methods to use the "recursive driver" technique. Rules and Explanations: 1. Even Digit Up - Odd Digit Down: Implement the method eduodd that accept an integer (long data type). eduodd(n) returns a value which increases each of the even decimal digits of n by one and decreases each of the odd digits of n by one. Leading zero digits will disappear. The sign of eduodd(n) should be the same as n, unless n is negative and eduodd(n) is zero as seen in the last example below. Here is the examples: n eduodd(n) 0 1 n Here is the examples: 1 fibby(n) 27 36 fibby (0) = 1 3n fibby(n) = fibby([2]) + fibby([]) where n > 0 and [n] is the floor of n 4 4 2 3 2. Fibby: Implement the method fibby that accepts an integer. Fibby is mathematically defined for nonnegative values in the following way: + 987654321 -8443 4 896745230 -9552 6 LO 5 6 7 8 8 11121113 = 30002 9 11 skip this line because fibby (9) 10 11 -> skip this line because fibby (10) = 10 -11 0 3. Sparse Table Generation: Implement the method stg that accept two integers which are lower bound and upper bound. Print all consecutive values of n and fibby(n) (just the two numeric values separated by a space) where n start and n end. However, skip a line of output if the previous row printed has the same fibby value. For example, if you call stg(5, 10), it should internally iterate as below: 5 6 68 7 8-skip this line because fibby (7) 8 11 fibby (6) = 8 20 11 11 11 24 111 100 fibby (8) = 11 = fibby (8) = 11 Hence, the expected output to the console should be: 5 6 68 8 11 4. Median: Implement the method median3 that accepts an array of integers and strictly follows the below strategy. Do not create any new arrays; you will need one or more helper methods that look at portions of the existing array. Consider an array of integers. You wish to find an approximate median. You have an idea: split the array into three pieces, find the approximate median of each piece, and then calculate the median (of the three approximate medians (if you put the three approximate medians in sorted order, the one in the middle). There are a few details to consider: o If the array is one element, that element itself is its own median. o If the array is two elements, take the mean (average) which may be a fractional value. o Otherwise, there are at least three elements in the array. There are three possibilities for the length: the length is divisible by 3, it has a remainder of 1 when divided by 3, or a remainder of 2 when divided by 3. o If the length divided by 3 has a remainder of 0: Each piece should be n/3 elements. o If a remainder of 1: The first piece should consist of the first [n/3] elements The last piece should consist of the last [n/3] elements The middle piece is the remaining [n/3] elements. [n/3] rounds up. (For example, if there were 4 elements, the first piece is the first element, the last piece is the last element, and the middle two elements constitute the middle piece.) o If a remainder of 2: The first piece should consist of the first [n/3] elements The last piece should consist of the last [n/3] elements The middle piece is the remaining [n/3] elements. (For example, if there were 8 elements, the first piece is the first 3 elements, the last piece is the last 3, and the middle two elements constitute the middle piece.) You must name the file MathematicsRec.java that includes the methods as following: Method public static long eduodd(long n) public static int fibby(int n) public static void stg(int start, int end) public static double median3(int[] a) Description The method implement the problem "Even Digit Up - Odd Digit Down". The method implement the problem "Fibby". The method implement the problem "Sparse Table Generation". The method implement the problem "Median". Extra Credit: (1.0% to the final grade) Rewrite the fibby method using iterative approach and make sure it runs and produces the output correctly (you can check with your recursive version). Compare the runtime of both approaches and draw conclusion based on your observation. The extra credits are only considered according to the correctness and the usefulness of your report. Please write your report in readme.txt file that provided in the project skeleton. Implementation Guidelines: 0.8% for representing two plots (one for iteration and one for recursion) on a single graph. The file must be included in the zip file. Note: each plot must have at least 30 data points on the graph and should be consistent with data generated from ExtraCredit.java o 0.2% for conclusion of which approach is better in specific scenario and why. (must have at least 100 words) The program does not compile will receive grade of zero. Place your code in a class named MathematicsRec. Use the file MathematicsTest.java and run to have a local sanity check (please ignore this score): o Please do NOT leave any comment in the file MathematicsRec.java because the class Mathematics Test may detect some illegal restricted uses of for-loop, while-loop, dot reference, etc. and that strongly affect the tentative score (please ignore this score). requirements. Rubric: Points 50 10 5 10 15 5 LO 5 100 Categories Functionality Functionality Functionality Functionality Functionality Functionality Miscellaneous Miscellaneous Comments Compiled Mathematics Rec.java with error(s) will receive a grade of zero Compiled MathematicsRec.java with no error and no infinite run. The class MathematicsRec had method eduodd worked correctly. The class MathematicsRec had method fibby worked correctly. The class MathematicsRec had method stg worked correctly. The class Mathematics Rec had method median3 worked correctly. Compressed files as expected Used spacing, indentation appropriately and consistently Total Download: o MathematicsRec.java o Mathematics Test.java (use this file to test your functions for local sanity check and please ignore this score) o ExtraCredit.java (use this file for extra credit only) Ex Ex Gu

Answer rating: 100% (QA)

Question 1 public static long eduoddlong n if n 0 return 0 Base case return ... View the full answer