goal of any
solution is to minimize swaps.
Solution to challenge. Numbering
the rows from top to bottom and left to
right, we can build roads between red
towns from ( 1, 1) to ( 2, 2), ( 2, 4) to ( 3, 3),
( 2, 2) to ( 3, 3), and ( 3, 1) to ( 2, 2). This
leaves the red towns at ( 1, 3), ( 4, 2), and
( 4, 4) surrounded by blue towns, high-
lighted in bold, in the following grid
Now build roads between the blue
towns from ( 1, 2) to ( 2, 1), from ( 2, 1) to
( 3, 2), from ( 2, 3) to ( 3, 2), and from ( 2, 3)
to ( 3, 4). This leaves certain towns iso-
lated from their own colors, like those
highlighted in bold in this grid
The two sides then need just three
swaps: red and blue on top and the pairs
on the bottom.
Upstart 1. Suppose you are given an
arbitrary planar graph of connections
and an arbitrary red/blue coloring of
nodes. You are also given a budget of r
planar edges you can add. Can you create an algorithm (and implementation)
that will perform a minimum number
of swaps to achieve partitioned peace?
If so, please explain it in pseudo-code
and send links to platform-indepen-dent software.
Upstart 2. Now consider the same
question as in Upstart, 1 but allow non-planar edges.
All are invited to submit their solutions to
email@example.com; solutions and discussion
will be posted at http://cs.nyu.edu/cs/faculty/shasha/
Dennis Shasha ( firstname.lastname@example.org) is a professor
of computer science in the Computer Science Department
of the Courant Institute at New York University, New York,
as well as the chronicler of his good friend the omniheurist
Copyright held by the author.
[CONTINUED FROM P. 112]
FOR LIFELONG LEARNING
Online Courses from Skillsoft
Online Books from Safari, Books24x7,
Morgan Kaufmann and Syngress
Webinars on today’s
hottest topics in computing