Recursion Versus Iteration The Shalen Numbers - IT Computer Science Assignment Help

Assignment Task:

Task:

Objective To compare the efficiency of a recursive implementation of an algorithm and an iterative version.

The Shalen Numbers

The Shalen numbers are defined as follows: S(0) = 1, S(1) = 2, S(2) = 3, and S(n) = S(n − 1) + b(nX−2)/2c k=0 (−1)kS((n − 2) − 2k) , for n > 2. Remember that P-notation is like a for-loop that adds up terms. In this case, the P-notation sum is using a loop index named k that goes from 0 to b(n − 2)/2c (inclusive) when you are computing C(n); see the note below about the meaning of ba/bc.

Each term in the P-notation sum is a product of two parts:

• S((n − 2) − 2k) is one of the previous Shalen numbers (previous to S(n), that is).

• (−1)k is either 1 or -1 depending on whether the current value of k is even or odd, respectively. You will see this type of term used in sums when the terms of the sum are supposed to alternate between being added on and subtracted off; see the examples below! Note that ba/bc is the floor function — it returns the largest integer that is ≤ a/b, that is, it removes any fractional part keeping only the integer part. For example, b5/3c = b1 + (2/3)c = 1. When programming the formula, you can ignore the floor function if you are using integer types (int or long, for example) because if a and b are both integer types, then a/b uses integer division to compute a/b, which gives you the floor of a/b. Here are some values in the series: n 0 1 2 3 4 5 6 7 8 9 S(n) 1 2 3 5 7 10 15 22 32 4 For example, here is how you would compute

S(3): S(3) = S(3 − 1) + b(3 X−2)/2c k=0 ((−1)kS((3 − 2) − 2k)) = S(2) +X 0 k=0 ((−1)kS(1 − 2k)) (the Σ-notation sum contains one term only) = S(2) + ((−1)0 × S(1 − 2 × 0)) = S(2) + (1 × S(1)) = 3 + 2 (because S(1) = 2 and S(2) = 3) = 5. And here is how you would compute S(4): S(4) = S(4 − 1) + b(4 X−2)/2c k=0 ((−1)kS((4 − 2) − 2k)) = S(3) +X 1 k=0 ((−1)kS(2 − 2k)) (the Σ-notation sum contains two terms) = S(3) + ((−1)0 × S(2 − 2 × 0) + (−1)1 × S(2 − 2 × 1)) = S(3) + (1 × S(2) + (−1) × S(0)) = 5 + (3 − 1) (because S(0) = 1 and S(2) = 3 and S(3) = 5) = 7. And here is how you would compute S(5): S(5) = S(5 − 1) + b(5 X−2)/2c k=0 ((−1)kS((5 − 2) − 2k)) = S(4) +X 1 k=0 ((−1)kS(3 − 2k)) = S(4) + ((−1)0 × S(3 − 2 × 0) + (−1)1 × S(3 − 2 × 1)) = S(4) + (1 × S(3) + (−1) × S(1)) = 7 + (5 − 21) (because S(1) = 2 and S(3) = 5 and S(4) = 7) = 10.

Lab Exercise: Complete a program Take a copy of the file Lab1.java and rename it Lab1.java (e.g., Lab1CameronHelen.java). You must also rename the class Lab1 inside the file to match the new file name — that is, rename class Lab1 to be Lab1 (e.g., Lab1CameronHelen). The file contains a nearly-complete program, except it needs TWO method bodies added (details below). Do not change any of the code that is already written in Lab1.java — just add the two required method bodies (replace the comments inside those two methods with your own method bodies). The two static methods you will write the bodies of: 2 recursiveShalen: This method is passed an int n and recursively computes and returns the n th Shalen number, S(n), for n ≥ 0. It must compute Shalen numbers using the formula exactly as written above. If n > 2, it must use a loop to compute the sum in Σ-notation. Hint 1: The recursive part of a recursive method needs to make a number of recursive calls — every time it needs the value of S(anything) when it is computing S(n), it must make a recursive call to get the value of S(anything). (Note that “anything” is any value less than n.) Hint 2: Like the recursive Fibonacci method, this recursive method is not efficient! So don’t be surprised if it takes a long time to compute S(n) for larger n. nonrecursiveShalen: This method is passed an int n and iteratively computes the n th Shalen number, S(n), for n ≥ 0. (No recursion in this method — just loops.) It must compute Shalen numbers using the formula exactly as written above. When n > 2, to compute the n th Shalen number, S(n), this non-recursive method uses: • Two loops (nested), instead of recursion, and • An array to store Shalen numbers as you compute them — the i-th position of the array will store S(i), for i = 0, . . . , n. The idea if n > 2: First, put S(0) and S(1) and S(2) into the first three positions of the array. Then use a loop to compute S(i) and put it into position i of the array, for i going from 3 to n. When your code is computing S(i) — it will need an inner nested loop to do this computation —, it can easily get any of the values of S(0), S(1), . . ., S(i − 1) that are needed to compute S(i) because they are already computed and stored in the array. Finally, return S(n) after the outermost loop is done

The above IT Assignment has been solved by our  IT Assignment  Experts at My Uni Paper. Our Assignment Writing Experts are efficient to provide a fresh solution to this question. We are serving more than 10000+ Students in Australia, UK & US by helping them to score HD in their academics. Our experts are well trained to follow all marking rubrics & referencing style.

Be it a used or new solution, the quality of the work submitted by our assignment experts remains unhampered. You may continue to expect the same or even better quality with the used and new assignment solution files respectively. There’s one thing to be noticed that you could choose one between the two and acquire considered worthy of the highest distinction.