Algorithm of decorated graph, Data Structure & Algorithms

Assignment Help:

As we talked in class, a program with two integer variables is universal. Now, we consider a special form of four variableprograms. Let G = (V; E) be a directed graph, where V is a finite set of nodes, and E ⊆V X V be the set of (directed) edges (arcs). In particular, we identify a node as the initial node, and a node as the final node. Let x1; x2; x3; x4 be four non-negative integer variables. Further, we decorate each edge with one of the following instructions: (1 ≤i≤ 4)

xi:= xi + 1;

xi:= 0;

xi == c? (c is a non-negative integer)

The result is called a decorated graph (we still use G to denote it). The semantics of a decorated graph is straightforward. It executes from the initial node with x1; x2; x3; x4 being 0, then walks along the graph. G can walk an edge (v, v') if all of the following conditions are satisfied: for each 1 ≤i≤4,

  • if the edge is decorated with instruction xi:= xi + 1 for some i, the new value of xi is one more than the old value, and all the other xj(j ≠i) is unchanged.
  • if the edge is decorated with instruction xi:= 0, the new value of xi is set to 0, and all the other xj (j ≠i) is unchanged.
  • if the edge is decorated with instruction xi == c?, the value of xi must be c.

If at a node, G has more than one edge that can be walked, then G non-deterministically chooses one. If at a node G has no edge that can be walked, then G crashes (i.e., do not walk any further). We say that a decorated graph G is terminating if G can walk from an initial node to a final node and at the final node the values of x1; x2; x3; x4 satisfy the following constraint:

x1 = x2 = x3 = x4:

Show me an algorithm that answers (yes/no) whether G is terminating or not. (To correct a common misunderstanding, I shall point out that a walk could be arbitrarily long even though there are only 10 nodes in the graph! So, don't even try depth/breadth first search.)


Related Discussions:- Algorithm of decorated graph

What is efficiency of algorithm, What is Efficiency of algorithm? Effic...

What is Efficiency of algorithm? Efficiency of an algorithm can be precisely explained and investigated with mathematical rigor.  There are two types of algorithm efficiency

A linear list of elements in which deletion can be done, A linear list of e...

A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is called as a   Queue.

What is diffuse illumination, Diffuse Illumination Diffuse illuminatio...

Diffuse Illumination Diffuse illumination means light that comes from all directions not from one particular source. Think about the light of a grey cloudy day as compared to

Polynomials, Polynomials like  5x 4    +  2x 3    +  7x 2     +  10x  -  8...

Polynomials like  5x 4    +  2x 3    +  7x 2     +  10x  -  8  can  be  represented by using arrays. Arithmetic operations such as addition & multiplication of polynomials are com

Explain the interfaces in ruby, Explain the Interfaces in Ruby Recall...

Explain the Interfaces in Ruby Recall that in object-oriented programming, an interface is a collection of abstract operations that cannot be instantiated. Even though Ruby i

Explain the stack, QUESTION Explain the following data structures: ...

QUESTION Explain the following data structures: (a) List (b) Stack (c) Queues Note : your explanation should consist of the definition, operations and examples.

Trees, What is AVL Tree? Describe the method of Deletion of a node from and...

What is AVL Tree? Describe the method of Deletion of a node from and AVL Tree ?

Array implementation of a queue, Since the stack is list of elements, the q...

Since the stack is list of elements, the queue is also a list of elements. The stack & the queue differ just in the position where the elements may be added or deleted. Similar to

Sorted list using binary search technique, Write an algorithm for searching...

Write an algorithm for searching a key from a sorted list using binary search technique 1.   if (low > high) 2.     return (-1) 3.    mid = (low +high)/2; 4    .if ( X

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd