Lesson 3 Summary

Please refer to the Resource box on the right to download the RecursionApp.java, DP.ppt, GreedyAlgo.ppt and lastly Complexity Analysis.ppt.

[ Recursion ]

Understand what is Recursion by looking at the RecursionApp.java.

Rule 1: Have a base case that can be solved without using recursion (Terminating condition must exist)
Rule 2: Make sure that the recursion work towards the base case (Move towards terminating condition)
Rule 3: Assumes that the recursion call works (Inductive hypothesis)
Rule 4: Do not duplicate effort/work by solving same instance of problem in another recursive function call

In lesson 2, we illustrate a normal binary search algorithm on slide 24(lesson 2).
In lesson 3, we illustrate a recursive binary search algorithm on slide 19(lesson 3).

*** Recursion is not necessarily efficient
*** Recursion will not necessarily produce shorter codes


[ Fibonacci ]

Fibonacci sequence is a classic example of recursion.

Fib(0) = 0 [base case]
Fib(1) = 1 [base case]
For all integers n > 1: Fib(n) = (Fib(n-1) + Fib(n-2)) [recursive definition]

Please visit wikipedia: http://en.wikipedia.org/wiki/Fibonacci_number for better elucidation.


[ Divide and Conquer ]

Divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same (or related) type, until these become simple enough to be solved directly.

Use Fibonacci to explain divide and conquer.

public static long fibonacci( int n ){
if( n <= 1 )
return n;
else
return fibonacci( n-1 ) + fibonacci( n-2 );
}

The above code snipplet illustrates the use of disjoint recursive calls to divide and conquer a number problem.


[ Solution to Week 2 homework :: Maximum Contiguous Subsequence Sum Problem ]

- For the Recursive solution to the Maximum Contiguous Subsequence Sum Problem, refer to page 280 of the textbook. See page 278 and 279 for background description.

- For the Cubic complexity solution to the Maximum Contiguous Subsequence Sum Problem, refer to page 171 of the textbook.

- For the Quadratic complexity solution to the Maximum Contiguous Subsequence Sum Problem, refer to page 174 of the textbook.

- For the Linear complexity solution to the Maximum Contiguous Subsequence Sum Problem, refer to page 176 of the textbook.

*** Remember that the simpler the complexity, the shorter the number of iterations and the more efficient the algorithm


[ Dynamic Programming ]

Will elaborate more in the next lesson. Meanwhile, please take a look at DP.ppt.


[ Greedy Algorithm ]

Will elaborate more in the next lesson. Meanwhile, please take a look at GreedyAlgo.ppt.


[ Complexity Analysis ]

Please look at Complexity Analysis.ppt to appreciate the following
- Definition of Algorithm
- Example (Linear Search, Binary Search)
- Complexity (Time Complexity)
- Big-Oh Notation
- Complexity Analysis


[ Measure time taken to process your Algorithm ]

To take a closer look at how to measure your algorithm processing time, please visit
http://nadeausoftware.com/articles/2008/03/java_tip_how_get_cpu_and_user_time_benchmarking#Timingataskusingwallclocktime