Characteristics of an Algorithm

While designing an algorithm as a solution to a given problem, we must take care of the following five important characteristics of an algorithm:

1. Finiteness

An algorithm must terminate after a finite number of steps and further each step must be executable in finite amount of time. In order to establish a sequence of steps as an algorithm, it should be established that it terminates (in finite number of steps) on all allowed inputs.

2. Definiteness (no ambiguity)

Each step of an algorithm must be precisely defined; the action to be carried out must be rigorously and unambiguously specified for each case. Through the next example, we show how an instruction may not be definite.
Example: Method which is effective (to be explained later) but not definite.
The following is a program fragment for the example method:
x ← 1
Toss a coin,
If the result is Head then x ←3 else x ← 4
{In the above, the symbol ‘←’ denotes that the value on its R.H.S is assigned to the variable on its L.H.S. Detailed discussion under (i) of Section 1.6.1}
All the steps, like tossing the coin etc., can be (effectively) carried out. However, the method is not definite, as two different executions may yield different outputs.

3. Inputs

An algorithm has zero or more, but only finite, number of inputs.
Examples of algorithms requiring zero inputs:

1. Print the largest integer, say MAX, representable in the computer system being used.
2. Print the ASCII code of each of the letter in the alphabet of the computer system being used.
3. Find the sum S of the form 1+2+3+…, where S is the largest integer less than or equal to MAX defined in Example (i) above.

4. Output

An algorithm has one or more outputs. The requirement of at least one output is obviously essential, because, otherwise we cannot know the answer/solution provided by the algorithm.

The outputs have specific relation to the inputs, where the relation is defined by the algorithm.

5. Effectiveness

An algorithm should be effective. This means that each of the operation to be performed in an algorithm must be sufficiently basic that it can, in principle, be done exactly and in a finite length of time, by a person using pencil and paper. It may be noted that the ‘FINITENESS’ condition is a special case of ‘EFFECTIVENESS’. If a sequence of steps is not finite, then it cannot be effective also.

Read More

Difference between Problems and Instances

The difference between the two concepts viz., ‘problem’ and ‘instance’, can be understood in terms of the following example. An instance of a problem is also called a question. We know that the roots of a general quadratic equation

 (1)

are given by the equation

 (2)

where a, b, c may be any real numbers except the restriction that a ≠ 0.

Now, if we take a = 3, b = 4 and c = 1, we get the particular equation

 (3)

Using (2), the roots of (3) are given by

With reference to the above discussion, the issue of finding roots of the general quadratic equation ax2 + bx + c = 0, with a ≠ 0 is called a problem, whereas the issue
of finding the roots of the particular equation

is called a question or an instance of the (general) problem.

In general, a problem may have a large, possibly infinite, number of instances. The above-mentioned problem of finding the roots of the quadratic equation

with a ≠ 0, b and c as real numbers, has infinitely many instances, each obtained by giving some specific real values to a, b and c, taking care that the value assigned to a is not zero. However, all problems may not be of generic nature. For some problems, there may be only one instance/question corresponding to each of the problems. For example, the problem of finding out the largest integer that can be stored or can be arithmetically operated on, in a given computer, is a single-instance problem. Many of the interesting problems like the ones given below, are just single-instance problems.

Read More

Euclid’s Algorithm for Finding G.C.D. of two Natural Numbers m & n

E1. {Find Remainder}. Divide m by n and let r be the (new) remainder {r have 0≤r<n}
E2. {Is r zero?} If r = 0, the algorithm terminates and n is the answer. Otherwise,
E3. {Interchange}. Let the new value of m be the current value of n and the new value of n be the current value of r. Go back to Step E1.

The termination of the above method is guaranteed, as m and n must reduce in each iteration and r must become zero in finite number of repetitions of steps E1, E2 and E3.

The great Greek mathematician Euclid sometimes between fourth and third century BC, at least knew and may be the first to suggest, the above algorithm. The algorithm is considered as among the first non-trivial algorithms. However, the word ‘algorithm’ itself came into usage quite late. The word is derived from the name of the Persian mathematician Mohammed al-Khwarizmi who lived during the ninth century A.D. The word ‘al-khowarizmi’ when written in Latin became ‘Algorismus’, from which ‘algorithm’ is a small step away.

