Algorithms and Truth

Fixing a broken lamp

In an earlier post, I introduced the concept of algorithms as a way of solving problems using a step-by-step process.  Most of us understand algorithmic thinking when it is applied to everyday tasks.  Fixing a broken lamp is a good example of an algorithm, because it involves taking different paths, depending on the outcome of several questions.  A recipe is a simple form of an algorithm:

Sausage and Peppers
1 package of Italian sausage (mild or hot, your choice)
2 bell peppers (red, orange, yellow, green, your choice), sliced
1 sweet onion, sliced
1 Tbsp minced garlic
fresh basil (or dried)
2 Tbsp olive oil
1 28 oz can whole tomatoes
1 package angel hair or penne pasta

1. Cook the sausage whole, on medium heat, until browned, using 1 Tbsp of olive oil. Alternatively, broil the sausage in the oven.  Slice into pieces and reserve
2. In the same pan, cook the bell peppers, onion over medium heat using 1 Tbsp of olive oil, until onion is lightly browned.
3. Add the garlic to the pan and simmer until slightly browned.
4. Add the sausage back to the pan.
5. Puree the tomatoes by pulsing, so that there are still small chunks.
6. Add the tomatoes to the pan, along with the basil.
7. Simmer the sauce on medium-low until reduced and thickened, about 10 or 15 minutes.
8. Serve over angel hair or penne pasta, cooked to package instructions for al dente.

Programming as Problem Solving

The programming process

I highly recommend the book Computers Ltd.: What They Really Can't Do as a good introduction to the concepts of computability and complexity from a non-technical perspective.  The figure at right is inspired by a diagram the book uses to introduce the concepts of programming and programming languages.

When a programmer has an idea for developing a new piece of software, the first thing he does is express this idea as a algorithm.  An algorithm is a method for solving a problem in a step-by-step fashion.  The next step is to implement this algorithm in a high-level programming language; this is a language designed to make it easy for a human to tell the computer what he wants it to do.  The programmer then uses a special program called a compiler to translate this language into machine code, which is a series of instructions the computer can understand.  The result is a software program that can be run on a machine, such as a laptop or a smart phone.

From this description, you can see programming is a two-step process, of first designing an algorithm and then writing it in a programming language.  Algorithm design is usually the hardest part; computer scientists often refer to the need to train students to think algorithmically.  A good definition of what we mean by this is found in Developing Algorithmic Thinking with Alice, a paper by Cooper et al. that was published in the 2000 Information Systems Education Conference:

1) state a problem clearly, 2) break the problem down into a number of well-defined smaller problems, and 3) devise a step-by-step solution to solve each of the sub-tasks

This is an extremely important skill that transfers over into many disciplines, and the reason why we believe most students can benefit from taking at least one programming class sometime in their education.