Chapter 1

Introduction

1.1 | SOFTWARE

A program is generally made up of a sequence of instructions that clearly specify what a computer is supposed to do. Software, in contrast, is a set of programs that are either supplied by the manufacturer of the hardware associated with it or written by an application developer, with purposeful intent of commercial or public use. Thus, for a program to qualify as software, it should have the properties of correctness, versatility, and maintainability in addition to well-documented code.

Software engineering is a methodical approach used in software development. It is defined in IEEE Software Engineering Standards 1987 as Software Engineering is the systematic approach to the development, operation, maintenance and retirement of software.

A program is rarely executed correctly on a computer system unless considerable amount of time has been spent in the problem-solving phase of its development. Coding can start only after the problem-solving phase is complete. The computer language (code) is then coded from the prepared plan. The plan for solving a problem involves development of a series of instructions, referred to as an algorithm. An algorithm enables us to solve the problem at hand in a systematic way. The development of an algorithm for a problem is justified by the fact that it is necessary to select the correct logical steps to be followed so that the problem can be solved in a quick and an efficient manner.

Let us understand the working of a program by drawing an analogy with a blender used to prepare our favourite recipe. To prepare food, we follow different types of processes - the first pertaining to the use of the blender and the second to the ingredients required for the recipe. Here the recipe is analogous to the program, the ingredients are the input, and the prepared food is the output of the program.

We require two different types of software to enable a computer to process data, namely, systems software and application software. Returning to the analogy, application software can be equated with the recipe, while systems software acts as the blender. Let us take a look into each type of software first.

Computer software consists of two major types of programs:

• Systems software: It controls and supports the operations of a computer system as it performs various information processing tasks.
• Application software: It directs the performance of a particular use or application of computers to meet the information processing needs of computers.

1.2 | SYSTEMS SOFTWARE

Systems software can be subdivided into system control programs, system support programs, and system development programs.

• System control programs control the use of hardware, software, and data resources of the computer system during the execution of information processing tasks.
• System support programs support the operations, management, and users of the computer system by providing a variety of support services. Service programs, performance monitors, and security monitors are some of the major support programs.
• System development programs help users to develop information processing programs and procedures, and to prepare user programs for execution by the system. Major development programs include language translators, compilers, and application development systems.

1.2.1 | Operating Systems

The most important system software for any system is its operating system. An operating system is an integrated system of programs that supervises the operations of the Central Processing Unit (CPU) - controls the input/output (I/O) and storage functions of the computer system, and provides various support services. The control programs of an operating system perform three important tasks like job, resource, and data management. Other programs that could be part of the operating system or that can be acquired as service programs may include language translators and other software.

1.2.2 | Other System Software

Language translator programs convert programming language instructions into machine language instruction codes. Service programs are specialized programs that perform routine and repetitive functions, and are made available to all the users of a computer system. A common service program is the linkage editor, which updates a program by defining the specific storage locations it requires and links together the parts of the program, which require other routines. Major categories of service programs are utility programs, which perform various housekeeping and file conversion functions.

1.3 | APPLICATION SOFTWARE

Application software refers to those programs that are written to solve day-to-day problems such as payroll maintenance, inventories, billings, etc. An application program is written by a programmer or a group of programmers (employed by a software development firm), and the latter charges a fee for rendering the service. Given a certain application requirement, package software provides an easy generic solution assuming it meets the needs of the client. The use of package software counterpoints with specialized software, which is developed for a particular client requirement.

Application software includes a variety of programs that can be segregated into general purpose, business, scientific, and other application program categories.

• General-purpose application programs can perform common information processing jobs for users. Examples are word processors, spreadsheet applications, and graphic packages.
• Business application programs can accomplish information processing tasks that support important business functions for industrial requirements.
• Scientific application programs perform information processing tasks of all areas involved in scientific research, experimentation, and development. Other application program areas include education, entertainment, music, and art.

1.4 | PROGRAM DEVELOPMENT PROCESS

A program is a sequence of instructions used to perform a specific task. The program development process can be viewed in a number of steps as follows:

