Back to Course


0% Complete
0/82 Steps
  1. Getting Started with Algorithm
    What is an Algorithm?
  2. Characteristics of Algorithm
    1 Topic
  3. Analysis Framework
  4. Performance Analysis
    3 Topics
  5. Mathematical Analysis
    2 Topics
  6. Sorting Algorithm
    Sorting Algorithm
    10 Topics
  7. Searching Algorithm
    6 Topics
  8. Fundamental of Data Structures
  9. Queues
  10. Graphs
  11. Trees
  12. Sets
  13. Dictionaries
  14. Divide and Conquer
    General Method
  15. Binary Search
  16. Recurrence Equation for Divide and Conquer
  17. Finding the Maximum and Minimum
  18. Merge Sort
  19. Quick Sort
  20. Stassen’s Matrix Multiplication
  21. Advantages and Disadvantages of Divide and Conquer
  22. Decrease and Conquer
    Insertion Sort
  23. Topological Sort
  24. Greedy Method
    General Method
  25. Coin Change Problem
  26. Knapsack Problem
  27. Job Sequencing with Deadlines
  28. Minimum Cost Spanning Trees
    2 Topics
  29. Single Source Shortest Paths
    1 Topic
  30. Optimal Tree Problem
    1 Topic
  31. Transform and Conquer Approach
    1 Topic
  32. Dynamic Programming
    General Method with Examples
  33. Multistage Graphs
  34. Transitive Closure
    1 Topic
  35. All Pairs Shortest Paths
    6 Topics
  36. Backtracking
    General Method
  37. N-Queens Problem
  38. Sum of Subsets problem
  39. Graph Coloring
  40. Hamiltonian Cycles
  41. Branch and Bound
    2 Topics
  42. 0/1 Knapsack problem
    2 Topics
  43. NP-Complete and NP-Hard Problems
    1 Topic
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:

KodNest Capture1

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


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

KodNest Capture2

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:

KodNest Capture3 1

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:

KodNest Capture4 1

A repeat-until statement is constructed as follows:

KodNest Capture5 1

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:

KodNest Capture6

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.

KodNest Capture7

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

KodNest Capture8

New Report