Recursive Binary Search

• Recall binary Search
  • Need ordered array
  • recFind(someKey, 0, numItems-1);
    Look at middle element: (bigi + smalli)/2
    Found? Return index
    Look in top half or bottom half
  • Not found? Return a sentinel value (null)
• Author's binary search code
• Does it stop?
  • item is found, stop recursing & return element
    Otherwise split list & continue looking
  • Case two remaining elems:
    LB=x-1, UB=x, CI =(LB + UB)/2 = (2x-1)/2 = floor(x - 1/2) = LB
    If not found, key must be larger: recFind (key, x, x)
  • Case one remaining elem:
    LB=x, UB=x, CI = 2x/2 = x
  • If not found,
    Recfind (key, x+1, x) or recFind (key, x, x-1)
    In either case, LB >> UB,thus stop looking & return impossible value
• This is an example of a Divide and Conquer Algorithms

Towers of Hanoi Revisted

• Hanoi
• Author's towers Java code
• Analysis

    if (numDisks == 1)
       System.out.println("Move from "+from+" to"+to);
    else 
        solveTowers(int numDisks -1, from, to, temp) // O(Tn-l}
        System.out.println("Move from "+from+" to"+to) // O(1)
        solveTowers(int numDisks -1, temp, from, to);  // O(Tn-l}
  

• Sample Run
• T_n = 2T_n-1 + 1
• Recall:
  T₁ = 1 --> 2¹ - 1
  T₂ = 3 --> 2² - 1
  T₃ = 7 --> 2³ - 1
  T₄ = 15 --> 2⁴ - 1
  Thus for small n, --> 2ⁿ - 1
• For any n T_n
  = 2(2^n-1 - 1) + 1
  = 2(2^n-1) - 1
  = 2ⁿ - 1
  Top

• Merging two SORTED arrays
  • Assume you have an (sub)array with two parts that are already sorted
  • You know the index of
    1st element of lower sorted sequence (lowPtr)
    1st element of upper sorted sequence (highPtr)
    Last element of upper sequence (UB)
  • Sort the elements by merging the sequences
  
• Author's merge code
• Recursive sorting using merging -- merge sort
• 
• Use a "work space" array
• While there are elements left in both sequences
  

     If (A[lowPtr] < A[highPtr])
      WS[j++] = A[lowPtr++]
     Else
      WS[j++] = A[highPtr++]
  

• 
  
• Typically, one sequence or the other will have elements remaining, so
• Copy the remaining elements to WS
  
• 
  Copy all elements from WS back into A
• Algorithm for Merge Sort
  1. Assume a workspace that can be used by all
     Size equal to A
  2. Split array in half
     1. Apply Recursive Merge Sort to lower half
     2. Apply Recursive Merge Sort to upper half
     3. Then, merge upper & lower halfs
  3. Base case
     Only one element in subarray => do nothing
• Author's merge sort code
• Need to know the upper bound of the lower sequence
  To determine if we are done comparing
  To copy remaining elements from A to WS
  This is the initial highPtr - 1
     mid = highPtr - 1
• Merge Sort Efficiency
  O(N) comparisons
  O(2N) copies
• Split array in half for each step
  O(N) done O(logN) times so, O(N logN)
  Space required (not an in place sort) is 2N
• O(N²) vs O(N log₂N)

  N	N2	N log2N
  2	4 = 2*2	2 = 2*2
  4	16 = 4*4	8 = 4*2
  1024	1M	1K
  106	1012	2 * 107
  ~ 220	~ 240	~ 20 * 220

Eliminating recursion by using stacks

• Recursive Backtracking
• Uses the system stack
• Author's triangle code
• Author's stack triangle code
• Simplify the code
  Eliminate switch statement
  Make the code more efficient
• Author's stack triangle code

The Knapsack Problem

• Fit items of different weights into knapsack
• Knapsack weight has to total some specified weight
• Not all items have to be placed into the knapsack
• Algorithm
  1. If sum = target then done
  2. Select first item. New weight is target - first item
  3. Try each combination of remaining weights
     Stop the combination if sum > target
     (Recall the all possible combinabtions of letters)
  4. If none of combinations work, discard first item and restart process with second
  5. Continue on with 3rd, 4th, ... until all combinations are exhausted
• Given target total weight of 20
  and individual weights of 11, 8, 7, 6, and 5

  11	//Target = 20, 11 is too small
  11, 8	//Target = 9, 8 is too small
  11, 8, 7	//Target = 1, 7 is too big
  11, 8, 6	//Target = 1, 6 is too big
  11, 8, 5	//Target = 1, 5 is too big //No more items
  11, 7	//Target = 9, 7 is too small
  11, 7, 6	//Target = 2, 6 is too big
  11, 7, 5	//Target = 2, 5 is too big //No more items
  11, 6	//Target = 9, 6 is too small
  11, 6, 5	//Target = 3, 5 is too big //No more items
  11, 5	//Target = 9, 5 is too small //No more items
  8	//Target = 20, 8 is too small
  8, 7	//Target = 12, 7 is too small
  8, 7, 6	//Target = 5, 6 is too big
  8, 7, 5	//Target = 5, 5 is just right!