What is a spanning tree?

Spanning tree is an important field in both mathematics and computer science. Mathematically, we define a spanning tree T of an un-directed and connected graph G as a tree consisting of all the vertices and all or some edges of the graph G.

- Spanning tree is defined as a selection of some edges from G forming a tree such that every vertex is spanned by it. 

- This means that every vertex of graph G is present in the spanning tree but there are no loops or cycles. 

- Also, every bridge of the given graph must be present in its spanning tree. 

- We can even say that a maximal set of the graph G’s edges containing no cycle or a minimal set of the graph G’s vertices forms a spanning tree. 

- In the field of graph theory, it is common finding the MST or the minimum spanning tree for some weighted graph. 

- There are a number of other optimization problems that require using the minimum spanning trees and other types of spanning trees. 

The other types of spanning trees include the following:

Ø  Maximum spanning tree

Ø  An MST spanning at least k number of vertices.

Ø  An MST having at the most k number of edges per vertex i.e., the degree constrained spanning tree.

Ø  Spanning tree having the largest no. of leaves (this type of spanning tree bears a close relation with the “smallest connected dominating set”).

Ø  Spanning tree with the fewest number of leaves (this spanning tree bears a close relation with the “Hamiltonian path problem”).

Ø  Minimum diameter spanning tree.

Ø  Minimum dilation spanning tree.

- One characteristic property of the spanning trees is that they do not have any cycles. 

- This also means that if you add just an edge to the tree, a cycle will be created. 

- We call this cycle as the fundamental cycle. 

- For each edge in the spanning there exists a distinct fundamental cycle and therefore there arises a one – to – one correspondence among the edges that are not present and the fundamental cycles. 

- For a graph G that is connected and has V vertices, there are V-1 edges in its spanning tree. 

- Therefore, for a general graph composed of E edges, its spanning tree will have E-V+1 number of fundamental cycles.

- For the cycle space of a given spanning tree these fundamental cycles are used. 

- The notion of the fundamental cut set as well as of the fundamental cycle forms a dual.  

- If we delete even one edge from the spanning tree, two disjoint sets will be formed of the vertices. 

- The set of the edges that if taken out from the graph G partitioning the vertices in to same disjoint sets is defined as the fundamental cut set. 

- For a given graph G there are V-1 fundamental cut sets i.e., one corresponding to each spanning tree edge. 

- The fact that the edges of the cycles that do not appear in the spanning tree but only in the cut sets of the edges can be used to establish the relationship between the cycles and the cut sets.

What is Spanning Forest?

- The sub-graph generalizing the spanning tree concept is called the spanning forest. 

- A spanning forest can be defined as a sub-graph consisting in each of the connected component a spanning tree of the graph G or we can call it a maximal cycle free sub graph.

- For counting the number of spanning trees for a complete graph the formula used is known as the cayley’s formula.

What are types of artificial neural networks?

In this article we discuss the types of artificial neural networks. These models simulate the real life biological system of nervous system.

1. Feed forward neural network: 

- This is the simplest type of neural network that has been ever devised. 

- In these networks the information flow is unidirectional; therefore the data moves only in forward direction. 

- From input nodes data flows to the output nodes via hidden nodes (if there are any). 

- In this model there are no loops or cycles. 

- Different types of units can be used for constructing feed forward networks for example, McCulloch – pitts neurons.

- Continuous neurons are used in error back propagation along with the sigmoidal activation.

2. Radial basis function network: 

- For interpolating in a multi – dimensional space radial basis functions are the most powerful tools. 

- These functions can be built in to criterion of distance with respect to some center.

- These functions can be applied in the neural networks. 

- In these networks, sigmoidal hidden layer transfer characteristic can be replaced by these functions.

3. Kohonen self–organization network: 

- Un–supervised learning is performed with the help of self – organizing map or SOM. 

- This map was an invention of Teuvo Kohonen.

- Few neurons learn mapping points in the input space that could not coordinate in the output space. 

- The dimensions and topology of the input space can be different from those of the output space. SOM makes an attempt for preserving these.