In order to familiarise ourselves with the notation usually used to express algorithms, next, we express the Euclid’s Algorithm in a pseudo-code notation which is closer to a programming language.

Algorithm GCD-Euclid (m, n)

{This algorithm computes the greatest common divisor of two given positive integers}
begin {of algorithm}
while n ≠ 0 do
begin {of while loop}
r ← m mod n;
{a new variable is used to store the remainder which is obtained by dividing m by n, with 0≤ r < m}
m ←n;
{the value of n is assigned as new value of m; but at this stage value of n remains unchanged}
n← r;
{the value of r becomes the new value of n and the value of r remains unchanged}
end {of while loop}
return (n).
end; {of algorithm}

Read More

Notation for expressing algorithms

This issue of notation for representations of algorithms will be discussed in some detail, later. However, mainly, some combinations of mathematical symbols, English phrases and sentences, and some sort of pseudo-high-level language notations, shall be used for the purpose.

Particularly, the symbol ‘←’ is used for assignment. For example, x←y + 3, means that 3 is added to the value of the variable y and the resultant value becomes the new value of the variable x. However, the value of y remains unchanged.

If in an algorithm, more than one variables are required to store values of the same type, notation of the form A[1..n] is used to denote n variables A[1], A[2], … A[n].

In general, for the integers m, n with m ≤ n, A [m..n] is used to denote the variables A[m], A[m+1], …, A[n]. However, we must note that another similar notation A[m, n] is used to indicate the element of the matrix (or twodimensional array) A, which is in mth row and nth column.

Role and Notation for Comments

The comments do not form that part of an algorithm, corresponding to which there is an (executable) action in the process. However, the comments help the human reader of the algorithm to better understand the algorithm. In different programming languages, there are different notations for incorporating comments in algorithms. We use the convention of putting comments between pair of braces, i.e., { } . The comments may be inserted at any place within an algorithm. For example, if an algorithm finds roots of a quadratic equation, then we may add the following comments, somewhere in the beginning of the algorithm, to tell what the algorithm does:

{this algorithm finds the roots of a quadratic equation in which the coefficient of x2 is assumed to be non-zero}.

Read More

Capability Maturity Models, Maturity Levels & their Key Process Areas

The process models are based on various software development phases whereas the capability models have an entirely different basis of development. They are based upon the capabilities of software. It was developed by Software Engineering Institute (SEI). In this model, significant emphasis is given to the techniques to improve the “software quality” and “process maturity”. In this model a strategy for improving Software process is devised. It is not concerned which life cycle mode is followed for development. SEI has laid guidelines regarding the capabilities an organization should have to reach different levels of process maturity. This approach evaluates the global effectiveness of a software company.

Maturity Levels

It defines five maturity levels as described below. Different organizations are certified for different levels based on the processes they follow.

Level 1 (Initial): At this maturity level, software is developed an ad hoc basis and no strategic approach is used for its development. The success of developed software entirely depends upon the skills of the team members. As no sound engineering approach is followed, the time and cost of the project are not critical issues. In Maturity Level 1 organizations, the software process is unpredictable, because if the developing team changes, the process will change. The testing of software is also very simple and accurate predictions regarding software quality are not possible.

SEI’s assessment indicates that the vast majority of software organizations are Level 1 organizations.

Level 2 (Repeatable): The organization satisfies all the requirements of level-1. At this level, basic project management policies and related procedures are established.

The institutions achieving this maturity level learn with experience of earlier projects and reutilize the successful practices in on-going projects. The effective process can be characterized as practiced, documented, implemented and trained. In this maturity level, the manager provides quick solutions to the problem encountered in software development and corrective action is immediately taken. Hence, the process of development is much disciplined in this maturity level. Thus, without measurement, sufficiently realistic estimates regarding cost, schedules and functionality are performed. The organizations of this maturity level have installed basic management controls.

