5/14/2008
Sing, Prayer

ANNOUNCEMENTS
* Project 2?  Challenges?
* Updated Project Pages, Checkstyle Compliant

REVIEW
* Recursion pictures
* More Recursive Examples
	* Sum.java - another example, what is the base case?  Does the recursive step progressing towards the base case?
	* Fibonacci.java - compare iterative and recursive methods, show recursive slowdown
	* DrawRuler.java - base case?  progression?
	* RecursiveWordSearch.java - base case?  progression?


GROUP WORK
Which algorithm would work best on a sorted yet unevenly distributed dataset?
	A. sequential search
	B. binary search
	C. interpolation search
	
Which algorithm would work best on an unsorted dataset?
	A. sequential search
	B. binary search
	C. interpolation search
	
Which algorithm would work best on a sorted dataset, that is evenly distributed?
	A. sequential search
	B. binary search
	C. interpolation search

What are some approaches you might take for frequently searching an unsorted dataset?
What other searching algorithms are you aware of?

NEW STUFF
* Logarithm (Section 5.5, Page 181)
	* definition: For any B, N > 0, log_B N = K if B^K = N 
		The logarithm of N (to the base 2) is the value X such that 2 raised to the power of X equals N.  By default, the base of the logarithm is 2. 
	* a logarithm is the exponent that indicates the power to which a number (the base) is raised to produce a given number
	* Thm 5.4:  The base does not matter.  For any constant B>1, log_B N = O(log N)
	* bits in a binary number
		How many bits are required to represent N consecutive numbers?
	* Repeated Doubling Principle (Page 182):
		Starting from X=1, how many times should X be doubled before it is at least large as N?
	* Repeated Halfing Principle (Page 182)
		Starting from X=N, if N is repeatedly halved, how many iterations must be aplied to make N smaller than or equal to 1?
* Static Searching (Section 5.6, Page 183)
	Defined: Given an integer X and an array A, return the position of X in A or an indication that it is not present.  If X occurs more than once, return any occurence.  The Array A is never altered.
	* Sequential
		* steps through the data sequentially until a match is found
		* linear
		* unsorted
	* Binary Search
		* if the input array has been sorted, the Binary Search can be performed from middle of array rather than the end
		* logarithmic - search range is halved each iteration
		* optimizing the binary search can cut the number of comparisons roughly in half
	* Interpolation
		1. Each access must be very expensive compared to a typical instruction.
		2. The data must not only be sorted, it must also be fairly uniformly distributed.
		* interpolation search has a better Big-Oh bound on average than does binary search, but has limited practicality and a bad worst case.
	
	
GROUP WORK:  Big-O 
==================
		
		
[1]    for ( int i = 0; i < n; i++ )            O(N)
         sum++;

[2]    for ( int i = 0; i < n; i += 2 )         O(1/2 N) => O(N)    
         sum++;

[3]    for ( int i = 0; i < n; i++ )            O(N^2)
         for ( int j = 0; j < n; j++ )
            sum++;

[4]    for ( int i = 0; i < n; i++ )            O(2N) => O(N)
         sum++;
       for ( int j = 0; j < n; j++ )
         sum++;

[5]    for ( int i = 0; i < n; i++ )            O(N*N^2) => O(N^3)
         for ( int j = 0; j < n*n; j++ )
            sum++;

[6]    for ( int i = 0; i < n; i++ )            O(N * ((N-1)/2)) => O(N^2) 
         for ( int j = 0; j < i; j++ )
            sum++;

[7]    for ( int i = 0; i < n; i++ )            O(N * N^2 * ((N^2 - 1)/2)) => O(N^5)
       	 for ( int j = 0; j < n*n; j++ )
        	for ( int k = 0; k < j; k++ )
            	sum++;