Introduction to Pseudocode

1 AIntroduction to PseudocodeWhat is Pseudocode ?Analgorithmis a sequence of instructions to solve a well-formulated computationalproblem specified in terms of itsinputandoutput. An algorithm uses the input togenerate the output. For example, the algorithmPATTERNCOUNT uses stringsTextandPatternas input to generate the number COUNT(Text,Pattern)as its order to solve a computational problem, you need to carry out the instructionsspecified by the algorithm. For example, if we want you to count how many timesPatternappears inText, we could tell you to do the from the first position ofTextand check whetherPatternappears inTextstarting at its first yes, draw a dot on a piece of to the second position ofTextand check whetherPatternappears inTextstarting at its second yes, draw another dot on the same piece of until you reach the end the number of dots on the humans are slow, make mistakes, and hate repetitive work, we inventedcomputers, which are fast, love repetitive work, and never make mistakes.

2 However,while you may easily understand the above instructions for counting the number ofoccurrences ofPatterninText, no computer in the world can execute them. The only115 WHICH DNA PATTERNS PLAY THE ROLE OF MOLECULAR CLOCKS?reason you can understand them is because you have been trained for many years tounderstand human language. For example, we didn t specify that you should startfrom ablankpiece of paper without any dots, but you assumed it. We didn t explainwhat it means to reach the end ofText ; at what position ofTextshould we stop?Because computers do not understand human language, algorithms must be rephrasedin aprogramming language(such as Python, Java, C++, Perl, Ruby, Go, or dozens ofothers) in order to give the computer specific instructions. However, we don t want todescribe algorithms in a specific language because it may not be your favoriteOur focus is on algorithmic ideas rather than on implementation details, which iswhy we will meet you halfway between human languages and programming languagesby usingpseudocode.

3 By emphasizing ideas rather than implementation details, pseu-docode is able to describe algorithms without being too formal, ignoring many of thetedious details that are required in a specific programming language. At the same time, Pseudocode is more precise and less ambiguous than the instructions we gave abovefor counting a pattern in a example, consider the following Pseudocode for an algorithm calledDISTANCE,whose input is four numbers (x1,y1,x2,y2) and whose output is one numberd. Canyou guess what it does?DISTANCE(x1,y1,x2,y2)d (x2 x1)2+(y2 y1)2d pdreturndThe first line of Pseudocode specifies the name of an algorithm (DISTANCE), followedby a list ofargumentsthat it requires as input (x1,y1,x2,y2). Subsequent lines containthe statements that describe the algorithm s actions, and the operationreturnreportsthe result of the can invoke an algorithm by passing it the appropriate values for its example,DISTANCE(1, 3, 7, 5)would return the distance between points(1, 3)and(7, 5)in two-dimensional space, by first computingd 7 1)2+(5 3)2=40and then computingd p40.

4 116 WHICH DNA PATTERNS PLAY THE ROLE OF MOLECULAR CLOCKS?The Pseudocode forDISTANCE uses the concept of avariable, which contains somevalue and can be assigned a new value at different points throughout the course of analgorithm. To assign a new value to a variable, we use the notationa b,which sets the variableaequal to the value stored in variableb. For example, in thepseudocode above, when we computeDISTANCE(1, 3, 7, 5),dis first assigned the value(7 1)2+(5 3)2=40 and then is assigned the , we can use any name we like for variable names. For example, thefollowing Pseudocode is equivalent to the previous Pseudocode (x,y,z,w)abracadabra (z x)2+(w y)2abracadabra pabracadabrareturnabracadabraWhereas computer scientists are accustomed to Pseudocode , we fear that some biologistsreading this book might decide that Pseudocode is too cryptic and therefore modern biologists deal with algorithms on a daily basis, the language theyuse to describe an algorithm may be closer to a series of steps described in plain , some bioinformatics books are written without Pseudocode .

5 Unfortu-nately, this language is insufficient to describe the complex algorithmic ideas behindvarious bioinformatics tools that biologists use every be able to explain complex algorithmic ideas, we will need to delve deeper intothe details of Pseudocode . As a result, you will be able not only to understand thealgorithms in this book, but use Pseudocode to design your own algorithms!NutsandBoltsofPseudocodeWe have thus far described Pseudocode only superficially. We will now discuss someof the details of Pseudocode that we use throughout this book. We will often avoidtedious details by specifying parts of an algorithm in English, using operations that arenot listed below, or by omitting noncritical DNA PATTERNS PLAY THE ROLE OF MOLECULAR CLOCKS?ifconditionsThe algorithmMINIMUM2shown below has two numbers (aandb) as its input and asingle number as its output. What do you think that it does?