• Understanding the Specifications: The specification for the problem must be clear and unambiguous.
• Role of the System Analyst: Medium- and large-sized companies employ professionals, designated as a system analyst, who is responsible for the overall design procedures. The system analyst determines, by querying the client, the nature of the inputs and outputs needed, and provides the input and output layouts along with the processing requirements for the programmers. According to customization needs, as stated earlier, the client might be advised to purchase a general-purpose package, or a customized package might be in order.
• Problem Analysis: The program to be developed might be simple or complex, in accordance with the nature of the task.
• Solution Design: Every task to be executed needs to be planned carefully. This involves testing the various conditions, taking alternate paths in the procedure depending on the outcome of the test, and determining the sequence of the steps. There are two ways of accomplishing this task:
  • Algorithm: A detailed description of the sequence of steps to be followed.
  • Flowchart: A pictorial representation of the program, which is easier to visualize due to its graphical organization.
• Testing and Debugging: A computer program seldom runs perfectly for the first time due to the possible presence of logical and/or syntactic errors. These errors are referred as bugs. The process of removing these bugs is called debugging. The errors in the program are checked by testing it at various stages.
  • Use of Test Data: Test data should be prepared in such a way that the programs run by using this data. It should be prepared so as to include all the conditions that the program is expected to test.
  • Use of Diagnostic Tools: There are diagnostic aids, which programmers may deploy to detect errors when a program fails to run correctly. The diagnostic procedures may vary from one language to another. The diagnostic tools provide, in general, a method for testing the execution of a program at each step or each time the program follows a particular path. Breakpoints may also be used in code for debugging purposes.
• Installation: The tested software is installed at the client end and finally tested with real-time data.

1.5 | ALGORITHMS

An algorithm is a well-defined computational procedure (sequence of computational steps). It takes a set of values as its input and produces a set of values as its output. It can be viewed as a utility for solving a computational problem.

There are a number of important features that must be satisfied by any algorithm:

• Finiteness: This imposes that the algorithm must terminate after executing a finite number of steps, i.e., it cannot run infinitely.
• Definiteness: An algorithm, as stated earlier, is a sequence of steps. For a computational procedure to qualify as an algorithm, each step in the procedure must have a precise definition.
• Input and Output: An algorithm has a domain of values, which initialize the procedures. These are called the input values to the algorithm. It must also generate a set of result values called output values. Thus, an algorithm can be viewed as a function or a transformation that maps input values to output values.
• Effectiveness: The operations specified in an algorithm must be basic enough in nature to be performed by someone using a pen and a paper.

Let us illustrate an example of algorithm for calculating the Greatest Common Divisor (GCD) of any two numbers. The problem must be stated explicitly before an algorithm can be devised. The GCD problem is stated as:

“Given two positive integers, p and q, find their GCD x, (i.e., the largest positive integer that divides both p and q exactly).”

We present Euclid's algorithm for the problem. (Here, Si's are the steps of the algorithm and ‘i’ refers to the step number.)

Algorithm Euclid GCD

Begin

S1:	[ Calculate remainder]
	Divide p by q and let r be the remainder.
S2:	[Terminate algorithm if remainder is zero]
	If r is zero, go to Step S4.
S3:	[Loop]
	Set p ← q set q ← r Go to Step S1.
S4:	[Set output GCD to q]
	Set x ← q End.

End algorithm Euclid GCD.

By examining the steps illustrated in Euclid GCD, we find that the procedure has inputs p and q, and produces x as output. It can be shown that the procedure terminates after a finite sequence of steps (ensured by S3). Each step is, at the same time, precisely defined and can easily be carried out by hand. Thus, we can state that the procedure given above is an algorithm.

1.6 | ANALYSIS OF ALGORITHMS

As there are a number of methods that can be adapted for solving a particular problem, a number of algorithms corresponding to the various methods may exist. We often have to make a choice regarding the use of a particular algorithm as a suitable one. Such a selection necessitates analysis of algorithms. When we talk about analysing an algorithm for solving a particular problem, we try to predict the resources required by the algorithm. Although resources such as memory capacity and system bandwidth might be of concern, the efficiency of an algorithm is primarily measured by its running time.

Generally, it is found that the running time of an algorithm increases with the input size. Thus, the running time is described as a function of the input size. The number of items in the input or the number of bits required for input representation is the most general measure of input size.

• Worst-case Analysis: Worst case is an upper bound on the running time for any input to the algorithm. This guarantees that the algorithm will not be worse under any circumstance. The worst case occurs fairly often and is a natural choice for analysis.
• Average-case Analysis: The average case is often roughly as bad as the worst case, where we consider that all inputs of a given size are equally alike. However, it might not always be apparent as to what constitutes an average input to a particular problem.
• Order of Growth: It is the rate of growth of the running time that algorithmic studies are generally concerned with. We, therefore, consider only the leading term of a formula, ignoring the leading term's constant co-efficient, as constant factors are less significant than the rate of growth in determining the computational efficiency for large inputs.

We consider an algorithm to be more efficient than another if its worst-case running time has a lower order of growth.

1.7 | FLOWCHARTS

The flowchart is an important tool aiding development. A flowchart is a graphic/pictorial representation of the steps necessary to solve a problem, accomplish a task, complete a process, or illustrate the components of a system. The basic types of flowcharts are system flowcharts and program flowcharts. A system flowchart is a representation of the components and flows in a system. A program flowchart represents the information processing steps to be performed within a computer program. In this section, we shall only illustrate program flowcharts. The various symbols used in drawing flowcharts are shown in Figure 1.1. Henceforth, we shall mean program flowcharts, when we refer to flowcharts unless stated otherwise.

 

 

The various flowchart symbols are explained as follows:

• Oval/Rounded Rectangle: These symbols indicate the start or end of the program as indicated by the text written inside the symbol.
• Rectangle: Indicates a processing step where the step performed is indicated inside the rectangle.
• Diamond: Indicates that a condition check is to be performed. The data under test and the test performed are indicated inside the diamond.
• Parallelogram: Indicates I/O operations.
• Arrow: Indicates direction of program control flow.

A program flowchart or flowchart illustrates the detailed sequence of steps undertaken by a program. It can be used to

• visualize the logic and sequence of steps in an operation,
• experiment with various programming approaches, and
• keep track of all processing steps.

A self-explanatory flowchart is illustrated in Figure 1.2(a) to read and add 10 integers and display the sum.

 

 

The flowchart for the algorithm Euclid GCD presented in Section 1.5 is shown in Figure 1.2(b).

 

1.8 | PROGRAMMING LANGUAGE CLASSIFICATIONS

A language is a medium for communication. The languages we speak are called natural languages. A programming language is a subset of the set of natural languages. It contains all the symbols, characters, and usage rules that permit a human being to communicate with computers. A variety of programming languages have been invented over the years of computer history. However, every programming language must accept certain types of written instructions that enable a computer system to perform a number of familiar operations. In other words, every programming language must have instructions that fall under the following categories:

• Input/Output Instructions: A program needs input data from the external world (or sometimes given implicitly) with which it performs operations on the input data, and generates output (compare with algorithm). Input/output instructions. provide details on the type of input or output operations to be performed, and the storage locations to be used during the operations, hence they are provided with purpose.
• Arithmetic Instructions: A program might be required to perform arithmetic operations on the data in the program. Arithmetic instructions are provided for the requirement. These perform the arithmetic operations of addition, subtraction, multiplication, division, etc.
• Logical/Comparison Instructions: They are used to compare two values to check whether the values satisfy a given condition or state.
• Storage/Retrieval and Movement Instructions: These are used to store, retrieve, and move data during processing. Data may be copied from one storage location to another and retrieved as required.
• Control Instructions: These are selection and loop constructs, which aid in out-of-sequence program flow.

Although all programming languages have an instruction set that permits these familiar operations to be performed, a marked difference is found between the symbols and syntax used in machine languages, assembly languages, and high-level languages.

1.8.1 | Assembly Language

