Algorithms and pseudo code

A computing program is a series of actions that are carried out in a specific order. A procedure for solving a problem is called an algorithm. (named after a 9th century Persian mathematician). Hence any procedural language program is also an algorithm. It consists of

• The actions to be executed
• The sequence in which these actions are to be performed.

Before attempting to write a computer program it is essential to have a good understanding of the problem (problem specification) and a strategy for solving it. This is usually the hardest part of the process and is independent of any programming language. There are at least four distinct phases to developing and writing a computer program.

1. Problem specification - Identify and understand the problem to be solved.
2. Identify and evaluate different strategies for solving the problem.
3. Use a suitable methodology to document the solutions. Either Textual (i.e. pseudo code)or a Graphical technique (flow chart). At this stage you may need to clarify the problem specification. It's important to update this to record the changes made.
4. Code the solution using the program language of your choice. As the developer/programmer you must then test the program and debug the program to ensure it does what its supposed to do, before giving it to the end user.

It is particularly important that steps 3 and 4 are kept separate. Trying to code a solution, without having thought through the problem will result in clumsy and inefficient code that is hard to read. You should be able to trace through an algorithm using nothing more than pencil and paper to prove it works.

Methodologies

The technique you use to describe and document the algorithm may be textual, or graphical, e.g. flow chart. Use whichever technique you are most comfortable with. These notes look specifically at textual methods. By restricting the vocabulary and structure of English sentences we might remove many of ambiguities we experience in everyday use of English.

Remember structured English, decision tables, flow charts etc. are different ways of representing the same thing. Its largely up to you which technique you use. Choose the one you are most comfortable with. You do however need to be able convert between the different them.

From plain language to program language

Initially the requirement will most probably be specified in plain language by the user, with no clear idea whether what is being asked for is actually possible. Have a read through the request and decide if it is feasible. The next step is to write out using Structured English a way to achieve what is being asked for. This may go through many iterations before it is deemed to be workable.

As the diagram indicates, the structured English, (or sometimes called PDL - Program Definition Language), may be further refined using Pseudo code. By this stage of development, the developer/programmer is identifying the variables and structures etc. to be used within the program itself. As a simple example, a web page may be laid out using DIV tags, or a TABLE structure. When writing Structured English this decision can probably be deferred to the pseudo code stage.

The danger with pseudo code is it can easily start to look very much like program code. Especially if the developer knows what the target language is.

So what is the difference between these.

• Plain (or narrative) English is unwieldy and potentially ambiguous for the reasons outlined.
• Structured English on the other hand uses a restricted vocabulary and reads like a list of instructions. It focuses on what to do, not how it is to be done.
• Pseudo code is concerned with how a process is carried out. It looks very similar to Structured English and also like your favourite programming language. It is not concerned with the syntax of any particular language, nor its data types.
• A formal description of what must be done which must be syntactically correct in order for it to be understood by a compiler (or interpreter).

The danger with pseudo code is it can easily start to look very much like program code. Especially if the developer knows what the target language is.

Structured English is simply an abbreviated form of English used to write down a set of instructions. It has no formal structure and is simply a written form of the instructions or steps to solve a problem. It may be regarded as program code without the syntax constraints of any particular program language.

Structured English, or "pseudo code" consists of the following elements:

1. Sequence blocks consisting of a series of commands (also called imperative sentences, or operational statements) written in the order they are to be performed
2. Conditional blocks indicated by keywords such as IF, THEN, and ELSE
3. Repetition blocks indicated by keywords such as DO, WHILE

When writing Structured English, statements should be clear, concise and unambiguous, so doesn't need additional comments! The Structured English should be expressed in sequence, conditional, and repetition blocks. Indent the instructions to indicate structure. For more complex problems, a whole block of instructions may be given a name which is then called as required by some higher level block.

There is no standardised way of writing structured English however it is recommended the following rules are adopted.

1. Express all logic in terms of
   • sequential instructions
   • selection (decision) instructions
   • repetition (iteration) instructions
2. Capitalize accepted keywords such as
   • IF ... THEN ... ELSE
   • SELECT ... CASE
   • DO ... LOOP UNTIL
   • WHILE ... WEND

   keep everything else in lower case.

3. Indent statement structures (blocks), or use brackets to clearly show their hierarchy (nesting).

   For example the Python programming language chooses to use indentation to clearly denote where a block of code starts and ends, while other programming languages, such as Javascript uses curly braces {}. You may choose to adopt either convention but indentation is probably better suited to pseudo code you write.

4. When words or phrases have been defined in a data dictionary, underline them to indicate they have a specialised (or reserved) meaning.
5. Compound conditions may be formed using the logic operators AND, OR and NOT.
6. Conditions may be formed using the relational operators EQUALS (=) , GREATER THAN (>) or LESS THAN (<).
7. Sentences of structured English (or pseudo code) consist of:
   • Verbs/Actions. This should be chosen from a small set (a maximum of 40 serves most businesses) of action-oriented verbs such as
     • GET / READ, PUT / WRITE, DISPLAY, COMPUTE, ADD, SUBTRACT, MULTIPLY, DIVIDE, DELETE, FIND, MOVE, MERGE, REPLACE, SET, SORT , EXTRACT, COLLATE, VALIDATE ...
   • Nouns/Objects
     • elements known in the data dictionary, e.g. data flow inputs and outputs, attributes, variable names.
     • local variables in terms of known elements
   • Adjectives from Domain
     • e.g., overdue, on-reserve, ...
   • Avoid programming language punctuation (parentheses may be used to clarify order of operations, in a mathematical for example.)


