We prove that the robber can evade (that is, stay at least unit distance from)
at least lfloor n/5.889 rfloor cops in an n by n continuous square region,
that a robber can always evade a single cop in a square with side length 4.5,
and that a single cop can always capture the robber in a square with side
length smaller than 2.189... . We also make many new observations and
conjectures about both the continuous problem and the discrete problem in
which a robber tries to evade k cops on an n by n grid.
Slides (PDF; 37 pages)
We give four elementary examples of recursion that are real-life, non-trivial, more natural than the corresponding iterative approach, and do not involve any sophisticated algorithms, data structures, or mathematical problems. The examples are two forms of writing numbers in words, coalescing page references for an index, and finding unclosed blocks.
Given a set of n elements, each of which is colored one of c colors, we must determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. We focus on the expected number of color comparisons when the c^n colorings are equally probable. We analyze an obvious algorithm, showing that its expected performance is (c^2 + c - 2)n/(2c) - O(c^2). We present and analyze an algorithm for the case c=3 colors whose average complexity on the 3^n equally probable inputs is 7083n/5425 + O(sqrt n) = 1.3056...n + O(sqrt n), substantially better than the expected complexity 5n/3 + O(1) = 1.6666...n + O(1) of the obvious algorithm. We describe a similar algorithm for c=4 colors whose average complexity on the 4^n equally probable inputs is 761311n/402850 + O(log n)= 1.8898...n + O(log n), substantially better than the expected complexity 9n/4 + O(1) = 2.25n + O(1) of the obvious algorithm.