REFINEMENT STAGES

© The best approach to solve a complex problem is to divide it into smaller parts such that
each part becomes an independent module which is easy to manage. An example of this
approach is the System Development Life Cycle (SDLC) methodology.

© This helps in understanding the problem, analysing solutions, and handling the problems
efficiently.

© The principle underlying writing large programs is the top-down refinement. While
writing the main program, we decide exactly how the work will be divided into various
functions and then, in the refinement process.

o Itis further decide what will be the task of each functions, and what inputs are to be given
El ts to be obtained. The ind the actions of the functions

© Similarly, the purpose of studying Abstract data types is to find out some general

principles that will help in designing efficient programs.

© There exists a similarity between process of top down refinement of algorithms

and the top-down specification of the data structures. In algorithm design, we

begin with the problem and slowly specify more details until we develop a complete

program. In data specification, we begin with the selection of mathematical concepts

and abstract data types required for our problem, and slowly specify more details until

finally we can describe our data structures in terms of programming language.

© The application or the nature of problem determines the number of refinement stages

required in the specification process.

© Different problems have different number of refinement stages but in general, there are

four levels of refinement processes:

+ Conceptual or abstract level

+ Algorithmic or data structures

+ Programming or implementation

+ Applications

Conceptual Level

© At this level we decide how the data is related to each other, and what operations are

needed.

© Details about how to store data and how various operations are performed on that

data are not decided at this level.

© Algorithmic or Data Structure Level re]

© At data structure level we decide about the operations on the data as needed by our

problem for example, we decide what kind of data structure will be required to “@

the problem —contiguous list will be preferred for |

FINDING THE LENGTH OF A LIST, OR FOR RETRIEVING ANY ELEMENT, WHEREAS FOR THE

EVALUATION OF ANY EXPRESSION INTO PREFIX OR POSTFIX, STACKS WILL BE USED.

Programming or Implementation Level

© Atimplementation level, we decide the details of how the data structure will be

represented in the computer memory.

© For example, we decide whether the linked lists will be implemented with pointers or with

the cursors in an array.

Application Level

© This level settles all details required for particular application such as names for variables

or special requirements for the operations imposed by applications.

© ALUELE SITUCLUTE EVE! We UeCIae auouL Ue OPErations On (Ne data as Needed by our kN

problem for example, we decide what kind of data structure will be required to “@

the problem —contiguous list will be preferred for |

                                                    these are all applications

© The first two levels are often called conceptual. The middle two levels can be called

algorithmic as they are concerned with representing data and the operations

performed on the same. -

© Last level is basically concerned with programming.

© the conceptual level, the queue has been selected as an abstract data type and further

at the next level circular queue has been selected, as this could provide the best solution.

© Last level shows the operations which can be performed on the data, for the airport

simulation.