What do you think?
Rate this book
Algorithmic Puzzles
While many think of algorithms as specific to computer science, at its core algorithmic thinking is defined by the use of analytical logic to solve problems. This logic extends far beyond the realm of computer science and into the wide and entertaining world of puzzles. In Algorithmic Puzzles , Anany and Maria Levitin use many classic brainteasers as well as newer examples from job interviews with major corporations to show readers how to apply analytical thinking to solve puzzles requiring well-defined procedures.
The book's unique collection of puzzles is supplemented with carefully developed tutorials on algorithm design strategies and analysis techniques intended to walk the reader step-by-step through the various approaches to algorithmic problem solving. Mastery of these strategies--exhaustive search, backtracking, and divide-and-conquer, among others--will aid the reader in solving not only the puzzles contained in this book, but also others encountered in interviews, puzzle collections, and throughout everyday life. Each of the 150 puzzles contains hints and solutions, along with commentary on the puzzle's origins and solution methods.
The only book of its kind, Algorithmic Puzzles houses puzzles for all skill levels. Readers with only middle school mathematics will develop their algorithmic problem-solving skills through puzzles at the elementary level, while seasoned puzzle solvers will enjoy the challenge of thinking through more difficult puzzles.
The book's unique collection of puzzles is supplemented with carefully developed tutorials on algorithm design strategies and analysis techniques intended to walk the reader step-by-step through the various approaches to algorithmic problem solving. Mastery of these strategies--exhaustive search, backtracking, and divide-and-conquer, among others--will aid the reader in solving not only the puzzles contained in this book, but also others encountered in interviews, puzzle collections, and throughout everyday life. Each of the 150 puzzles contains hints and solutions, along with commentary on the puzzle's origins and solution methods.
The only book of its kind, Algorithmic Puzzles houses puzzles for all skill levels. Readers with only middle school mathematics will develop their algorithmic problem-solving skills through puzzles at the elementary level, while seasoned puzzle solvers will enjoy the challenge of thinking through more difficult puzzles.
257 pages, Paperback
First published September 13, 2011
139 people are currently reading
899 people want to read
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 - 11 of 11 reviews
July 8, 2021
I got to know about this book because it was mentioned in his book on Algorithms as an accompaniment. I think one of the best ways to learn concepts is to do problems with them and this was quite ideal. This book is an anthology of Mathematical and Algorithmic puzzles.
Structure There are 3 chapters in this book - Easy, Medium and Hard. Some of the Hard Puzzles are genuinely hard, but many of them are approachable.
Well Known Puzzles There are many well known and famous problems here such as Monkey and the Coconuts, Josephus Problem and Godel, Escher, Bach's MU Puzzle . Some of the problems are variations of well known problem.
For example, there is a famous problem which asks whether we can tile a (2^n x 2^n) board with exactly 1 square missing with L-shaped trominoes. This has a beautiful proof with Mathematical Induction. In this book, we are asked how we can tile a board of size (2^n x 2^n) with 1 missing square with L shaped trominoes of 3 different colours such that no 2 of the same colour are touching.
There is a problem (Point Colouring) that was asked in the 1987 International Mathematical Olympiad . It has a very beautiful proof by Contradiction.
There are a few puzzles that are based on games proposed by John Conway like Game of Life, Toads and Frogs, Counter Exchange, One Dimensional Solitaire and Bulgarian Solitaire (I found this the hardest puzzle in the whole book.)
There are variations of the Tower of Hanoi problem like Reve’s Puzzle
The N-Queens problem is very famous. However, we are asked to provide a linear time constructive solution rather than the traditional exponential backtracking one.
There is Bachet's Problem and many problems on weighing and detecting the counterfeit coin.
Topics Covered There are many elegant problems about Invariants and Logical Deduction. There are many problems that are 'Constructive' in nature where we have to construct an answer or a counterexample rather than just provide an existence proof.
There are several problems that are based on the chessboard and the movement of chess pieces (Sometimes new pieces are invented for the purpose of the puzzle like The Prince's Tour ).
Mathematical Induction is an important techinque for the purpose of this book. There are several solutions which are difficult to understand, but easy to guess and prove with Mathematical Induction.
Here are some of the puzzles I really enjoyed.
One Coin for Freedom - A jailer offers two imprisoned programmers, A, B freedom if they win a game. The jailer sets up a 8 x 8 board with one coin on each cell with some heads and tails. The jailer takes only A into the room and shows A the cell B will be asked to guess. A must flip over exactly one coin from heads to tails. B is then bought into the room and made to guess the selected cell.
They may plan their strategy beforehand but cannot communicate during the game.
How do they win ?
Penny Distribution Machine - There is a stack of pennies. In one move, we remove 2 pennies from any one stack and add 1 penny to the stack on it's right. We will stop when no stack has more than 1 penny.
1. Does the final distribution of pennies depend on the order we process the stacks ?
2. What is the minimum number of stacks that will be created ?
3. How many moves will it take us ?
Hats with Numbers There are n people who are wearing a hat. Each hat has a number written on it in {0, 1, \dots , n - 1}. The numbers written on the hats need not be distinct and may repeat on multiple hats.
Everybody can see the number written on everybody else's hat but their own. Everybody must write down the number they think is on their own hat on a piece of paper. Nobody is allowed to see the number written by anybody else and no form of communication is allowed between participants.
What strategy can be adopted so that at least one person gets the number on their hat correct ?
Structure There are 3 chapters in this book - Easy, Medium and Hard. Some of the Hard Puzzles are genuinely hard, but many of them are approachable.
Well Known Puzzles There are many well known and famous problems here such as Monkey and the Coconuts, Josephus Problem and Godel, Escher, Bach's MU Puzzle . Some of the problems are variations of well known problem.
For example, there is a famous problem which asks whether we can tile a (2^n x 2^n) board with exactly 1 square missing with L-shaped trominoes. This has a beautiful proof with Mathematical Induction. In this book, we are asked how we can tile a board of size (2^n x 2^n) with 1 missing square with L shaped trominoes of 3 different colours such that no 2 of the same colour are touching.
There is a problem (Point Colouring) that was asked in the 1987 International Mathematical Olympiad . It has a very beautiful proof by Contradiction.
There are a few puzzles that are based on games proposed by John Conway like Game of Life, Toads and Frogs, Counter Exchange, One Dimensional Solitaire and Bulgarian Solitaire (I found this the hardest puzzle in the whole book.)
There are variations of the Tower of Hanoi problem like Reve’s Puzzle
The N-Queens problem is very famous. However, we are asked to provide a linear time constructive solution rather than the traditional exponential backtracking one.
There is Bachet's Problem and many problems on weighing and detecting the counterfeit coin.
Topics Covered There are many elegant problems about Invariants and Logical Deduction. There are many problems that are 'Constructive' in nature where we have to construct an answer or a counterexample rather than just provide an existence proof.
There are several problems that are based on the chessboard and the movement of chess pieces (Sometimes new pieces are invented for the purpose of the puzzle like The Prince's Tour ).
Mathematical Induction is an important techinque for the purpose of this book. There are several solutions which are difficult to understand, but easy to guess and prove with Mathematical Induction.
Here are some of the puzzles I really enjoyed.
One Coin for Freedom - A jailer offers two imprisoned programmers, A, B freedom if they win a game. The jailer sets up a 8 x 8 board with one coin on each cell with some heads and tails. The jailer takes only A into the room and shows A the cell B will be asked to guess. A must flip over exactly one coin from heads to tails. B is then bought into the room and made to guess the selected cell.
They may plan their strategy beforehand but cannot communicate during the game.
How do they win ?
Penny Distribution Machine - There is a stack of pennies. In one move, we remove 2 pennies from any one stack and add 1 penny to the stack on it's right. We will stop when no stack has more than 1 penny.
1. Does the final distribution of pennies depend on the order we process the stacks ?
2. What is the minimum number of stacks that will be created ?
3. How many moves will it take us ?
Hats with Numbers There are n people who are wearing a hat. Each hat has a number written on it in {0, 1, \dots , n - 1}. The numbers written on the hats need not be distinct and may repeat on multiple hats.
Everybody can see the number written on everybody else's hat but their own. Everybody must write down the number they think is on their own hat on a piece of paper. Nobody is allowed to see the number written by anybody else and no form of communication is allowed between participants.
What strategy can be adopted so that at least one person gets the number on their hat correct ?
February 18, 2023
Absolutely class. Would recommend to all, not for the faint of heart.
December 27, 2018
My first puzzle book. It has been an interesting read. The solutions are clear and detailed.
July 18, 2012
Molti problemi matematici possono anche essere considerati "problemi informatici". In definitiva, risolvere il problema significa trovare un algoritmo tale che anche lo stupido computer possa risolverlo. In questo libro ci sono per l'appunto centocinquanta problemi di questo tipo. Gli autori in un certo senso barano, perché a volte ci sono anche dimostrazioni di impossibilità in alcuni casi e quelle non sono certo algoritmiche; ma non importa. Quello che importa è che ci sono i problemi, ci sono le soluzioni, ci sono le spiegazioni delle tecniche adottate per risolverli (mi ero dimenticato: la prima sezione del libro contiene un tutorial con alcuni problemi risolti e l'elenco di tecniche classiche per risolvere questi problemi, dal divide-et-impera al togli-uno). Il tutto con un taglio più informatico che strettamente matematico, il che forse potrebbe risultare più interessante per alcuni.
Tutti i problemi hanno sempre una spiegazione che rimanda alle tecniche usate nella loro risoluzione, oltre che - per quanto possa essere possibile in un campo come quello dei giochi matematici in cui spesso ci si passavano le cose in maniera carbonara - l'indicazione di dove il problema è stato presentato per la prima volta, magari in forma leggermente diversa.
Un'opera altamente consigliabile per gli appassionati di matematica e di informatica, insomma!
Tutti i problemi hanno sempre una spiegazione che rimanda alle tecniche usate nella loro risoluzione, oltre che - per quanto possa essere possibile in un campo come quello dei giochi matematici in cui spesso ci si passavano le cose in maniera carbonara - l'indicazione di dove il problema è stato presentato per la prima volta, magari in forma leggermente diversa.
Un'opera altamente consigliabile per gli appassionati di matematica e di informatica, insomma!
March 4, 2018
This is essentially a collection of puzzles. Algorithmic puzzles that have a defined procedure for solving problems. I loved that it wasn't written like a textbook yet for an amateur. It has a short tutorial section and the rest are problems to solve. Not going to lie, the problems are very challenging (even the easy ones).
March 7, 2018
A very entertaining book which exercises your algorithmic thinking muscles. If you like puzzles, and you like programming or algorithms, get this book!
April 13, 2020
A wonderful collection of easily-stated and fun to solve problems of all difficulty levels.
The problems are algorithmic in their nature, involving steps and processes rather than equations and quantities. The solutions are always elementary, in that they do not require the reader to be familiar with university level mathematics. However, they present a richness in terms of the mathematical mindset required to solve them.
Clues and pointers are given in a separate chapters. Without them, many problems in the Hard section are on a difficulty level on par with the International Mathematical Olympiads (IMO).
The problems are algorithmic in their nature, involving steps and processes rather than equations and quantities. The solutions are always elementary, in that they do not require the reader to be familiar with university level mathematics. However, they present a richness in terms of the mathematical mindset required to solve them.
Clues and pointers are given in a separate chapters. Without them, many problems in the Hard section are on a difficulty level on par with the International Mathematical Olympiads (IMO).
January 16, 2019
Many interesting puzzles with good explanations in places (the tutorials at the start are the strongest point), but unfortunately spoiled by the inclusion of numerous puzzles where the solutions reduce to tedious symbol-pushing with little or no insight.
This entire review has been hidden because of spoilers.
January 6, 2019
will not read till end as this are quite hard challenges and I dont have enough motivation to finish them all
Read
May 4, 2025hh
December 30, 2020
many interesting examples to learn from are in this book.
Displaying 1 - 11 of 11 reviews