By Anany Levitin
In the last few years algorithmic thinking has become somewhat of a buzzword among computer science educators, and with some justice: ubiquity of computers in today’s world does make algorithmic thinking a very important skill for almost any student. Although at the present time there are few colleges and universities that require non-computer science majors to take a course exposing them to important issues and methods of algorithmic problem solving, one should expect the number of such schools to grow significantly in the near future.
Algorithmic puzzles, i.e., puzzles that involve clearly defined procedures for solving problems, provide an ideal vehicle to introduce students to major ideas and methods of algorithmic problem solving:
- Algorithmic puzzles force students to think about algorithms on a more abstract level, divorced from programming and computer language minutiae. In fact, puzzles can be used to illustrate major strategies of the design and analysis of algorithms without any computer programming — an important point, especially for courses targeting non-CS majors.
- Solving puzzles helps in developing creativity and problem-solving skills — the qualities any student should strive to acquire.
- Puzzles are fun, and students are usually willing to put more effort into solving them than in doing routine exercises.
- Puzzles provide attractive topics for student research because many of them don’t require an extensive mathematical or computing background.
It’s important to stress that algorithmic puzzles is a serious topic. A few algorithmic puzzles such as Fibonacci’s Rabbits and Königsberg’s Bridges played an important role in history of mathematics. Such well-known and intriguing problems as the Traveling Salesman and the Knapsack Problem, which clearly have a puzzle flavor, lie at the heart of the so-called P ≠ NP conjecture, the most important open question in modern computer science and mathematics.
So reader, I would like to challenge you to an algorithmic puzzle, #136, “Catching a Spy”:
In a computer game, a spy is located on a one-dimensional line. At time 0, the spy is at location a. With each time interval, the spy moves b units to the right if b≥0 and |b| units to the left if b<0. a and b are fixed integers, but they are unknown to you. Your goal is to identify the spy’s location by asking at each time interval (starting at time 0) whether the spy is currently at some location of your choosing. For example, you can ask whether the spy is currently at location 19, to which you will receive a truthful yes/no answer. If the answer is “yes,” you reach your goal; if the answer is “no,” you can ask the next time whether the spy is at the same or another location of your choice. Devise an algorithm that will find the spy after a finite number questions.
Leave the answer in the comments below.
Anany Levitin is a professor of Computing Sciences at Villanova University. He is the co-author of Algorithmic Puzzles with Maria Levitin. He is the author of Introduction to the Design and Analysis of Algorithms, Third edition, a popular textbook on design and analysis of algorithms, which has been translated into Chinese, Greek, Korean, and Russian. He has also published papers on mathematical optimization theory, software engineering, data management, algorithm design, and computer science education.
Subscribe to the OUPblog via email or RSS.
Subscribe to only mathematics articles on the OUPblog via email or RSS.
Image credit: Leonardo da Pisa, Liber abbaci, Ms. Biblioteca Nazionale di Firenze, Codice magliabechiano cs cI, 2626, fol. 124r Source: Heinz Lüneburg, Leonardi Pisani Liber Abbaci oder Lesevergnügen eines Mathematikers, 2. überarb. und erw. Ausg., Mannheim et al.: BI Wissenschaftsverlag, 1993. Public domain via Wikimedia Commons.
Let B_i be the unique base two representation of the natural number t. Let c = B_0, d = B_1, e = sum(B_{2+2k} 2^k), f = sum(B_{3+2k} 2^k) and g = (2c – 1) e + t ( 2 d – 1 ) f.
Then the sequence g(t) will eventually match the position of the spy at a + b t. if log_2 max(1 +|a|, 1+|b|) <= n, then will will find the spy before t = 4^(n+1).
This can be made less redundant by replacing e and f with e' = e – c + 1, f' = f – d + 1 but the analysis would be trickier.
is the line finite in length or not?
Scan over all possible pairs of natural numbers (a,b) in any standard way (one of the ways to show that NxN has the same cardinality as N), and at the t-th such step, check if the spy is at a+bt.