6 MINIMUM2(a,b)ifa>breturnbelsereturnaThis algorithm, which computes the minimum of two numbers, uses the followingconstruction:ifstatementXis trueexecute instructionsYelseexecute instructionsZIf statementXis true, then the algorithm executes instructionsY; otherwise, it executesinstructionsZ. For example,MINIMUM2(1, 9)returns 1 because the condition 1 > 9 is following Pseudocode computes the minimum of three (a,b,c)ifa>bifb>creturncelsereturnbelsei fa<creturnaelsereturncWe may also useelse if, which allows us to consider more than two different possi-bilities in the sameifstatement. For example, we can compute the minimum of three118 WHICH DNA PATTERNS PLAY THE ROLE OF MOLECULAR CLOCKS?numbers as (a,b,c)ifa>candb>creturncelse ifa>bandc>breturnbelsereturnaBoth of these algorithms are correct, but below is a more compact version that uses theMINIMUM2function that we already wrote as asubroutine, or a function that is calledwithin another function.

7 Programmers break their programs into subroutines in orderto keep the length of functions short and to improve (a,b,c)ifa>breturnMINIMUM2(b,c)elseretur nMINIMUM2(a,c)STOP and Think:Can you rewriteMINIMUM3using just a single line of pseu-docode?EXERCISE BREAK:Write Pseudocode for an algorithmMINIMUM4that com-putes the minimum of four , we may omit the else the following DNA PATTERNS PLAY THE ROLE OF MOLECULAR CLOCKS?Summing Integers Problem:Compute the sum of the first n positive : A positive : The sum of the firstnpositive a fixed number, then we could solve this problem using our existing frame-work. For example, the following programSUM5returns the sum of the first fiveintegers ( , 1+2+3+4+5=15).SUM5()sum 0i 1sum sum+ii i+1sum sum+ii i+1sum sum+ii i+1sum sum+ii i+1sum sum+ireturnsumWe could then writeSUM6,SUM7, and so on. However, we cannot endorse this pro-gramming style! After all, to solve the Summing Integers Problem for anarbitraryintegern, we will need an algorithm that takesnas its input.

8 This is achieved by thefollowing algorithm, which we (n)sum 0fori 1tonsum sum+ireturnsum120 WHICH DNA PATTERNS PLAY THE ROLE OF MOLECULAR CLOCKS?GAUSS employs aforloop that has the following format:fori atobexecuteXThisforloop first setsiequal toaand executes instructionsX. Afterwards, it increasesiby 1 and executesXagain. It repeats this process by increasingiby 1 until it becomesequal tob, when it makes a final execution ofX. That is,ivaries through the valuesa,a+1,a+2, .. ,b 1,bduring execution of the different way of summing the firstnintegers, calledANOTHERGAUSS, is (n)sum 0i 1whilei nsum sum+ii i+1returnsumThis algorithm uses awhileloop having the following format:whilestatementXis trueexecuteYThewhileloop checks conditionX; ifXis true, then it executes instructionsY. Thisprocess is repeated untilXis false. (Note: ifXwinds up always being true, then thewhileloop enters aninfinite loop, which you should avoid at all costs, because youralgorithm will never end.)

9 In the case ofANOTHERGAUSS, the loop stops executingafterntrips through the loop, whenieventually becomes equal ton+1and the numbers1 throughnhave been added DNA PATTERNS PLAY THE ROLE OF MOLECULAR CLOCKS?Recursive algorithmsBelow is yet another algorithm solving the Summing Integers (n)ifn>0sum RECURSIVEGAUSS(n 1)+nelsesum 0returnsumYou may be confused by the fact thatRECURSIVEGAUSS(n)callsRECURSIVEGAUSS (n 1)as a subroutine. So imagine that you are computing the sum of the first 100 positiveintegers, but you are lazy and ask your friend to compute the sum of the first 99 positiveintegers for you. As soon as your friend has computed it, you will simply add 100 tothe result, and you are done! Yet little do you know that your friend is just as lazy, andshe asks her friend to compute the sum of the first 98 integers, to which she adds 99and then passes to you. The story continues until a friend is assigned 1.

10 Although everyindividual in this chain of friends is lazy, the group is nevertheless able to compute an example of arecursive algorithm, which subcon-tracts a job by calling itself (on a smaller input).EXERCISE BREAK:Can you write one line of Pseudocode solving the SummingIntegers Problem?You have undoubtedly been wondering why we have named all these summing algo-rithms Gauss . In 1785, a primary school teacher asked his class to sum the integersfrom 1 to 100, assuming that this task would occupy them for the rest of the day. Hewas shocked when an 8 year old boy thought for a few seconds and wrote down theanswer, 5,050. This boy was Karl Gauss, and he would go on to become one of thegreatest mathematicians of all time. The following one-line algorithm implements hisidea for solving the Summing Integers Problem. (Why does it work?)GAUSS(n)return(n+1) n/2122 WHICH DNA PATTERNS PLAY THE ROLE OF MOLECULAR CLOCKS?