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)
Question 1 public static long eduoddlong n if n 0 return 0 Base case return ... 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
-
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...
-
Wechsler Company produces three products: A130, B324, and C587. All three products use the same direct material, Brac. Unit data for the three products are: The demand for the products far exceeds...
-
Use symmetry to evaluate the following integrals. /4 [ sec x dx J-/4
-
Consider the following cash flow profile and assume MARR is 10 percent/year and the finance rate is 4 percent/year. a. Determine the MIRR for this project. b. Is this project economically attractive?...
-
Delph Company uses a job-order costing system and has two manufacturing departmentsMolding and Fabrication. The company provided the following estimates at the beginning of the year: During the year,...
-
Part E Constants A rigid, uniform, horizontal bar of mass m and length is supported by two identical massless strings. (Figure 1)Both strings are vertical. String A is attached at a distance d < L/2...
-
Frame the Mattco case using the factors set forth in this chapter. Specific areas that should be addressed in this exercise include: a. Type of case b. Jurisdiction c. Professional standards d....
-
4. A Veterinary Office needs a database to track the services provided. B C Type Breed Dog Std. Poodle Cat Cashmier ma Dog Std. Poodle Dog Collie Mix Cat Unknown Cat Unknown Dog Border Collie 1...
-
Analyze background, customer demand, core value of The Gioi di Dong via 2 following link https://amp.vtc.vn/the-gioi-di-dong-sa-thai-gan-6-000-nhan-vien-trong-3-thang-ar769724.html,...
-
When comparing alternative interventions according to their additional cost per quality-adjusted life years (QALY), which cost per QALY would be preferred? Those with a higher cost per QALY are...
-
A book that sounds just perfect for me, Kate Raworth's Doughnut Economics is available on Amazon for $57.57 for the hardback and $15.05 for paperback. From the publisher's perspective, the difference...
-
Why Do Gas Station Prices Constantly Change? Blame the Algorithm Retailers are using artificial-intelligence software to set optimal prices, testing textbook theories of competition; antitrust...
-
The cost of renting a van for one day includes a flat rental fee plus a charge for each mile the van is driven while it is rented. A van that is driven 107 miles costs $97.15. a can that is driven...
-
4.92 A gyro consists of a circular ring with mass m and radius R as well as light spokes and center bar. A thread of length b has been wound around the center bar. You pull it with a constant force...
-
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...
-
Which firms look best for someone wishing to buy stocks on margin?
-
Which firm looks best for someone planning to pay cash to buy 100 shares?
-
Examine all of the views available in the drop-down box menu (Snapshot, Performance, Portfolio, and Nuts and Bolts) to answer the following questions: a. Which fund has the best expense ratio? b....
Study smarter with the SolutionInn App