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

Task 1: Review Recursive Backtracking

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