An algorithm is just a way of doing something and as such every program embodies an algorithm. This is an extract from my book Trick of the Mind which explores what it is to be a programmer.

The Trick Of The Mind - Programming & ComputationalThought

Buy Now From Amazon

Chapter List

1. The Trick Of The Mind

2. Little Languages
      Extract: Little Languages Arithmetic

3. Big Languages Are Turing Complete

4. The Strange Incident of The Goto Considered Harmful
      Extract: The Goto Considered Harmful

5. On Being Variable  

6. Representation

7. The Loop Zoo
      Extract The Loop Zoo
      Extract Advanced Loops
   

8. Modules, Subroutines, Procedures and Functions
      Extract Modular Programming

9. Top-Down Programming 

10. Algorithms
       Extract: Binary Search 
       Extract: Recursion ***NEW!!

11. The Scientific Method As Debugging 

12. The Object Of It All
       Extract Why Objects 

 <ASIN:1871962722>

<ASIN:B09MDL5J1S>

Now is the time to confront the algorithm. It is worth pointing out that to an extent we have been doing this since Chapter 1. When you are writing lists of instructions you are, in essence, implementing an algorithm. An algorithm is just a way of doing something and as such every program embodies an algorithm. However, the use of the term “algorithm” generally refers to the core part of what the program is doing, not all of the small details needed to make the whole thing work. Algorithms are the big picture of how to do something and as such they can be simple or sophisticated and occasionally so clever that they are difficult to follow.

It is difficult to explain the subject of algorithms without getting involved with “advanced” topics and mathematics in particular, but many algorithms are concerned with how to do very simple things. In this chapter we examine the idea of an algorithm by way of a very non-technical example. Along the way we meet one of the cleverest algorithms in all of computer science and, incidentally, a big contributor to the success of Amazon and other major companies.

The Book Problem

The very first thing to say is that books are never a problem and always welcome, however finding a book you are looking for is often difficult. What we need to do is examine the way that you look for a book in a suitably large library. The questions are “how do you find a book?” and “what algorithm are you using?”

Whenever you ask a question like this there is a tendency to gloss over the details. For example, you might say “I just look at the shelves and I spot the title”. This may be what you think you do, but introspection of this sort is usually vague because you might well not be aware of what you actually do. Just looking isn’t an algorithm, or rather it isn’t an accurate description of an algorithm.

Usually to make what is happening apparent, you first have to make what is to be done clear and precise. Essentially you have to create a description of the algorithm that can be implemented by a non-intelligent entity – i.e. a computer. Without practice this is not as easy as it sounds because you generally don’t notice when you have used a fragment of intelligence in your description. Getting down to the fine details of a set of actions can be very difficult and it is at the heart of being a good programmer.

In the book search case what this means is to say how the books are placed on the shelves and how the searcher can interact with them. Suppose the books are placed on the shelves with a position number below each book and the searcher can ask for a book by giving the number. If you look back to Chapter 6 you will recognize our bookshelves as an array of books. The searcher can say “What is the title of book number 42” and can compare this to the title being searched for. When the book in question is found the task is complete.

Now, how do you look for a book?

The Case of the Lazy Librarian

First we can assume that we have a very lazy librarian who has put the books on the shelves in any old order, as they arrived at the library say. If you are searching for the The Programmers Guide To Theory then where do you start? There is no obvious place to start as the books are not in any particular order and so the book you are looking for could be anywhere. However, it is important that you check each possible location otherwise you might conclude the book you are looking for isn’t there when it actually is.

A simple algorithm is to start at location 1, retrieve the book and compare it to the title you are looking for, if it is the book you are done and can stop. If it isn’t the book you have to retrieve the book at location 2 and check that it is your book. You carry on like this until either you have found the book or you have reached the last book – if there are N books this is location N.

This is an algorithm and we can write it down to give it a more concise form:

S = 1
While S < = N
	if book[S] == Target Then Exit Loop
	S = S+1

We are assuming that there are N possible books and writing the shelf locations as if they were an array of books. We set S to 1 at the start of the loop, which means we check location 1 first and exit the loop if we have found the book. If not we increment the position so that it is now 2 and repeat the test to see if book at location 2 is the book we are looking for. The loop also ends if S is greater than N, i.e. we don’t look for shelf location N+1 as it doesn’t hold a book at all.

There are many ways to express this algorithm and even experienced programmers will argue what the best expression of it is in any given language, but the one above is reasonable.

Notice, however, that the loop can end for two different reasons – either we found the book or we ran out of books. How can you tell what the outcome was? Simple enough – at the end of the loop, if S is greater than N we didn’t find the book, but if S is less than or equal to N it is the location of the book we are looking for.

You might find the exact expression for what is a simple algorithm more complex and intricate than you expected. After all you just move along the books and pull out the one you are looking for. This maybe how it seems to you, but you are implicitly incrementing a position counter, stopping when you run out of books and, equally, stopping incrementing the list when you find the book. The program is a precise description of the algorithm.

Beginners often make mistakes in creating the program because they make assumptions about the competence or intelligence of the system. For example, many will miss out the step that sets S to 1 to ensure that the search starts at the beginning. The reason is usually that the agent running the program is assumed to “know” where to start. Similarly, not checking the value of S to find the end of the search is omitted because it is “obvious” when the end of the shelf has been reached.

Nothing is obvious to a computer.

This search algorithm is generally called linear search because you scan the array of objects from start to finish until you find what you are looking for. You can easily appreciate that at worst it takes N steps to find or conclude that the book isn’t in the library and on average N/2 steps to find the book, assuming it is in the library.