Etude on theme of Dijkstra

ABSTRACT

We present a tutorial for undergraduate students who are interested in different programming contests like National Programming Olympiads or regional ACM International Collegiate Programming Contests (ACM ICPC). It is based on a problem discussed by E. W. Dijkstra in a public lecture in 1994. The tutorial was a part of a special undergraduate course presented for students of Novosibirsk State University in 2003-04 academic year during their preparation for ACM ICPC Final at Prague (2004).

The original problem is how to couple <i>N</i> black and <i>N</i> white points on the plane by intervals without intersections. E. W. Dijkstra suggested a nice heuristic search algorithm and proved its termination and correctness by the method of R. W. Floyd. Unfortunately, the upper bound of his algorithm was exponential. Due to this reason, he suggested to audience investigation of the problem complexity and development of an efficient algorithm.

We demonstrate that the problem is decidable in cubic time by quadratic reduction to the classical assignment problem. We also discuss how to solve the coupling problem in pure geometric/topological way. We also present some examples of utility of the coupling problem.

REFERENCES

• 1: Krzysztof R. Apt , Ernst-Rüdiger Olderog, Verification of sequential and concurrent programs (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 2: {Kuhn55} H. Kuhn The Hungarian method for the assignment problem. Naval Res. Logist. Q., vol. 2, 1955, p. 83--97.
• 3: Mikhail J. Atallah , Susan Fox , Suzanne Lassandro, Algorithms and Theory of Computation Handbook, CRC Press, Inc., Boca Raton, FL, 1998