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.

Explain Test-Driven Development Cycle?

Test driven development or TDD is considered to one of the most effective as well as efficient software development methodology or process that is often cited under the category of the agile software development processes.

The term “test driven development” is self justifying as one make out from the term itself that it is driven by the tests. Actually, the test driven development process is wholly based up on the repetition process of the several development cycles that are shorter than the usual development cycles. 

This whole article is dedicated to the discussion regarding the test driven development cycle. 

What are the steps in TDD process?

Test driven development process involves the below mentioned steps:

1. First step involves the creation of an automatic test case that is failing and defines a new function or some desired improvement in the code.

2. Second step involves the production of code which can pass the test.

3. Third and the final step involves the re-factoring of the new code in order to meet the prescribed standards.

This development strategy or process was introduced in the year of 2003 by Kent beck. The first programming concepts of the extreme programming or XP are considered to be related to the concepts of the test driven development to some extent.

But, nowadays the test driven development has been observed to be an individual development methodology with its own rules and independent procedures. The test driven development process has proved to be successful in improving and debugging legacy code that has been developed using the older development techniques. 

We all know that every development process has its own requirements so here in this the requirements are the automated unit tests that provide a definition of the code requirements and create the associated code themselves. 

Test Driven Development Cycle

Now let us describe the test driven development cycle in detail and sequence:

1. Adding of a test: 

- In test driven development, for every feature to be added, first a test is written that is inevitably expected to fail since it is written before the actual implementation of the features. 

- If the test does not fail, then there are two probabilities: the test is either wrongly formulated or the feature for which the test has been created already exists. 

- The test should be written with utmost understanding of the specifications and requirements which can be achieved from the use cases and user stories. 

- An already existing test can also be modified.

- Writing unit tests before the implementation of the feature helps the software developer or program focus up on the requirements before the actual code is written. 

- This feature of the test driven development differentiates it from the others and leaves a subtle and important effect.

2. Execution of all the tests and check if they fail: 

- This step involves the validation of the test harnesses for their proper working.

- This is done to ensure that no test passes mistakenly without requirement of new code. 

- The test itself is also tested but in the negative so that all the possibilities of passing of the new test are ruled out making it worthless.

3. Production of code: 

- This step involves the production of code by virtue of which the test will pass.

- The code even if its no perfect is accepted since later it can be improved.

4. Execution of the automated tests: 

After all the tests have passed, the developer can be confident that the code is perfect.

5. Refactorization of the code: 

This involves clean up drive of the code and the tests can be re- executed in order to ensure that the existing code is not being damaged.

6. Repetition: 

This involves repetitions of the whole development cycle in order to improve functionality. 

What is meant by application testing cycle?

An application testing cycle states what all the activities are to be carried out in the testing. Although different organizations might be following different procedures or test plans for testing the software applications, they all follow the same application testing cycle. They draft their plans based on a common testing cycle. This is basically done to maintain the standards of testing.

APPLICATION TESTING CYCLE
The application testing cycle that we are going to discuss here is a typical test cycle for the organizations that base their application’s development on water fall model.

1. Analysis of Requirements
- Since this is the first phase in the development cycle of an application, the testing should begin from here itself.
- After the identification of the requirements of the application, the testers and developers together determine what all the requirements should be tested.

2. Drawing up the Test Plan
- The whole testing is planned and it includes the test plan, the test strategy and test environment creation.
- Testing is a very complex process.
- Therefore a plan is needed so that there is no messing around.
- The test plans are usually of a high level.

3. Development of Test
- A procedure for carrying out the test is designed.
- Other things like test cases, test scenarios, test scripts and test input data are also made ready.
- This phase also includes the verification of the test cases.
- The automated test cases are scripted.
- This phase is commonly called as the construction and the verification phase.

4. Execution of the Test
- The test cases are executed by the tester as per the test plan and any error or bug found is reported and documented at the same time.

5. Reporting of Test
- A final report on the carried out test is prepared which contains all the observations made and also the testing details.
- This report is submitted to the development team.

6. Analysis of the Test Results
- The results of the test are then analyzed by the whole development team in the presence of the client.
- The client and the development team together decide which issues are to be resolved and which are to be rejected.
- Risks to the application are identified and a risk assessment is prepared.
- Features and functionalities of the application software are validated.

7. Retesting of the Defects
- After resolving all the issues stated by the client, they are once again reviewed by the development if in case they have caused some other bug.
- This is commonly called as resolution testing.

8. Regression Testing/Final Testing
- This is the last but one phase of the application testing cycle and very important.
- This testing is done after making all the major as well as minor fixes in the application in order to ensure that the application is still working properly.
- If any changes are made to the application, at the same time the documentation is also updated.
- The verification of the application is done under the production conditions.
- Metrics of the test efforts are also prepared in this phase.

