We have covered a lot of ground in the previous Tech Tuesday posts on programming. Now it is time to return to the original definition that I provided in the introductory post, where I wrote that programming is “telling a computer what to do.” We have all the pieces we need: we have covered the syntax and semantics of programming languages; we have learned about variables and the data types they can hold; we have looked at reserved words and the control structures we can form with them; we have seend how to define functions and pass arguments to them; and in the last six posts we have encountered a variety of different data structures. So how do we put all of these together to tell the computer to do something?
What we need is to define a proper sequence of steps that leads to the desired outcome. In cooking we would call that a recipe. In programming we call it an algorithm, a word that comes from the Latin transliteration of the last name of the Persian mathematician Muḥammad ibn Mūsā al-Khwārizmī. He wrote one of the first books on Algebra and provided detailed steps for solving quadratic equations. Or as we would say today: he specified an algorithm for solving quadratic equations. It can be a big sounding word but it really is akin to a recipe. If you follow a sufficiently detailed recipe (and do it right) the food will come out (roughly) the same every time. Ditto for an algorithm.
Enough with the abstract, let’s go to a concrete example. I encountered this problem over the past weekend when I was talking to a young student taking a computer science class. Imagine you are given a sequence of integers and you are supposed to detect whether it contains an instance of the same integer at least four times in a row. So consider the following two sequences:
The first sequence contains no such instance (it has the number 8 repeated twice but that’s it). The second sequence has an instance of the number 8 repeated four times. This may seem like a contrived problem but there are actually many real world applications that have roughly this structure. Imagine for instance a production line that makes different parts and where making the same part repeatedly could be a sign of a problem with a machine that’s stuck.
Speaking of stuck, the student I was talking to was a bit stuck on some specifics of the programming language (Java) which he was supposed to use to solve this problem. I explained that it’s a better idea to first express the algorithm in plain English and only then think about implementing it in a particular language. So here is a first cut at it:
This is probably good enough for a human to follow but lacks a fair bit of detail for translating it into computer code. This is where we start thinking about all the parts from above and how we might use them. First, we will need data structure to hold our sequence of numbers. We could use an array or a list for that. Second, we need a variable to serve as our counter. Third, we need to repeat going over the numbers until we are either done with them or the counter gets to four, so we need a loop and a conditional as our control structures. So here is a second cut at the algorithm
This way of writing down the algorithm is beginning to look a lot like a computer program. But it is not written in a specific programming language. That’s a critical insight about algorithms – they are language independent recipes for getting things done. Or put differently, an algorithm like the one above can be implemented in any programming language (as long as it is Turing complete, which is true for any general purpose language).
Next Tuesday we will first fix an important omission in the algorithm above (can you state what it is?). Then we will learn about something known as pseudo code and wind up writing our first implementation (I am open to suggestions for which language to use first). In subsequent posts we will look at a bunch of different languages and learn about the performance of different algorithms.
