Algorithms Part 1: Two Traditional Views
Engineers and computer scientists think about algorithms quite differently. Working with recent graduates, I've consistently found that while CS grads are quite comfortable with notions of computational complexity and repeat-ability, engineers shine on topics related to algorithm interpretation and deployment. To a certain extent, this is to be expected. In a computer science curriculum, algorithms are discussed quite formally. Meanwhile, engineering programs tend to focus less on theory and more on applied problem solving.
I believe it is the interaction between these two sets of knowledge -- the theory of algorithms and the practice of problem solving -- that is essential to achieving their shared goal of providing analytical insight. This may sound obvious, but in many cases it appears that universities overemphasize one at the expense of the other. From framing, design, programming, and testing to deployment, evaluation, adjustment, and retirement, the use of algorithms is always about both the immediate technical need and the broader problem and context. Therefore, it is critical that we develop in young computer scientists and engineers alike a familiarity for the interaction between computation and problem solving.
So, I thought I would use this blog to work through an example or two of how algorithmic thinking is conducted in practice, emphasizing the various inter-dependencies between the code and the problem at hand.
Let's start with Sudoku. It's a game almost as ubiquitous as the crossword -- and fortunately for us, much better suited for algorithmic evaluation. It is fairly simple:
The puzzle takes the form of a 9x9 grid -- that's 81 cells in total
To solve the puzzle, the player must fill each cell with a number between 1 and 9
Some of the cells are already filled in, and the player starts from there
The task of the player is to fill in the remaining cells in such a way as to satisfy these three rules:
Each row (of 9 cells) must contain exactly one 1, 2, 3, 4, 5, 6, 7, 8, and 9 (no number may be missing or repeated in the row)
Each column must also have exactly one cell with each number
Each 3x3 box (indicated to the right) must also have exactly one cell with each number.
So, the basic task of Sudoku is to figure out which cells have to be particular numbers, in order to simultaneously satisfy each of those three constraints. But we're going to examine Sudoku from the other side: it's design. The central question that we will attempt to answer is: how can we efficiently produce Sudoku puzzles for players? In the next post, we start by examining the most basic possible approaches and then get more sophisticated.