Level 3 (Defined): The organization satisfies all the requirements of level-2. At this maturity level, the software development processes are well defined, managed and documented. Training is imparted to staff to gain the required knowledge. The standard practices are simply tailored to create new projects.

Level 4 (Managed): The organization satisfies all the requirements of level-3. At this level quantitative standards are set for software products and processes. The project analysis is done at integrated organizational level and collective database is created.

The performance is measured at integrated organization level. The Software development is performed with well defined instruments. The organization’s capability at Level 4 is “predictable” because projects control their products and processes to ensure their performance within quantitatively specified limits. The quality of software is high.

Level 5 (Optimizing): The organization satisfies all the requirements of level-4. This is last level. The organization at this maturity level is considered almost perfect. At this level, the entire organization continuously works for process improvement with the help of quantitative feedback obtained from lower level. The organization analyses its weakness and takes required corrective steps proactively to prevent the errors.

Based on the cost benefit analysis of new technologies, the organization changes their Software development processes.

Key Process Areas

The SEI has associated key process areas (KPAs) with each maturity level. The KPA is an indicative measurement of goodness of software engineering functions like project planning, requirements management, etc. The KPA consists of the following parameters:

Goals: Objectives to be achieved.
Commitments: The requirements that the organization should meet to ensure the claimed quality of product.
Abilities: The capabilities an organization has.
Activities: The specific tasks required to achieve KPA function.
Methods for varying implementation: It explains how the KPAs can be verified.

18 KPAs are defined by SEI and associated with different maturity levels. These are described below:

Level 1 KPAs: There is no key process area at Level 1.
Level 2 KPAs:

1. Software Project Planning: Gives concrete plans for software management.
2. Software Project Tracing & Oversight: Establish adequate visibility into actual process to enable the organization to take immediate corrective steps if Software performance deviates from plans.
3. Requirements Management: The requirements are well specified to develop a contract between developer and customer.
4. Software Subcontract Management: Select qualified software subcontractors and manage them effectively.
5. Software Quality Assurance (SQA): To Assure the quality of developed product.
6. Software Configuration Management (SCM): Establish & maintain integrity throughout the lifecycle of project.

Level 3 KPAs:

1. Organization Process Focus (OPF): The organizations responsibility is fixed for software process activities that improve the ultimate software process capability.
2. Training Program (TP): It imparts training to develop the skills and knowledge of organization staff.
3. Organization Process Definition (OPD): It develops a workable set of software process to enhance cumulative long term benefit of organization by improving process performance.
4. Integrated Software Management (ISM): The software management and software engineering activities are defined and a tailor made standard and software process suiting to organizations requirements is developed.
5. Software Product Engineering (SPE): Well defined software engineering activities are integrated to produce correct, consistent software products effectively and efficiently.
6. Inter group co-ordination (IC): To satisfy the customer’s needs effectively and efficiently, Software engineering groups are created. These groups participate actively with other groups.
7. Peer reviews (PR): They remove defects from software engineering work products.

Level 4 KPAs:

1. Quantitative Process Management (QP): It defines quantitative standards for software process.
2. Software Quality Management (SQM): It develops quantitative understanding of the quality of Software products and achieves specific quality goals.

Level 5 KPAs:

1. Defect Prevention (DP): It discovers the causes of defects and devises the techniques which prevent them from recurring.
2. Technology Change Management (TCM): It continuously upgrades itself according to new tools, methods and processes.
3. Process Change Management (PCM): It continually improves the software processes used in organization to improve software quality, increase productivity and decrease cycle time for product development.

Read More

Spiral Model - Software Development Models

This model can be considered as the model, which combines the strengths of various other models. Conventional software development processes do not take uncertainties into account. Important software projects have failed because of unforeseen risks.

The other models view the software process as a linear activity whereas this model considers it as a spiral process. This is made by representing the iterative development cycle as an expanding spiral.

The following are the primary activities in this model:

1. Finalizing Objective: The objectives are set for the particular phase of the project.
2. Risk Analysis: The risks are identified to the extent possible. They are analyzed and necessary steps are taken.
3. Development: Based on the risks that are identified, an SDLC model is selected and is followed.
4. Planning: At this point, the work done till this time is reviewed. Based on the review, a decision regarding whether to go through the loop of spiral again or not will be decided. If there is need to go, then planning is done accordingly.

