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

Task 1: Recursive Backtracking

In lecture we saw how we could use the technique of recursive backtracking to solve the N-Queens problem. 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