TASK 'CHALLENGE' RATING (offered to assist you with project management strategies)
	Routine	Typically some deep thinking required, but not necessarily a lot of coding.
	Hard	Likely involves either a multiplicity of (possibly new) concepts or algorithms. Allow time.
	Buckle Up	Start immediately, think hard, employ a stepwise refinement strategy and post concerns as required.

The Golden Ratio, φ. In class we investigated the relationship between the sequence defined by the quotients of successive terms of the Fibonacci sequence and the Golden Ratio, φ. This can be expressed as,

(GR-1)

A compelling topic in pure mathematics is Continued Fractions. The essential idea is that the deeper the evaluation of these expressions, the better the approximation is to the ultimate irrational target, or what we prefer to call it in Calculus, the limit. The programmatic evaluation of these expressions is a good fit with your understanding of recursive methods. Here is one example of the continued fraction for the Golden Ratio.

(GR-2)

The limit of both of these sequences is φ.

Task. Develop a java project called GoldenRatio, the output of which will allow the viewer to confirm that both sequences (1) and (2) converge on φ. You will maximize your use of recursive methods, but beyond that, the design of the classes and methods are yours to decide based on our efforts last year. Beyond the correct answer, my evaluation of your submission will focus on the elements of good programming: class and method design, efficient implementation, strong documentation and highly intuitive output. Finally, keep in mind the following,

1. Both strategies incorporate recursion to determine their n'th approximations to the Golden Ratio.
2. The n'th approximation of each strategy are identical (i.e. grFib(1) and grCF(1) are 1, grFib(2) and grCF(2) are 2, and so on...)
3. Recursive methods are elegantly (and deceptively) simple.

Fibonacci Sequence.

1. The first two terms of the fibonacci sequence are defined as t₁=t₂=1. All remaining terms are defined as the sum of the previous 2 terms.

2. Develop the Java method public int fib (int n) that iteratively determines and returns the nth term of the fibonacci sequence. What is the Big-O of this implementation?
3. Write a piecewise definition of the nth term of the fibonacci sequence, t_n, in a recursive style similar (1) below. Develop the Java method public int fib (int n) that exercises this definition. What is the Big-O of this implementation?
4. Is there a way to determine t_n in O(1) without using a lookup table?

Powers. It is virtually impossible to provide practical programming solutions to a variety of complex problems without recursion. As such, it is an indispensable programming strategy. Having said this, you'll have to decide when it's warranted. Successful implementation of a recursive solution depends on your ability to define a recursive solution on paper. For example, the power function, xⁿ can be defined iteratively (non-recursively) as,

Defined recursively, we could write,

(P-1)

From (1), the implementation is straightforward. Successful recursive solutions arise from the programmer being able to express a definition similar to (1) for each new problem, that includes both the general recursive substitution expression and a basis or stopping condition.

Tasks.

1. Create the project, Powers. Implement the methods described below and supply statements in the main method to test them. Include your suggestion for the Big-O of each algorithm in the comment preceding each method.
2. Develop the Java method public int powerIterative(int x, int n) that determines and returns the value of xⁿ, iteratively. What is the Big-O of this implementation?
3. Develop a second version of public int powerRecursive(int x, int n) that determines and returns the value of xⁿ, recursively. What is the Big-O of this implementation?
4. Develop a third version of public int pow2(int n) that computes the value of 2ⁿ with a running time of O(1).
5. Improved Power Algorithm. Can the Big-O of the iterative and recursive power algorithms above be improved? Identify a pattern from the following examples,

   

   1. Explain this algorithm.
   2. What is the Big-O of this algorithm?
   3. Write down the piecewise definition of the algorithm
   4. Code the algorithm into the method public int powerImproved(int x, int n)

Perfect Powers.

1. Develop an inductive expression for perfect cubes, C_n+1, in a manner similar to our in-class development of the formulas for the perfect triangles, T_n+1 and the perfect squares, S_n+1 .
2. Looking at the three inductive formulas you have engineered, again, identify the role play by Pascal's Triangle.
3. Use this observation to propose and confirm (by example) inductive formulas for perfect fourths and fifths.
4. Rewrite your inductive expression for the perfect cubes, C_n+1 in Step 1 as a piecewise recursive function suitable for coding.

Number of Paths. Consider Problem 15 of Project Euler.

1. Determine what connection the problem has to Pascal's Triangle.
2. Use the conection determined above to solve the problem with pencil and paper.
3. Submit your neatly prepared solution to me at the start of class on Monday, Period 1.