In the spiral model, these phases are followed iteratively. The following figure depicts the Boehm’s Spiral Model (IEEE, 1988).

In this model Software development starts with lesser requirements specification, lesser risk analysis, etc. The radical dimension this model represents cumulative cost. The angular dimension represents progress made in completing the cycle.

The inner cycles of the spiral model represent early phases of requirements analysis and after prototyping of software, the requirements are refined.

In the spiral model, after each phase a review is performed regarding all products developed upto that point and plans are devised for the next cycle. This model is a realistic approach to the development of large scale software. It suggests a systematic approach according to classical life cycle, but incorporates it into iterative framework. It gives a direct consideration to technical risks. Thus, for high risk projects, this model is very useful. The risk analysis and validation steps eliminate errors in early phases of development.

Read More

Prototyping Model - Software Development Models

In Prototyping Model, a working model of actual software is developed initially. The prototype is just like sample software having lesser functional capabilities and low reliability and it does not undergo through the rigorous testing phase. Developing a working prototype in the first phase overcomes the disadvantage of the waterfall model where the reporting about serious errors is possible only after completion of software development.

The working prototype is given to the customer for operation. The customer, after its use, gives the feedback. Analyzing the feedback given by the customer, the developer refines, adds the requirements and prepares the final specification document. Once the prototype becomes operational, the actual product is developed using the normal waterfall model.

The prototype model has the following features:

1. It helps in determining user requirements more deeply.
2. At the time of actual product development, the customer feedback is available.
3. It does consider any types of risks at the initial level.

Read More

Iterative Enhancement Model - Software Development Models

Iterative Enhancement Model was developed to remove the shortcomings of waterfall model. In this model, the phases of software development remain the same, but the construction and delivery is done in the iterative mode. In the first iteration, a less capable product is developed and delivered for use. This product satisfies only a subset of the requirements. In the next iteration, a product with incremental features is developed.

Every iteration consists of all phases of the waterfall model. The complete product is divided into releases and the developer delivers the product release by release.

Figure 1 depicts the Iterative Enhancement Model.

This model is useful when less manpower is available for software development and the release deadlines are tight. It is best suited for in-house product development, where it is ensured that the user has something to start with. The main disadvantage of this model is that iteration may never end, and the user may have to endlessly wait for the final product. The cost estimation is also tedious because it is difficult to relate the software development cost with the number of requirements.

Read More

Waterfall Model - Software Development Model

It is the simplest, oldest and most widely used process model. In this model, each phase of the life cycle is completed before the start of a new phase. It is actually the first engineering approach of software development.

Figure 1 depicts Water Fall Model.

Figure 1 : Waterfall model

The functions of various phases are discussed in software process technology.

The waterfall model provides a systematic and sequential approach to software development and is better than the build and fixes approach. But, in this model, complete requirements should be available at the time of commencement of the project, but in actual practice, the requirements keep on originating during different phases. The water fall model can accommodate the new requirements only in maintenance phase. Moreover, it does not incorporate any kind of risk assessment. In waterfall model, a working model of software is not available. Thus, there are no methods to judge the problems of software in between different phases.

A slight modification of the waterfall model is a model with feedback. Once software is developed and is operational, then the feedback to various phases may be given.

Figure 2 depicts the Water Fall Model with feedback.

Figure 2 : Water Fall Model with feedback.

Read More

Importance of Software Engineering

As the application domains of software are becoming complicated and design of big software without a systematic approach is virtually impossible, the field of software engineering is increasingly gaining importance. It is now developing like an industry. Thus, the industry has to answer following or similar queries of clients:

1. What is the best approach to design of software?
2. Why the cost of software is too high?
3. Why can’t we find all errors?
4. Why is there always some gap between claimed performance and actual performance?

To answer all such queries, software development has adopted a systematic approach. Software development should not remain an art. Scientific basis for cost, duration, risks, defects etc. are required. For quality assurance, product qualities and process qualities and must be made measurable as far as possible by developing metrics for them.

Read More