9. Closure of the Test
- As we know that for every test exit criteria is defined.
- When the test meets these criteria the testing is declared close and all the reports and documentations are archived.
- These archived reports are used for future reference.
- A line of attack is identified and used to prevent such similar bugs and errors in the future applications.
- The whole testing process is evaluated and ways are sort to make it better.
- The test environment is cleaned up and the restoring of all the testing machines and tools to the baseline is also done.

What is Adaptive Software Development (ASD)? What are three phases of ASD?

Adpative Software Development (ASD) is a method for the creation and development of software systems. It focuses on rapid creation and evolution of software systems. ASD is a pat of rapid application development.

Adaptive software development life cycle is mission focused, feature based, iterative, time-boxed, risk driven, and change tolerant. In adaptive software development, the developer has a basic idea in mind and they g to work. The focus is in the computer code.

In ASD, there are no pre-planned steps. The software is made very quickly. New versions can come out very quickly as the development cycle is very short. The structure of adpative software development and rapid application development are similar, difference lies in the fact that:
- adaptive software development does not allow the time when the project is finished, rapid application development does.
- adaptive software development does not have a real end point whereas rapid applicatio development allows the end of project.

Adaptive Software Development life cycle comprises of three phases:
- Speculation
- Collaboration
- Learning

In speculation, user requirements are understood and an adaptive cycle planning is conducted. It depends on bug and user reports.
Effective collaboration with customer is very important. Communication, teamwork, individual creativity are a part of effective collaboration. The individual developers combine their portions of work.
Learning cycles are based on the short iterations with design, build and testing. ASD teams can learn through focus groups, formal technical reviews and postmortems.

Articles on the product development cycle

These are a series of articles on the product development cycle, meant for a product development cycle where either a new product or a new version is being developed. These articles are meant to illustrate different stages of the development cycle although some of the stages could be overlapping:

Requirements Gathering (link)

Requirements Gathering contd .. (link)

Requirements Planning - Template (link)

Planning a patch or minor release (link)

Rolling out the patch (link)

What is a minor / dot release ? (link)

Planning a minor / dot release - Challenges (link)

Actual Kickoff of Development Effort (link)

PreRelease / Beta planning (link)

Planning for metrics (link)

To be contd ..

Stages of a complete test cycle

People who are involved in the business of software testing know many parts of the testing process, but there are few people who have covered all the stages involved from the time of getting the project requirements, to the last stages of testing. Here is a timeline of the steps involved in this process:

• Requirements Phase: Get the requirements, along with the functional design, the internal design specifications
• Resourcing estimation: Obtain budget and schedule requirements
• Get into details of the project-related personnel and their responsibilities and the reporting requirements
• Work out the required processes (such as release processes, change processes, etc.). Defining such processes can typically take a lot of time.
• Identify application's higher-risk aspects, set priorities, and determine scope and limitations of tests
• Test methods: This is the time to plan and determine test approaches and methods - unit, integration, functional, system, load, usability tests, etc., the whole breakup of the types of tests to be done
• Determine test environment requirements (hardware, software, communications, etc.). These are critical to determine because the testing success depends on getting a good approximation of the test environment
• Determine testware requirements (record/playback tools, coverage analyzers, test tracking, problem/bug tracking, etc.). In many cases, a complete coverage of these tools is not done.
• Determine test input data requirements. This can be a fairly intensive task, and needs to be thought through carefully.
• People assignment: This is stage where for the project, task identification, those responsible for tasks, and labor requirements all need to be calculated.
• Find out schedule estimates, timelines, milestones. Absolutely critical, since these determine the overall testing schedule along with resource needs.
• Determine input equivalence classes, boundary value analyses, error classes
• Prepare test plan document and have needed reviews/approvals. A test plan document encapsulates the entire testing proposal and needs to be properly reviewed for completeness.
• Once the test plan is done and accepted, the next step is to write test cases
• Have needed reviews/inspections/approvals of test cases. This may include reviews by the development team as well.
• Prepare test environment and testware, obtain needed user manuals/reference documents/configuration guides/installation guides, set up test tracking processes, set up logging and archiving processes, set up or obtain test input data
• Obtain and install software releases. If a daily build is available, the smoke testing regime for build acceptance needs to be brought in.
• Perform tests. The actual phase where you start to see the results of all the previous efforts.
• Evaluate and report results
• Track problems/bugs and fixes. This phase can take up a substantial portion of the overall project time.
• Retest as needed, including regression testing
• Maintain and update test plans, test cases, test environment, and testware through life cycle