4. Learning vector quantization or LVQ: 

- This can also be considered as neural network architecture. 

- This one also was a suggestion of Teuvo Kohonen.  

- In these prototypical representatives are parameterized along with two important things namely, a classification scheme based - up on distance and a distance measure.

5. Recurrent neural network: 

- These networks are somewhat contrary to the feed forward networks. 

- They offer a bi–directional flow of data.

- On a feed forward network data is propagated linearly from input to output. 

- Data from later stages of processing is also transferred to its earlier stages by this network. 

- Sometimes these also double up as the general sequence processors. 

- Recurrent neural networks have a number of types as mentioned below:

Ø  Fully recurrent network

Ø  Hopfield network

Ø  Boltzmann machine

Ø  Simple recurrent networks

Ø  Echo state network

Ø  Long short term memory network

Ø  Bi – directional RNN

Ø  Hierarchical RNN

Ø  Stochastic neural networks

6. Modular neural networks: 

- As per the studies have shown that human brain works actually as a collection of several small networks rather than as just one huge network, this ultimately helped in realizing the modular neural networks where smaller networks cooperate in solving a problem. 

- Modular networks are also of many types such as:

Ø  Committee of machines: Different networks that work together on a given problem are collectively termed as the committee of machines. The result achieved through this kind of networking is quite better than what is achieved with the others. The result is highly stabilized.

Ø  Associative neural network or ASNN: This is an extension of the previous one. And extends a little beyond the weighted average of various models. This one is a combined form of the k- nearest neighbor technique (kNN) and the feed forward neural networks. Its memory is coincident with that of the training set.

7. Physical neural network: 

- It consists of some resistance material that is electrically adjustable and capable of simulating the artificial synapses.

There are other types of ANNs that do not fall in any of the above categories:

Ø  Holographic associative memory

Ø  Instantaneously trained networks

Ø  Spiking neural networks

Ø  Dynamic neural networks

Ø  Cascading neural networks

Ø  Neuro – fuzzy networks

Ø  Compositional pattern producing networks

Ø  One – shot associative memory

What is the need of Agile Process Improvement?

It is commonly seen that a number of change projects are designed and published but none of actually goes into implementation. Most of the time is wasted in writing and publishing them. This approach usually fails. We should stop working with this methodology and develop a new one. Below mentioned are some common scenarios in the modern business:

1. Developing a stronger project
2. Changing the people working on it.
3. Threatening that project with termination
4. Appointment of a committee that would analyze the project
5. Taking examples from other organizations to see how they manage to do it.
6. Getting down to a dead project
7. Tagging a dead project as still worth of achieving something.
8. Putting many different projects together so as increase the benefit.
9. Additional training

-Drops in the delivery of the normal work always follow a change. 

-Big change projects are either dropped or rejected.

-It all happens because the changes introduced by such projects are mandatory to be followed.

-This threatens the normal functioning of the organization. 

-So, the organization is eventually compelled to kill the whole process and start with the old way of work again. 

-Instead of following this approach, a step by step process improvement can be followed that is nothing but the agile process improvement. 

Now you must be convinced why agile process improvement is actually needed. 

- The changes needs to be adaptive then only the process will be balanced. 

- An example is the CMMI maturity level. It takes 2 years approx. for completion and brings in the following:

1. Restructuring
2. New competitors
3. New products

-Only agile methods make these changes adaptive in nature.

-The change cycles when followed systematically produce results in every 2 – 6 weeks.

-Thus, your organization’s workload and improvement stay perfectly balanced. -The early identification of the issues becomes possible for the organizations thus giving you it a chance to be resolved early. 

-By and by the organization learns to tackle the problems and how to improve work.

-At the end it is able to adapt to the every changing needs of the business.

-The responsibility of the deployment and evaluation of the improvement is taken by the PPQA. 

-Whole process is implemented in 4 sprints:

1. Prototyping
2. Piloting
3. Deploying
4. Evaluating

-A large participation and leadership is required for these changes to take place.