Some applications are developed by coding in assembly language - a language closest to the machine language. This type of application software is most efficient for processing data. However, since a particular flavour of the assembly language is designed for a particular architecture, the type of assembly language understood by a computer depends upon the underlying architecture of the microprocessor used. For example, if a Zilog® microprocessor is used, then the machine language understood is Z-80. On the other hand, a flavour of the Intel® assembly language is used for a Pentium® microprocessor which differs from the Z-80. Thus, assembly languages are architecture-dependent.

1.8.2 | High-level Languages

Given the inability of assembly language to adapt across different architectural platforms and given the varied nature of real-world problems, a variety of computer languages, called high-level languages, were developed, each suited best to a model in a particular class of problems. High-level language programs are architecture-independent, easier to write, and provide easier maintenance and readability than their assembly-language counterparts. However, they require longer execution time compared to assembly-language programs.

Different high-level programming languages were introduced in the 1950s to reduce the problems that arose in writing code in assembly and machine language. When the first high-level languages were developed, the longer translation and execution time were considered as serious limitations of the technique. Nonetheless, the following factors contributed to the popularity of high-level languages for application development:

• Savings in Programming Time and Training: High-level languages were easier to learn and understand. Thus, it took less time and effort to write an error-free program or to make corrections and code-revisions.
• Increased Speed and Capacity of Hardware: The third and fourth generations of computer hardware brought about a revolution in access time, memory and disk capacities. This caused the time overhead incurred by the use of high-level languages to be tolerable.
• Increasing Complexities of Software: With time, software systems grew more complex. This necessitated use of complex constructs each of which could represent several lines of assembly code and was provided by high-level languages.

