OPINION
Row/Column Transformations
“sneak” from a zone on one side of the
cat’s attempt to a zone on the other side.
While these algorithms may seem
intuitively relevant at first glance, they
are not based on suitable underlying
characteristics. The challenge is to
recognize a suitable characteristic on
which to capitalize. In careful examination,
we may attempt a potentially relevant
characteristic: in every step, the mouse
changes the parity of its section.
A sequence of cat attempts in
consecutive sections, starting from
section1 (and advancing from left to right),
guaranties that the mouse will be caught
if the mouse is initially in an odd section.
This is due to the observation that at any
given time, the cat attempts a section
whose parity equals the parity of the
mouse section. A “sweep” from left to right
will not let the mouse escape from a zone
ahead of the cat to a zone behind the cat;
as the distance between the cat and the
mouse before every new attempt by the
cat is even (0, or 2, or 4, …).
However, the mouse may manage to
escape if its initial section-parity is even
(and the cat starts from section1). Does
this mean that the cat may catch the
mouse only in half of the initial cases? Not
quite. If the cat does not catch the mouse
in its left-to-right “sweep,” then upon
reaching sectionN, the cat may “
synchronize” the parity of its attempted section
with that of the mouse by attempting
sectionN again (i.e., attempting sectionN
twice in a row). Then, the cat may perform
a “sweep” from right to left, and this time
it will catch the mouse.
All in all, the cat may always catch
the mouse, in at most two “sweeps.”
The key point was to “go for” a parity
characteristic of the distance between the
cat’s attempted section and the mouse
section. When an even distance exists, it is
kept throughout a “sweep.” The underlying
theme here, of capitalization on parity
(with respect to distances), appears in a
variety of occasions in computer science—
e.g., the notion of even distances between
nodes in a bipartite graph, or the notion of
odd-length cycles found by Breadth-first
search in an undirected graph. Although
this theme is simple and common, our
experience with students shows that many
are not aware of its relevance. An example
like the one here may enhance students’
awareness of this theme.
David Ginat
Tel-Aviv University
Tel-Aviv, Israel
ginat@post.tau.ac.il
DOI: 10.1145/3024914 Copyright held by author.
The underlying theme here, of
capitalization on parity (with respect to
distances), appears in a variety of
occasions in computer science—e.g., the
notion of even distances between nodes
in a bipartite graph, or the notion of
odd-length cycles found by Breadth-first
search in an undirected graph.
ACM Conference
Proceedings
Now Available via
Print-on-Demand!
Did you know that you can
now order many popular
ACM conference proceedings
via print-on-demand?
Institutions, libraries and
individuals can choose
from more than 100 titles
on a continually updated
list through Amazon, Barnes
& Noble, Baker & Taylor,
Ingram and NACSCORP:
CHI, KDD, Multimedia,
SIGIR, SIGCOMM, SIGCSE,
SIGMOD/PODS,
and many more.
For available titles and
ordering info, visit:
librarians.acm.org/pod
ACM Conference
Proceedings
Now Available via
Print-on-Demand!