Recursion is both a mathematical and a computational concept. The purpose of this assignment is to...
Fantastic news! We've Found the answer you've been seeking!
Question:
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
Expert Answer:
Answer rating: 100% (QA)
Here are the beautified versions of the given objectives Even Digit Up Odd Digit Down Implement the ... View the full answer
Related Book For
Data Modeling and Database Design
ISBN: 978-1285085258
2nd edition
Authors: Narayan S. Umanath, Richard W. Scammel
Posted Date:
Students also viewed these programming questions
-
SALES ($1,000s) Month 2001 2002 2003 2004 2005 2006 2007 2008 2009 January 139.7 165.1 177.8 228.6 266.7 431.8 381 431.8 495.3 February 114.3 177.8 203.2 254 317.5 457.2 406.4 444.5 533.4 March 101.6...
-
Write a literature review for your study. See below for an example of a literature review. Your literature review should provide both analysis and synthesis of previous studies as related to the...
-
Let A, B be sets. Define: (a) the Cartesian product (A B) (b) the set of relations R between A and B (c) the identity relation A on the set A [3 marks] Suppose S, T are relations between A and B, and...
-
Review Questions: 1. What is the theory on which Rockwell hardness testing is based? 2. What is the purpose of the minor load in Rockwell hardness testing? 3. What are the advantages of the Rockwell...
-
Brand valuations are critical to CEOs, financial and marketing executives, security analysts, institutional investors, and others who depend on well-researched, reliable information needed for...
-
Who is the king of late night TV? An Internet survey estimates that, when given a choice between David Letterman and Jay Leno, 52% of the population prefers to watch Jay Leno. Suppose that you...
-
(Appendix) Compute ending inventory and cost of goods sold under a periodic inventory system. - Under a periodic inventory system, the inventory costing methods are applied as if all purchases during...
-
Zumbrunn Company's income statement contained the condensed information below. Zumbrunn's balance sheet contained the comparative data at December 31, shown below. Accounts payable pertain to...
-
1. How does estimating the present value of an investment lead to better financial decisions. What other functions have you used also help lead to better financial decisions? Your answer should be at...
-
Record the following transactions in General Ledger accounts of the General Fund of Fergieville. 1. Incurred salaries of $300,000, $280,000 of which was paid. 2. A long-term note ($400,000 face...
-
The table summarizes the movie-watching preferences and ages of a group of 500 people in one community. Movie Theater Streaming Service DVD Under age 18 0.13 0.16 0.01 Age 18-40 0.17 0.17 0.06 Over...
-
Convert 6 . 1 3 m / s 2 to a multiple of g .
-
Rooney's Doll Company produces handmade dolls. The standard amount of time spent on each doll is 1.50 hours. The standard cost of labor is $7.74 per hour. The company planned to make 8,800 dolls...
-
Regarding Qualitative and Quantitative research, document a proposed plan to accomplish a study on employing a U.S. essential Vaccine Passport procedure. What are the research techniques or approach?...
-
CFO wants to go to the bond market to issue debt instead of borrowing from a bank at lower interest rate. Why will the CFO go to the bond market?
-
Bandar Industries manufactures sporting equipment. One of the company's products is a football helmet that requires special plastic. During the quarter ending June 30, the company manufactured 3,900...
-
3 1 of 2 1 Required information [The following information applies to the questions displayed below.] On January 1, 2018, Splash City issues $500,000 of 9% bonds, due in 20 years, with interest...
-
Michelles trust is subject to 3.8% surtax on the lesser of the trusts net investment income or the excess of the trusts adjusted gross income over the $12,400 threshold (the highest trust tax rate)....
-
Use the instance diagram depicting the ternary relationship Orders shown on the next page to answer the following questions. a. Which customers order pens from the Galveston warehouse? b. Which items...
-
Display the number of pounds of milk produced in each region during the 2006-2010 period along with the ranking of each region in terms of the number of pounds of milk produced. The ranks should be...
-
You must have completed Exercise 9 before beginning this exercise, and thus have used the SQL Data Definition Language to create tables for the three relations DRIVER, TICKET_TYPE, and TICKET. Use...
-
What organizational enablers will best assist in creating a climate for change in a company?
-
Name some potential disruptive innovations in healthcare. Why might they be disruptive?
-
What other factors discussed in the chapter could Coye implement to enable greater creativity and innovation? UCLA Health, the healthcare system of the University of California at Los Angeles, had...
Study smarter with the SolutionInn App