Problem Class Questions 2006
for COMP1008 (Object-Oriented Programming)

Week 8 (Starting 13th March)

1. Review the recursive methods below (as seen in the lectures) and make sure you understand how they work. Then determine how to rewrite each method using loops rather than recursion, removing all the recursive method calls.

a) Binary Search

int binarySearch(int[] a, int low, int high, int value) {
  if (low > high) {
    return -1;
  }
  else {
    int middle = (low + high) / 2;
    if (value == a[middle]) { 
      return middle; 
    }
    else {
      if (value < a[middle]) {
        return binarySearch(a, low, middle - 1, value); 
      }
      else {
        return binarySearch(a, middle + 1, high, value); 
      }
    }
  }     
} 

b) Quick Sort

void quicksort(double[] a, 
               int left, 
               int right) { 
   if (right <= left) return; 
   int i = partition(a, left, right); 
   quicksort(a, left, i-1); 
   quicksort(a, i+1, right); 
} 

int partition(double[] a, 
              int left, int right) { 
   int i = left - 1; 
   int j = right; 
   while(true) { 
      while (less(a[++i], a[right])) ; 
      while (less(a[right], a[--j])) 
         if (j == left) break; 
      if (i >= j) break; 
      swap(a, i, j); 
   } 
   swap(a, i, right); 
   return i; 
} 

2. The Eight Queens puzzle requires 8 queens to be placed on a chess board, such that no queen can be taken by any other queen. One solution is:

Develop a recursive algorithm that will find all the solutions to this problem.

3. You are probably familiar with a sliding block puzzle like the one illustrated below, where you have to slide the numbered blocks into order:

Determine a data structure to represent a sliding block puzzle and a recursive algorithm that will find the sequence of moves needed to slide the blocks into order from any starting position.