MCS-011 Problem Solving and Programming

First year, Semester 1

Chapters

Newsletter

Design of Algorithms

The first step in the program development is to devise and describe a precise plan of what you want the computer to do. This plan, expressed as a sequence of operations, is called an algorithm. An algorithm is just an outline or idea behind a program. something resembling C or Pascal, but with some statements in English rather than within the programming language. It is expected that one could translate each pseudocode statement to a small number of lines of actual code, easily and mechanically.

Definition

An algorithm is a finite set of steps defining the solution of a particular problem. An algorithm is expressed in pseudocode - something resembling C language or Pascal, but with some statements in English rather than within the programming language. Developing an efficient algorithm requires lot of practice and skill. It must be noted that an efficient algorithm is one which is capable of giving the solution to the problem by using minimum resources of the system such as memory and processor’s time. Algorithm is a language independent, well structured and detailed. It will enable the programmer to translate into a computer program using any high-level language. 
 

Features of Algorithm:

  1. Proper understanding of the problem: For designing an efficient algorithm, the expectations from the algorithm should be clearly defined so that the person developing the algorithm can understand the expectations from it. This is normally the outcome of the problem definition phase.
  2. Use of procedures / functions to emphasize modularity: Problem Solving To assist the development, implementation and readability of the program, it is usually helpful to modularize (section) the program. Independent functions perform specific and well defined tasks. In applying modularization, it is important to watch that the process is not taken so far to a point at which the implementation becomes difficult to read because of fragmentation. The program then can be implemented as calls to the various procedures that will be needed in the final implementations.
  3. Choice of variable names: Proper variable names and constant names can make the program more meaningful and easier to understand. This practice tends to make the program more self documenting. A clear definition of all variables and constants at the start of the procedure / algorithm can also be helpful. For example, it is better to use variable day for the day of the weeks, instead of the variable a or something else.
  4. Documentation of the program:  Brief information about the segment of the code can be included in the program to facilitate debugging and providing information. A related part of the documentation is the information that the programmer presents to the user during the execution of the program. Since, the program is often to be used by persons who are unfamiliar with the working and input requirements of the program, proper documentation must be provided. That is, the program must specify what responses are required from the user. Care should also be taken to avoid ambiguities in these specifications. Also the program should “catch” incorrect responses to its requests and inform the user in an appropriate manner. 
     

Criteria to be followed by an Algorithm

The following is the criteria to be followed by an algorithm:

  • Input: There should be zero or more values which are to be supplied.
  • Output: At least one result is to be produced.
  • Definiteness: Each step must be clear and unambiguous.
  • Finiteness: If we trace the steps of an algorithm, then for all cases, the algorithm must terminate after a finite number of steps.
  • Effectiveness: Each step must be sufficiently basic that a person using only paper and pencil can in principle carry it out. In addition, not only each step is definite, it must also be feasible. 

Example: Let us try to develop an algorithm to compute and display the sum of two numbers

  1. Start
  2. Read two numbers a and b
  3. Calculate the sum of a and b and store it in sum
  4. Display the value of sum
  5. Stop 


Top Down Design

Once we have defined the problem and have an idea of how to solve it, we can then use the powerful techniques for designing algorithms. Most of the problems are complex or large problems and to solve them we have to focus on to comprehend at one time, a very limited span of logic or instructions. A technique for algorithm design that tries to accommodate this human limitation is known as top-down design or stepwise refinement.

Top down design provides the way of handling the logical complexity and detail encountered in computer algorithm. It allows building solutions to problems in step by step. In this way, specific and complex details of the implementation are encountered only at the stage when sufficient groundwork on the overall structure and relationships among the various parts of the problem.

Before the top down design can be applied to any problem, we must at least have the outlines of a solution. Sometimes this might demand a lengthy and creative investigation into the problem while at another time the problem description may in itself provide the necessary starting point for the top-down design.

Top-down design suggests taking the general statements about the solution one at a time, and then breaking them down into a more precise subtask / sub-problem. These sub-problems should more accurately describe how the final goal can be reached. The process of repeatedly breaking a task down into a subtask and then each subtask into smaller subtasks must continue until the sub-problem can be implemented as the program statement. With each spitting, it is essential to define how sub-problems interact with each other. In this way, the overall structure of the solution to the problem can be maintained. Preservation of the overall structure is important for making the algorithm comprehensible and also for making it possible to prove the correctness of the solution.
 


Report an issue

Reporting: Design of Algorithms (topic)

Related Posts