Lab 6: Recursive Backtracking; A first look at Big-O notation and Sorting analysis

Task 1: Review Recursive Backtracking (optional)

In the current problem set you are asked to implement a recursive backtracking solution on Problem #8: Sudoku. Although the problems are different, you may find it helpful to have a good understanding of the recursive backtracking solution implemented to solve the N-Queens problem which was covered in lecture.

We can use the same technique for determining how to color states on a map.

What are the common characteristics of these two problems?

Understanding how recursive backtracking works in these two scenarios will help you implement a recursive backtracking solution for the next problem set.

Task 2: Practice algorithm analysis

Consider the following code fragment:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < 2*n; j++) {
        methodA();

        for (int k = 0; k < n + 1; k++) {
            methodB();
        }
    }

    for (int j = 0; j < i; j++) {
        methodC();
    }

    if (i % 2 == 0) {
        methodD();
    }
}

For each of the following, find the function that expresses the number of times each part of the code is executed for a given value of n, and then determine the corresponding big-O expression.

1. the number of times methodA() is called
2. the number of times methodB() is called
3. the number of times methodC() is called
4. the number of times methodD() is called

Task 3: Review and Analyze Bubblesort

In lecture, you have begun to learn about some of the many algorithms that are available for sorting arrays of values.

Now let’s take a closer look at Bubble sort. Recall that on each pass, the algorithm proceeds from left to right, swapping adjacent elements if they are out of order. As a result, larger elements “bubble up” to the end of the array.

For example, consider the following array:

First pass Bubble sort compares elements 0 and 1 (the 28 and 24), and because they are out of order, it swaps them:

It then compares elements 1 and 2 (the 28 in its new position and 27), and because they are out of order, it swaps them:

Finally, it compares elements 2 and 3 (the 28 in its new position and 18), and because they are out of order, it swaps them:

Note that the largest element (the 28) has bubbled up to its final position, so we don’t need to consider it on the next pass.

Second pass Bubble sort compares the elements 0 and 1 (the 24 and 27), and because they are in order, it leaves them alone:

It then compares elements 1 and 2 (the 27 and 18), and because they are out of order, it swaps them:

And the second pass ends there.

Note that the second largest element (the 27) has bubbled up to its final position, so we don’t need to consider it on the next pass.

Third pass Bubble sort compares elements 0 and 1 (the 24 and 18), and because they are out of order, it swaps them:

And the third pass ends there.

Note that the third largest element (the 27) has bubbled up to its final position, so we don’t need to consider it on the next pass.

And because there is only one remaining element that hasn’t been bubbled up, the algorithm ends, and the array is sorted.

1. Trace bubble sort on the following array:

   7

   39

   20

   11

   16

   5

   Show what the array looks like after each swap that occurs.

2. Here is the implementation of bubble sort from our Sort class:

   public static void bubbleSort(int[] arr) {
       for (int i = arr.length - 1; i > 0; i--) {
           for (int j = 0; j < i; j++) {
               if (arr[j] > arr[j+1]) {   // how many comparisons?
                   swap(arr, j, j+1);
               }
           }
       }
   }
   

   Note that:

   • The inner loop performs a single pass.

   • The outer loop governs the number of passes, and the ending point of each pass.

   Determine a formula for the number of comparisons of array elements that bubble sort performs when operating on an array of length n.

   To do so, it can help to begin by filling in a table like this one:

   pass #       # of comparisons
   ------       ----------------
      1              n - 1
   

   1. Fill in the next few rows of this table, and see if you notice a pattern.

   2. How can we take the pattern revealed by the table and use it to derive an exact formula for the number of comparisons?

   3. Given that formula, what is the big-O expression for the number of comparisons performed by bubble sort?

   4. The number of moves performed by bubble sort depends on the contents of the array. How many are performed as a function of n:

      • in the best case?
      • in the worst case?
      • in the average case?

   5. What is the big-O expression for the overall running time of bubble sort?

   6. What changes to the algorithm would be required to optimize it such that the algorithm can run O(n) in the best case?

Task 4: Practice with sorting

In this task, we will practice some of the algorithms from our Sort class.

Consider the following array:

1. Trace insertion sort on the above array.
   Show what the array looks like after each iteration of the outer loop of the algorithm (i.e., after each element is considered for insertion and either left alone or inserted).