Question

Design and Analysis of algorithm - -- pseudo code

Write a program that, for a given graph, outputs:

a. vertices of each connected component

b. its cycle or a message that the graph is acyclic

Answer 1

ALGORITHM: The algorithm was the first time proposed a Persian mathematician Al-Chwarizmi in 825 AD. According to the web star dictionary, the algorithm is a special method to represent the procedure to solve the given problem.

OR

An Algorithm is any well-defined computational procedure that takes some value or set of values as input and produces a set of values or some value as output. Thus algorithm is a sequence of computational steps that transforms the input into the output.

Formal Definition:

An Algorithm is a finite set of instructions that, if followed, accomplishes a particular task. In addition, all algorithms should satisfy the following criteria.

1. Input. Zero or more quantities are externally supplied.

2. Output. At least one quantity is produced.

3. Definiteness. Each instruction is clear and unambiguous.

4. Finiteness. If we trace out the instructions of an algorithm, then for all cases, the algorithm terminates after a finite number of steps.

5. Effectiveness. Every instruction must very basic so that it can be carried out, in principle, by a person using only a pencil & paper.

Areas of study of Algorithm:

• How to device or design an algorithm– It includes the study of various design techniques and helps in writing algorithms using the existing design techniques like divide and conquer.
• How to validate an algorithm– After the algorithm is written it is necessary to check the correctness of the algorithm i.e for each input correct output is produced, known as algorithm validation. The second phase is writing a program known as program proving or program verification.
• How to analysis an algorithm–It is known as analysis of algorithms or performance analysis, refers to the task of calculating time and space complexity of the algorithm.
• How to test a program – It consists of two phases . 1. debugging is detection and correction of errors. 2. Profiling or performance measurement is the actual amount of time required by the program to compute the result.

Algorithm Specification:

The algorithm can be described in three ways.

1. Natural language like English:

2. Graphic representation called flowchart:

This method will work well when the algorithm is small& simple.

3. Pseudo-code Method:

In this method, we should typically describe algorithms as the program, which resembles language like Pascal &algol.

Pseudo-Code for writing Algorithms:

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

2. Blocks are indicated with matching braces {and}.

3. An identifier begins with a letter. The data types of variables are not explicitly declared.

4. Compound data types can be formed with records.

Here is an example,

Node. Record

{

data type – 1 data-1; .

datatype – n data – n;

node * link;

}

Here link is a pointer to the record type node. Individual data items of a record can be accessed with -> and period.

5. The assignment of values to variables is done using the assignment statement.

<Variable>:= <expression>;

6. There are two Boolean values TRUE and FALSE.

Logical Operators AND, OR, NOT

Relational Operators < ,<=,>,>=, =, !=

7. The following looping statements are employed.

For, while and repeat-until

While Loop:

While < condition >do{. . }

For Loop:

For variable: = value-1 to value-2 step step do { . . }

One step is a keyword, another Step is used for increment or decrement.

Performance Analysis.

There are many criteria to judge an algorithm.

– Is it correct?

– Is it readable?

– How it works

Performance evaluation can be divided into two major phases.

1. Performance Analysis (machine independent)

– space complexity: The space complexity of an algorithm is the amount of memory it needs to run for completion.

– time complexity: The time complexity of an algorithm is the amount of computer time it needs to run to completion.

2.Performance Measurement (machine-dependent).

Space Complexity:

The Space Complexity of any algorithm P is given by S(P)=C+SP(I), C is constant.

1.Fixed Space Requirements (C)

Independent of the characteristics of the inputs and outputs

– It includes instruction space

– space for simple variables, fixed-size structured variable, constants

2. Variable Space Requirements (SP(I)) depend on the instance characteristic I

– number, size, values of inputs and outputs associated with I

– recursive stack space, formal parameters, local variables, return address

b)

#include <iostream>
#include <vector>
using namespace std;

// data structure to store graph edges
struct Edge {
   int src, dest;
};

// class to represent a graph object
class Graph
{
public:
   // construct a vector of vectors to represent an adjacency list
   vector<vector<int>> adjList;

   // Graph Constructor
   Graph(vector<Edge> const &edges, int N)
   {
       // resize the vector to N elements of type vector<int>
       adjList.resize(N);

       // add edges to the Directed graph
       for (auto &edge: edges)
       {
           adjList[edge.src].push_back(edge.dest);
       }
   }
};

// Perform DFS on graph and set departure time of all
// vertices of the graph
int DFS(Graph const &graph, int v, vector<bool>
   &discovered, vector<int> &departure, int& time)
{
   // mark current node as discovered
   discovered[v] = true;

   // do for every edge (v -> u)
   for (int u : graph.adjList[v])
   {
       // u is not discovered
       if (!discovered[u])
           DFS(graph, u, discovered, departure, time);
   }

   // ready to backtrack
   // set departure time of vertex v
   departure[v] = time++;
}

// returns true if given directed graph is DAG  
bool isDAG(Graph const& graph, int N)
{
   // stores vertex is discovered or not
   vector<bool> discovered(N);

   // stores departure time of a vertex in DFS
   vector<int> departure(N);

   int time = 0;

   // Do DFS traversal from all undiscovered vertices
   // to visit all connected components of graph
   for (int i = 0; i < N; i++)
       if (discovered[i] == false)
           DFS(graph, i, discovered, departure, time);

   // check if given directed graph is DAG or not      
   for (int u = 0; u < N; u++)
   {
       // check if (u, v) forms a back-edge.
       for (int v : graph.adjList[u])
       {
           // If departure time of vertex v is greater
           // than equal to departure time of u, then
           // they form a back edge
      
           // Note that departure[u] will be equal to
           // departure[v] only if u = v i.e vertex
           // contain an edge to itself
           if (departure[u] <= departure[v])
               return false;
       }
   }

   // no back edges
   return true;
}

// Check if given digraph is a DAG (Directed Acyclic Graph) or not
int main()
{
   // vector of graph edges as per above diagram
   vector<Edge> edges =
   {
       {0, 1}, {0, 3}, {1, 2}, {1, 3}, {3, 2}, {3, 4},
       {3, 0}, {5, 6}, {6, 3}
   };

   // Number of nodes in the graph
   int N = 7;

   // create a graph from given edges
   Graph graph(edges, N);

   // check if given directed graph is DAG or not
   if (isDAG(graph, N))
       cout << "Graph is DAG";
   else
       cout << "Graph is not DAG";

   return 0;
}