CS15-750  Midterm Exam 1              FEBRUARY 2003
                                                 Manuel Blum

Your name:______________________, __________________________
                FAMILY (LAST)       GIVEN (FIRST)

Your signature:_____________________________________________

Your email address:_________________________________________

* This is a closed book examination: No books, no laptops, no
  calculators, no scratch paper, are permitted.
* Do all your work including scratch work on the pages of this
  exam.
* Full credit is 102 pts.

Define a Tournament Graph G = <V,E> on |V| = n vertices and
|E| = (n choose 2) edges to be a directed graph with no self-loops
and exactly one (directed) edge joining every pair of distinct vertices.

(1 pt)
1. An nxn matrix /a  \ of 0's, 1's, and -1's is the adjacency
                 \ ij/
matrix for a Tournament Graph iff:

(1 pt)
2. Define a (Directed) Hamilton Path (HP) in a directed graph to be
a directed path v   -> v   -> ... -> v   that visits
                 i1     i2            in
every vertex exactly once.

Exhibit a Hamilton Path in the following Tournament Graph:

            1  2  3  4  5  6

       1    0  1  1  1  1  1

       2   -1  0 -1  1 -1  1

       3   -1  1  0 -1 -1  1

       4   -1 -1  1  0 -1  1

       5   -1  1  1  1  0 -1

       6   -1 -1 -1 -1  1  0

20 pts)
3. Prove that every Tournament Graph (TG) has a Hamilton Path (HP).

(5 pts)
4. Give an efficient (polynomial time) algorithm to find a Hamilton Path.
(If your proof above includes such an algorithm, you do not have to repeat
that algorithm here.)

(20 pts)
5. Give an algorithm (for HP in TG) that makes as few probes as you
can manage into the adjacency matrix.
* COUNT each probe into the adjacency matrix as ONE STEP.
* Do NOT charge for matrix entries that are not probed.
* Do NOT charge for any other data structure manipulations.

(10 pts)
6. Explain/prove why your algorithm is correct.

(10 pts)
7. Analyze the running time of your algorithm as measured
by the number of probes that it makes.

(10 pts)
8. Prove that your algorithm is optimal, ie. up to a
multiplicative constant no algorithm makes fewer probes.

---------------------------------------------------------------
The following problem 9 may be worked over the weekend and turned
in to class this Monday March 3 at 10:30am BEFORE class starts.
You may NOT collaborate with anyone or anything on the solution to this
problem.

There is no need to cut on the above line:
A copy of problem 9 below will be given to you together with solutions
to problems 1-8 as you leave this exam.

(25 pts)
9. Give a data structure that enables you to achieve the above
running time when all steps (not just probes) are counted.
Specify clearly the data structure and what counts as a step.