In Progress
Lesson 2, Topic 1
In Progress

# Specifications of Algorithm

Lesson Progress
0% Complete

A. Pseudo code Convention

We can describe an algorithm in many ways. We can use a natural language like English, although if we select this option,we must make sure that the resulting instructions are definite. Graphic representations called flowcharts are another possibility, but they work well only if the algorithm is small and simple.In this text we present most of our algorithms using a pseudo code that resembles C and Pascal.

1.Comments begin with // and continue until the end of line.

2.Blocks are indicated with matching braces: { and }. A compound statement (i.e.,a collection of simple statements)can be represented as a block.The body of a procedure also forms a block.Statements are delimited by ;.

3.An identifier begins with a letter.The data types of variables are not explicitly declared.The types will be clear from the context. Whether a variable is global or local to a procedure will also be evident from the context.We assume simple datatypes such as integer,float,char,boolean,and soon. Compound data types can be formed with records. Here is an example:

In this example,link is a pointer to the record type node.Individual data items of a record can be accessed with —–> and period. For instance if p points to a record of type node,p —–> data_1 stands for the value of the first field in the record.On the other hand,if q is a record of type node, q.data_1 will denote its first field.

4. Assignment of values to variables is done using the assignment statement

<variable>:=<expression>;

5.There are two boolean values true and false. In order to produce these values,the logical operators and,or,and not and the relational operators <,<=,=,/,>=,and > are provided.

6.Elements of multidimensional arrays are accessed using [ and ]. For example,if A is a two dimensional array, the (i,j)th element of the array is denoted as A[i,j]. Array indices start at zero.

7.The following looping statements are employed: for,while,and repeat- until.The while loop takes the following form

As long as (condition) is true,the statements get executed.When (condition) becomes false,the loop is exited. The value of (condition) is evaluated at the top of the loop. The general form of a for loop is:

Here valuel, value2, and step are arithmetic expressions.A variable of type integer or real or a numerical constant is a simple form of an arithmetic expression. The clause “step step” is optional and taken as +1 if it does not occur,step could either be positive or negative. variable is tested for termination at the start of each iteration. The for loop can be implemented as a while loop as follows:

A repeat-until statement is constructed as follows:

The statements are executed as long as <condition> is false. The value of <condition> is computed after executing the statements.

The instruction break; can be used within any of the above looping instructions to force exit. In case of nested loops, break; results in the exit of the inner most loop that it is a part of. A return statement within any of the above also will result in exiting the loops.A return statement results in the exit of the function itself.

8.A conditional statement has the following forms:

if <condition> then <statement>
if <condition> then <statement 1> else <statement 2>

Here(condition)is a boolean expression and (statement), (statement 1) and (statement 2) are arbitrary statements(simple or compound).
We also employ the following case statement:

Here(statement 1),(statement 2), etc. could be either simple statements or compound statements. A case statement is interpreted as follows. If (condition 1) is true, (statement 1) gets executed and the case statement is exited. If (statement 1) is false, (condition 2) is evaluated. If (condition 2) is true,(statement 2) gets executed and the case statement exited,and soon.If none of the conditions (condition 1),…, (condition n) are true,(statement n+1)is executed and the case statement is exited. The else clause is optional.

9.Input and output are done using the instructions read and write. No format is used to specify the sizeof input or output quantities.

10.There is only one type of procedure: Algorithm. An algorithm consists of a heading and a body. The heading takes the form

Algorithm Name(<parameter list>)

where Name is the name of the procedure and (<parameter list>) is a listing of the procedure parameters. The body has one or more (simple or compound) statements enclosed within braces { and }. An algorithm may or may not return any values. Simple variables to procedures are passed by value. Arrays and records are passed by reference. An array name or a record name is treated as a pointer to the respective datatype.

As an example,the following algorithm finds and returns the maximum
of n given numbers.

In this algorithm (named Max), A and n are procedure parameters. Result and i are local variables.

B. Recursive Algorithms

A recursive function is a function that is defined in terms of itself. Similarly, an algorithm is said to be recursive if the same algorithm is invoked in the body.

When is recursion an appropriate mechanism for algorithm exposition?One instance is when the problem it self is recursively defined. Factorial fits this category, as well as binomial coefficients, where