8. Pre/Post Conditions
   • State what preconditions must be true for the process to function
   • State what post conditions will be true after the process has been completed
   • States what the process must do, not how it will do it.
     • The process may be well understood e.g. SORT.
     • There might be many practical ways of performing the functions, and the choice may be left to the designer or programmer. E.g. Bubble sort, Linked list, binary tree etc.
     • It might be necessary to explore implementation alternatives.

The structures of sequence, selection and repetition share one fundamental property. They each have a single entry and exit point. A structured English description is only legal when it is structurally equivalent to some combination of these three basic building blocks.

Structured English is not pseudo code. Pseudo code is concerned with the precise details of process, e.g. variable declaration, initialisation, opening and closing files, etc. while Structured English specifies what need to done, not how it is to be achieved.

Some typical keywords found in structured English.

By identifying some of the basic operations of a computer a list of candidate words for a Structured English / pseudo code can be drawn up. No doubt you make up a few more but the general aim is to keep the list as short as possible; to avoid any possible ambiguity.

There are no rules or standards for writing Structured English. EOF is short for End Of File. The list is by no means definitive. The only criteria when writing Structured English is, does it make sense to the user and the programmer?

A cookery recipe is a form of pseudo code. In this case the instructions are intended for a human cook, not a machine. The point of pseudo code is, you don't have to be an expert programmer (in, Pascal, C++, Java, or whatever you favourite language is) in order to understand the solution.

Exam questions based on program fragments use pseudo code simply because different, schools, colleges or universities will probably have taught different program languages.

Good programmers keep their Structured English or pseudo code, by embedding it into the program as comments which are intended for human readers, and ignored by the program translators.

Example of pseudo code

The problem is to search a list and find whether a specified value is in the list. I.e. is value in list?. Return answer True or False. The algorithm starts with a sequence of 3 instructions (yellow). This is typical,or and usually where variables and other initial conditions are set up.

Next the algorithm encounters repetition (orange). Nested inside this loop, the first instruction is the start of a sequence. The next instruction is a selection block (green). Only the TRUE part is included, no special action is taken if the condition is false.

The next instruction continues the sequence (yellow), after which the end of the repetition block is encountered.. The algorithm continues the sequence with the return flag instruction. which is the last instruction. Program control is then returned to the parent level.

READ value
SET index = 0
SET flag = FALSE

DO 
READ LIST(index)

IF LIST(index) = value
   flag = TRUE
   RETURN flag
ENDIF

INCREMENT index
      
WHILE NOT end of LIST

RETURN flag

END search    

Non programmers might find this initially confusing because the algorithm does not necessarily have to run to the end before it is terminated. In this case, the value we are looking for might be at the start of the list. The moment it is found the algorithm returns true. If the value is not in the list, then the algorithm will run to the end of list before returning the answer false.

Don't start with the initial conditions. Wait until the algorithm is fully developed, you probably won't know what they are anyway. The trick is to imagine the code is already running, as if you have entered the do loop, though you may not even realise you are in a loop. At the end of sequence you realise it needs to be repeated, so construct the repetition loop. This gets you to the end, when, in this case, you run out of items to search. so return the result, a flag in this case, to say its TRUE at least one occurrence of the search item has been found. Now you know that this flag must initially be set to FALSE.

You will see some carefully crafted algorithms in books, what the author(s) don't tell you, is how many iteration's it took to arrive at this solution. So don't be fooled, or expect to get your algorithm right first time, or even perhaps the tenth time.

The initial specification

In this example of a search routine we have said nothing about the list itself. In fact we have assumed the worst case scenario, that the items are in a random order. This probably doesn't matter for short lists, but might you have (say) a million records to search. In a random list, that means on average, searching 500,000 records.

Suppose the list was sorted in say (alphabetical or numerical order. Now if you picked up a phone book and want to search for a particular Mr. Williams, you wouldn't start at the beginning, but take a guess and start somewhere new the back, then track backwards or forwards until you find your Mr. Williams.

Very often a simple change to the initial specification can turn an insurmountable problem, into something more manageable.

Trace tables - testing an algorithm

Trace tables provide a pencil and paper way of checking an algorithm while is is still under development. Taking our search example, the first thing to do is construct a (small) set of sample table. Lets use just 5 numbers for this purpose

    5,22,43,53,73

Next construct a table showing variables along the top and steps down the side. In this case we have four variables, value, index and flag. Now we literally step through the algorithm noting the changes along the way, and until it terminates. for the first test lets choose a number we know is in the list, 43.

As you can see this part of the algorithm works. A second test would be to enter a value that is not in the list, and check it terminates with the right answer. That is left as an exercise for the reader.

While Trace tables work, the are prone to human error. They can also take a long time to check an algorithm properly. When your program is not doing what you expected, then having the program itself output a modified form of trace table, by adding(say) alert boxes at strategic point in the program to assist with debugging.