-Some other agile techniques along with scrum can also be used in SPI.

-We can have the improvements continuously integrated in to the way the organization works. 

-The way of working can also be re-factored including assets and definitions by having an step by step integration of the improvements.

-Pair work can be carried out on improvements. 

-A collective ownership can be created for the organization. 

-Evaluations and pilots can be used for testing purpose. 

-In order to succeed with the sprints is important that only simple solutions should be developed. 

-An organization can write the coaching material with the help of the work description standards.

-This sprint technique helps the organization to strike a balance between the improvement and the normal workload. 

-In agile process improvement simple solutions are preferred over the complex ones.

-Here, the status quo and the vision are developed using the CMMI and SCAMPI. 

-Status quo and vision are necessary for the beginning of the software process improvement.

-SPI when conducted properly produces useful work otherwise unnecessary documentation has to be produced.

-An improvement in the process is an improvement in the work. 

-Improving work is what that is preferred by people. 

What is meant by evolutionary and adaptive development?

There are so many models designed for the development of the software systems or applications and a good tester needs to have knowledge of every software development model in order to decide for the best development model for building his/ her project. 

Types of Software Development Models

There are so many software development models available today like:

     1. Waterfall development model

     2. Spiral development model

     3. Iterative and incremental development model

     4. Agile development model

     5. Code and fix development model

     6. CMMI

     7. ISO 9000

     8. B – methods

     9. Petri nets

    10. Automated theorem proving

    11. RAISE

    12. VDM

    13. Z notation

    14. Chaos model

    15. Extreme programming

    16. ICONIX

    17. Incremental funding technology

    18. Software prototyping

    19. Rational unified process

    20. V model

    21. Service oriented modelling

    22. Evolutionary development model

    23. Adaptive development model

   

     This article has been written to discuss about the last two development models i.e., the evolutionary model and the adaptive model of software development. The water fall model is viable even today for the software products whose features do not change with time. 

     But what about the software applications whose features have to be redefined every now and then?? 

     The waterfall model does not hold to be appropriate. 

   

     

About Evolutionary Development Model

     - Under the evolutionary development model, the whole development cycle is broken down in to smaller waterfall models which can be incremented and the software product is accessible by the users when each cycle ends. 

     - Based on this product the users provide their feedback based on which the development plan for the next stage is created.

     - These incremental cycles can take up to 3 – 4 weeks and continue till the shipping of the software product. 

     - The business results as well as the internal and marketing operations are also benefited by the evolutionary development model if it is performed well. 

     - The best benefit of the business being a huge reduction in the associated risks like:

1. Missing scheduled deadlines
2. Wrong set of features
3. Poor quality
4. Unusable products and so on.

- Since the whole development process is broken down in to smaller ones, these risks become easily manageable. 

- Apart from this the evolutionary development helps in reducing the cost budget by the means of disciplined and structured avenue for doing the experimentation.

- The evolutionary development model has also been praised for the below mentioned matters:

1. Production of software systems and applications that fit the market requirements and needs of the users better.
2. Early deliveries in the marketing development.
3. Facilitation of the demonstration and the documentation.

With the constant feedback from the users in an evolutionary development model the team members are constantly motivated and encouraged. Now let us move to the other development model i.e., the adaptive development model that we had to discuss. 

About Adaptive Development Model

- In contrast to the evolutionary development model, the adaptive development model consists of shorter iterations, frequent releases of the working and useful softwares and continuous integration. - For an adaptive software development model the agile iterative approach is followed however no perspective set of rules has been defined. 

- Instead a couple of practices and principles have been identified.

- The adaptive development model has been inherited from the RAP or rapid application development. 

- This model is another attempt to replace the waterfall cycle with a development process that consists of speculative, collaborative and learning cycles.

- ASD is just the development process and is quite dynamic so as to provide adaptation to the state of project emergent in need. 

- Below mentioned are some of its characteristics:

1. Mission focused
2. Feature based
3. Iterative
4. Time boxed
5. Risk driven
6. Change tolerant