CHAPTER 1

Algorithms and Flowcharts

1.1 ALGORITHMS

In order to solve a problem using a computer, we must first express the procedure used to solve the problem in terms of computer instructions. A computer program is just a collection of these instructions, that are necessary to solve a specific problem. The approach or method that is used to solve the problem is known as an algorithm. For example, if we wish to develop a program that tests whether a number is +ve or -ve, then the set of statements which solves the problem becomes the program. The method that is used to test if the number is +ve or -ve is the algorithm. Normally, to develop a program to solve a particular problem, we first express the solution to the problem in terms of an algorithm and then translate or code this into a program using certain programming language. So the algorithm for solving the +ve or -ve problem might be expressed as follows.

“Check whether the number is less than zero or not.

If the number is less than zero, then the number is −ve; otherwise the number is +ve”

From the above discussion an algorithm can be defined as the set of unambiguous steps precisely described in broken English or some pseudo code to solve a problem. Though generally a set of pseudocode or broken English steps written sequentially to solve a problem is termed as an algorithm, any documentation that clearly holds the procedure of problem solving, including pictorial representations, are termed algorithms. An algorithm must be definite, complete and finite. By definite, we mean that each step of the algorithm must be precisely defined such that there is no ambiguity or contradiction. Finite means the algorithm must terminate in some definite number of steps. In otherwords it should not go on forever. (Some programs known as system programs are designed to go on forever. These programs are developed for the purpose of helping computer operations and operators. Such programs have nothing to do with problem solving using computers). Complete means the algorithm must work successfully in solving all the problems of a particular type for which it is designed. Another very important property of the algorithm to be considered seriously at final stages of program implementation is efficiency. One of the better methods of learning any new technique by a rank outsider i.e. beginner, is to get acquainted with as much know-how as one needs to get going, without worrying about the worst possible cases of the problem as well as efficient implementations.

1.2 FLOWCHARTS

As computers are used to solve problems of varying complexities, solving certain problems need larger algorithms to be developed. As already mentioned, generally algorithms are written in some textual form. Reading these textual form algorithms, understanding and analyzing them is practically some what difficult and irk-some as its size increases. For example, think of an architect explaining the plan of a proposed building complex to be built in words as well as actually drawing a plan and presenting it. Also, think of a TV reporter reporting about the movement of air pressure, heat wave etc., without maps being displayed as well as reporting the same weather conditions along with the map. Definitely it is the latter one which gives better understanding and hence preferred by many. Also, our experience has shown that, given a choice, one would prefer to have a look at pictures rather than reading the details available in the form of text. In other words, pictorial representations are, in general, more appealing, easily readable as well as understandable. Thus one may conclude that, for nontrivial problems, pictorial representations of the sequence of steps involved in solving a problem are better suited. These pictorial representations are called flow charts. All the operations to be performed and all the paths of processing to be followed while solving problem are indicated in a flow chart.

Flowcharts have several advantages. As they are pictorial representations, they could be easily read as well as the inbuilt logic could be followed. It is not necessary that a problem formulator be necessarily a programmer himself. In such cases it acts as a link between the person who formulates the problem and the programmer. Further, modifications, if necessary to a programme could be affected very easily by going through its flowchart.

1.2.1 Flowchart Symbols

On flow charts different actions are represented using different geometric shapes. These are called flowchart symbols. Figures below show some of these commonly used flow chart symbols.

Fig. 1.1

Fig. 1.2

Fig. 1.3

Fig. 1.4

Fig. 1.5

Fig. 1.6

Fig. 1.7

Fig. 1.8

Fig. 1.9

The processing of a statement is shown using a rectangular box. This box may contain one or more assignment statements (Fig 1.1). The input and/or output operations are shown using a parallelogram symbol (Fig 1.2). The beginning and/or ending of an algorithm are shown by an oval shaped symbol (Fig 1.3). A diamond shaped symbol is used to represent decision making (Fig 1.4). Generally this is used to indicate two way decision making (i.e. in decision making using statements like if statements).

There exist many situations where decisions taken could lead to multiple branching (rather than simple two way decision making with true and false answers). Many computer languages do provide facilities for such multiple-branching. For example, computed goto of Fortran, switch of C constructs allow multiple-branching. A diamond box, supplemented with a system of flow lines represents multiple decision-making (Fig 1.5).

The use of a predefined process i.e. a function or a module call is indicated by using a rectangle with two vertical bars inside it (Fig 1.6).

A line with an arrow head is used as flow line. A flow line indicates the order or sequence of actions in a program. They connect various other symbols in a flow chart.

A small circle is used as a connector. This connector may be just used to indicate continuation of a process or to indicate connectivity to some other part of the program, either on the same page or on a different page.

Repeated execution of certain statements for certain number of times or under certain conditions is quite a common feature. Such executions are pictorially shown using an hexagon shape symbol (Fig 1.9). The initial value, test condition and step size are shown inside the figure. The flowline leaving the box at the lower right (labelled ≤) indicates the repeated execution of statements following it. Statement like for, while and do-while are shown with this symbol.

Generally, declaration of variables, unless otherwise they have initial values, are not shown on a flowchart.

1.3 DIVIDE AND CONQUER STRATEGY

The discussion hitherto concentrates on developing algorithms to solve a problem on hand completely. As already mentioned one can solve problems of varying complexities using computers. A problem is considered as big if the complexity of the problem results in larger algorithms, which lead to large amount of coding in a single segment. It is practically very difficult to test and debug, if necessary, larger algorithms/code segments. As such it is customary as well as natural to divide larger problems to smaller, independent subproblems, as shown in the figure below, and then solve these subproblems independently and to put the results of all the subproblems together to get the final solution. Generally there will be a central program segment which 'puts together' all the independent small subprogram segments. Such central program segments are called main programs or main functions. When one starts to solve a big problem, the actual action starts from the main and ends in the main.

As seen from the figure above a subproblem can be further subdivided into smaller problem. The bi-directional lines connecting various subproblems indicate the relation, flow of data and flow of results among various subproblems. This strategy is popularly referred to as divide and conquer strategy. One will study many such different problem solving techniques as he advances into the field of computer science. Infact, almost all computer languages do have facilities to develop program codes to these subproblems. However, they are referred to as subprograms in FORTRAN, as functions in C, as procedures in PASCAL and so on.