Some popular high-level languages include FORTRAN (FORmula TRANslation), COBOL (COmmon Business Oriented Language), Pascal (after Blaise Pascal), C (refer to Section 1.11), and Ada (after Ada Byron, Countess of Lovelace - the world's first computer programmer).

1.9 | PROGRAMMING TECHNIQUES

As stated earlier, the task of coding for a problem in a convenient programming language is performed only after extensive effort in the problem-solving stage. The following sections provide an insight into some commonly adopted programming techniques.

1.9.1 | Bottom-up Design

Early programming techniques developed in the 1950s centred on problem-solving by using bottom-up design of the solution in which the extreme details of the programming solution were investigated first, as opposed to beginning with a breakdown by broad objectives. Each program was written in isolation to solve a particular sub-problem. The difficulty arose when the various sub-programs had to work together to produce the desired programs. Program logic was guided by the limitations of primary memory, and programs were designed with the objective of executing them as fast as possible. However, as application programs grew in size, several programmers worked together to solve them. Project teams were set up, consisting of several programmers and a project leader. However, programmers often switch jobs and might leave a company before a project is fully developed, thus requiring another programmer to continue the unfinished work midstream. This required formulation of a definite summary of how a problem is to be solved. This was not provided by the bottom-up approach to programming. Another approach was required.

1.9.2 | Top-down Design

In recent years, computer memory ceased to be the limitation factor for most of the application programs. This, along with increasing software complexity and maintenance hitches, shifted the focus from the execution time to the programming techniques adopted in development of a program. It allowed programs to be written in a more organized manner, i.e., in a structured manner, producing code that is easier to read, analyze, and modify later - if the need arose. With increasing demands for software efficiency and programming standardization, a changed approach saw the programmers examining the problem as a whole and outlining the major steps to solve the problem. Then the process was repeated and the steps thus obtained were broken down in finer details. This is the top-down programming approach and is used in structured programming.

1.9.3 | Structured Programming

Structured programming is a methodology that is part of a renewed emphasis on software engineering, which involves the systematic design and development of software and the management of the software development process. Software engineering views the development of a program as a coordinated activity involving people, tools, and practices; use of modern design; and development and management methods in an integrated approach. Structured approach involves the use of methods such as top-down program design and a limited number of control structures in a program to create tightly structured modules of program code.

The effect of top-down design and structured programming has been used to lower the overall cost of programming. The structured approach promises to reduce the cost of developing and maintaining computer programs by standardizing program development and structures used. This increases the simplicity and accuracy, and at the same time minimizes programming and maintenance cost.

A ’traditional’ flexible and creative environment provided to the programmer often results in complex and difficult-to-read programs requiring much testing before they are error-free. These also become costly to develop and maintain. Structured programming, on the other hand, emphasizes group responsibility for program development. It also brings in a standardization of program-design concepts and methods, which significantly reduces the program complexity.

Organizations using structured programming have shown the following characteristics:

• Programming Productivity: Programmers write more program statements per day with fewer errors.
• Program Economy: The cost and time of program development and maintenance are reduced.
• Program Simplicity: Programs are easier to read, write, correct, and maintain.

These results highlight the reasons for structured programming to continue to be a popular programming methodology.

1.9.4 | Modular Design

Structured programming is used as a set of tools to improve program organization, facilitate problem solving, and make code easier to write and analyse in both individual and group projects. Using structured programming, the solution to the problem is divided into segments called modules.

• A module is a logically separable part of a program. It is a unit, discrete and identifiable with respect to compilation and loading. In terms of common programming language constructs, a module can be a macro, a function, a procedure (or subroutine), a process, or a package.
• Each module involves processing of data that are logically related. Modules are functional parts, that aid in processing. Ideally, each module works independent of other modules, although this is sometimes impossible.
• Modules are ranked by hierarchy and organized on the basis of importance. The lower the module on the structure organization plan, more is the detail given to the programming steps involved. The controlling module resides at the top level. It gives the view of the overall structure for the entire program. The system is designed to give more detail at each module level. A module is coded and tested, and then tested with other tested modules. This procedure makes program testing easier, since there is only one entry point and one exit point per module.

1.10 | STRUCTURED PROGRAMMING CONSTRUCTS

The most common techniques used in structured programming to solve all problems are called constructs. Sequence, selection, and repetition constructs are shown in Figure 1.3. These constructs are also called control structures. Using these three basic control structures, it is possible to write standardized programs, which are easy to read and understand.

 

 

• Sequence Structure: Sequence refers to an instruction or a series of instructions that perform a required calculation or allow input or output of data. Since these steps are executed one after the other, there is no change in the flow logic. Figure 1.3(a) illustrates that program statements in function A will be executed before those for function B. In other words, we say that control ’flows’ from function A to function B.
• Selection Structure: Selection refers to testing for a certain condition for data. There are only two possible answers to questions regarding data - true (yes) or false (no). One selection-technique variation is known as the IF-THEN-ELSE. The instructions that are to be executed when the condition is true follow the IF-THEN alternative. The instructions followed by the ELSE alternative represent what is to be executed when the condition is false. Figure 1.3(b) shows that if the condition is true, the control will flow to function B and its statements will be executed; if it is false, function A is executed. Another selection variation is the IF-THEN. It is used when some operation is to be done only when the condition is true.
• Repetition Structure: Repetition involves the use of a series of instructions that are repeated until a certain condition is met. Repetition involves the use of two variations - the while and the do-while. The while performs a function as long as a condition is true. On the other hand, do-while allows a function to be executed until the given condition is false. Another marked difference is that the while first tests the given condition and then executes the function, whereas do-while processes the function before checking the condition. These are illustrated in Figure 1.3(c).

1.11 | HISTORY OF C LANGUAGE

C has its origin in the early 1970s in Basic Combined Programming Language (BPCL), a project shared by AT&T Bell Labs, USA, and developed by Martin Richards. B was derived from BCPL, written in 1970 by Ken Thompson for the first UNIX system on the DEC PDP-7. Dennis Ritchie is credited with defining and creating C from the language B. Many others also influenced the development of the language. C is closely related to the UNIX operating system since it was developed along with it. Most of the UNIX commands are written in C. The basic goal was to create a language for writing operating systems. C was a mechanism for providing portable assembly language. Hence, C was originally intended for systems level programming. Today, C has been implemented on many different types of hardware and the language is used to tackle a large class of programming problems.

Most commercial implementations of C differ from Kernighan and Ritchie (K&R) original definition. This has created portability problems within different platforms. The American National Standards Institute (ANSI) established a committee in the beginning of the summer of 1983 to remove discrepancies from within different versions of C that were commercially available. C was finally standardized in 1988, and was named ANSI C. A standard ANSI-compatible C compiler includes some new features to aid in programming, in addition to all the features of a UNIX-based compiler.

1.12 | C LANGUAGE OVERVIEW

C is a powerful and flexible general-purpose language that has gained the widest of acceptance over the years. Several features make C a very attractive programming language for coding solutions. These include:

• Performance features such as speed and efficiency of the executable program.
• Features relating to the portability of the programs. C is independent of any particular machine architecture - it is not bound to any hardware or system. Programs can be written to execute, without change, on a wide range of hardware.
• C is a simple and a straightforward language, providing only low-level operations and none to deal directly with composite objects or other higher level mechanisms (these high-level mechanisms can be built using functions - the C unit of a module).
• Its versatility enables it to be used to solve problems in every application area.
• Modularity allows C to be ideal for large projects involving several programmers. It lets us break a large program into small manageable pieces, which can be reused in other programs.

Of course, the extent to which a particular program takes advantage of modularity and portability depends on how well the program is written (programmer's skill).

C is both a low- and a high-level language. It supports the low-level features (i.e., the bit-manipulation facilities of assembly) needed by the operating-system implementers and the compiler writers. It also supports the high-level features of control and data structures characteristic of a procedural language. C is as flexible as a low-level language. On the other hand, C provides the tools for a structured program, as a high-level language does. Thus, C is often called a middle-level programming language.

SUMMARY

The hardware of a digital computer is operated on by software instructions. Programs differ from software in that the programmer for his own needs usually writes programs whereas software is a commercial product.

The development of software begins with a thorough analysis of the system requirements and the formulation of a sequence of steps (usually in the form of algorithms or flowcharts) to tackle the problem. Given a number of available algorithms, an appropriate one is usually chosen by worst-case analysis.

Systems may be designed either by a top-down understanding of the nature of the problem in its entirety or by a bottom-up approach of developing solutions to sub-problems and leaving the integrated solution to be developed at the last phase. Both approaches involve coding individual modules and use of certain structured programming constructs.

Coding is then performed in an appropriate assembly or high-level language and the code is documented properly. Testing and debugging is used to remove errors in the code. The final error-free software is then installed at the client. Maintenance may have to be performed in future and it is usually the responsibility of the developer.

C is often the preferred tool for writing programs. Developed in the 1970s, as an aid to system programming, C combines features from both high- and low-level programming languages and is thus a middle-level language. C is widely accepted for its performance, portability, versatility, simplicity, and modularity.

NEW TERMINOLOGY CHECKLIST

• Program
• Assembly language
• Top-down design
• Software
• High-level Language
• Structured programming
• Algorithm
• Flowchart
• Modular design
• System software
• System analyst
• Portability
• Operating systems
• Debugging
• Middle-level language
• Application software
• Bottom-up design

EXERCISES

1. Write an algorithm to find the maximum of three numbers a, b, and c. The output should be stored in ’max’.
2. “An operating system never terminates - it is infinite.” Based on this statement, justify whether an operating system is an algorithm.
3. Trace Euclid's algorithm for GCD (in Section 1.5) for inputs (32, 14), (12, 9).
4. Modify Euclid's algorithm (in Section 1.5) to accommodate a check of the input variables so that the algorithm executes only on positive integer inputs and the divide by zero error is detected.
5. Write an algorithm that accepts a positive integer number, n, and calculate the factorial of the number. Reject inputs less than 1 or greater than 17.
6. Draw a flowchart to convert miles into kilometres, given that 1 km = 1.609 miles and M is the input value in miles and K is the output value in kilometres.
7. Write an algorithm that calculates all the elements of rows and columns of a square matrix and calculate the total of primary and secondary diagonal.
8. Write an algorithm that accepts two positive integer numbers n1 and n2 (n1 < n2), and print the prime numbers in between n1 and n2, both inclusive.
9. What is validation of an algorithm?
10. What are the advantages and disadvantages of flowcharts?