22C:30, 22C:115 Homework 3
Due date: Friday, 11/22
Problem 1
You are given positive integers m and n and the general problem is to
produce as output a knight's tour on the m X n chessboard or output
the fact that such a tour does not exist.

Define a class called location which has two integer data members to keep
track of the location of the knight on the chessboard.
Define an implement appropriate data members.
What to turn in? Printouts of the class header file and
the class implementation file.

Assume that the rows of the m X n chessboard are labeled 0 through m1 from
top to bottom and from 0 through n1 from left to right.
For any location (i, j), 0 <= i <= m1 and 0 <= j <= n1, define a
neighbor of (i, j) as any location that a knight positioned in
location (i, j) can move to in one hop.
Write a function numberOfNeighbors that takes a location (i, j),
0 <= i <= m1 and 0 <= j <= n1 and returns the number of its neighbors.
What to turn in? Printout of the function numberOfNeighbors.

Write a function getNeighbor that takes a location (i, j),
a positive integer t and returns the t th neighbor of location (i, j).
Assume that the neighbors of (i, j) are ordered in counterclockwise order
and are number 1, 2, 3,... in that order.
You can also assume that t is no greater than the number of neighbors of
(i, j).
What to turn in? Printout of the function getNeighbor.

Write a function called knightsTour that takes positive integers m and n and returns a vector
of locations that represents a knight's tour on the m X n chessboard.
If a knight's tour exists, then the vector should have length mn.
It does not matter where the tour starts, so just assume that the tour always
starts at location (1, 1).
If no knight's tour exists, then the vector that is returned should have length 0.
This function should implement a ``dfslike'' backtracking procedure discussed in class.
What to turn in?Printout of the function knightsTour.
In addition, turn in answers to the following questions:
 Does a 10 X 10 chessboard have a knight's tour? If so attach a printout of
a knight's tour in a 10 X 10 chessboard obtained by calling your
knightsTour function and printing out the output.
 Roughly speaking, given one hour, what is the largest value of n for
which your function can produce a knight's tour in an n X n chessboard
in that time?

Think about ways in which you can speed up your function. Write down a couple of ways (in 12 sentences)
each. You do not have to implement any of these ideas.
There is plenty of information on the knight's tour problem on the web; much
of it will not be useful to you.
However, if you do use web based sources for any of your answer please
acknowledge these.
Problem 2
Analyse the running times of the following code fragments and express
your answer in the "BigOh" 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.

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(int i = 0; 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.