Inroads - March 2017

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.