22C:30, 22C:115 Homework 3 Solution

Problem 1

The class location is defined here: location.h and location.cxx.

Here is the function numberOfNeighbors. By itself the function may not make sense, because it uses a function called withinBound and a vector called offset. But, below you will see the entire program for the knight's tour problem.

Here is the function getNeighbor. Again, by itself this function may not make sense, so you should read it in the context of the entire knight's tour program.

Here is the entire program knightsTour.cxx.

The answers to the other questions are as follows:

I believe the 10 x 10 chessboard has a knight's tour, but my program is not fast enough to produce such a tour in a reasonable amount of time.
I could process a 7 x 7 chessboard in an hour. This was on an PC with an Intel PIII processor at 1GHz clock speed. The PC was running Red Hat Linux 6.2.
Two ways of improving the running time of the function are:
- The function getNeighbor starts with the neighbor 2 columns to the right and 1 row below and then goes around the neighbors in a counterclockwise order to get to the neighbor numbered t. It would be more efficient to replace this by a function called getNextNeighbor that takes a location x, the current neighbor c, and returns the next neighbor of x in counterclockwise order. However, this change will almost surely make only a small improvement in the running time of the function.
- A much better way of improving the running time of the function is to use some way of "pruning" the search. For example, it is possible to check if the set of unvisited squares in the chessboard are connected, that is, a knight can reach from any unvisited square to any other unvisited square. So a way of pruning the search would be to test if the set of unvisited squares is connected and backtracking if that is not the case.

Problem 2 Analyse the running times of the following code fragments and express your answer in the "Big-Oh" notation. Show all the work that went into getting your answers.

```
      for(int i = 0; i < n; i++)
          for(int j = 0; j < min(i, 10); j++)
             cout << i*j << endl;
```
In the above code the function call min(i, 10) returns the smaller of i and 10.
For each value of i, i = 1, 2, ..., 9, 10, the inner loop iterates i times. For each values of i > 10, the inner loop iterates 10 times. Thus the total number of times the cout statement is executed is:
```
1 + 2 + ... + 9 + 10 + 10 + 10 +... + 10 <= 10 + 10 + 10 +... + 10 = 10(n-1) = O(n)
```
The same code as above except that min(i, 10) is replaced by max(i, 10), which returns the larger of i and 10.
For each value of i, i = 0, 1, 2, ..., 9, 10, the inner loop iterates 10 times. For each values of i > 10, the inner loop iterates i times. Thus the total number of times the cout statement is executed is:
```
10 + 10 + 10 +... + 10 + 11 + 12 + ... + (n-1) = 10n + (1 + 2 +... + n-11) 
					       < 10n + (1 + 2 + ... n)
					       = 10n + n(n+1)/2 = O(n^2)
```
```
      for(int i = 1; i < n; i++)
          for(int j = 0; j < n; j = j + i)
             cout << i*j << endl;
```
The sum 1 + 1/2 + 1/3 + ... + 1/n is called the harmonic series and it is well known that this is O(log n). Use this fact in your analysis.

For each value of i, the inner loop iterates at most (n-1)/i times. Therefore the total number of times the cout statement is executed is:

(n-1) + (n-1)/2 + .... + (n-1)/(n-1) = (n-1) (1 + 1/2 + 1/3 +...+1/(n-1)) = O(n log n).