Algorithm

Algorithm –History Muhammad ibn Musa Al-Khwarizmi http:// www -groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Al-Khwarizmi.html

Book on arithmetic: Hindu numeration, decimal numbers, use of zero, method for finding square root Latin translation (c.1120 CE): “Algoritmi de numero Indorum”

Book on algebra Hisab al-jabr w’al-muqabala

The Problem-solving Process

Analysis Problem specification

Design Algorithm Implementation Program Compilation Executable (solution)

Components of an Algorithm  Variables and values  Instructions a. b. c. d.

Sequences Procedures Selections Repetitions

 Also required: Documentation

Algorithm basics It is a step by step procedure to solve a given problem in/with finite number of steps, where every step is labeled with a step number and no 2 steps are same. The components of an algorithm comprises of simple English statements with mathematical expressions, that specify step by step procedure towards the problem solution

Algorithm basics Properties of an algorithm It should be definite- no ambiguity It should be finite- definite number of steps It should be complete- must work successfully for which it has been designed for.  It should be efficient

Need for writing algorithm Effective communication-understandability Effective analysis-easy to write programs Proper documentation- to identify logical errors Easy and efficient coding Program debugging-detect & fix errors Program maintenance- maintenance of the software becomes easier

Algorithm -- Examples    

Assembly instructions for a model The rules of how to play a game VCR instructions Directions for driving from A to B

Algorithmic Notations Provide the necessary information as what the algorithm performs, along with the inputs and outputs

Algorithms are identified by a algorithm name followed by the type of computation it performs Ex: Algorithm Area_of_Circle ( This algorithm computes the area of a circle given radius) Each step is identified by a number followed by a description of what it does Ex: Step 3:[write the area of the circle] print area Finally the algorithm is terminated by using a stop/end. Step 4: [Stop] finished

Algorithm Example #1: Algorithm Area_of_a Circle This algorithm computes the area of a circle given radius Step 1: [start] Step 2: [ input the value of radius] read radius Step 3: [ calculate the area of the circle] area= 22/7*r*r Step 4: [ output the calculated area] write area Step 5: [finished] stop

Algorithm Example #2: Algorithm Area_of_a_Rectangle This algorithm computes the area of a rectangle given length and breadth step 1: [start] Step 2: [ input the value of length and breadth] read length, breadth Step 3: [ calculate the area of the rectangle] area= length * breadth Step 4: [ output the calculated area] write area Step 5: [finished] stop

Exchange (Swap) the contents of 2 variables

1 1

temp

a

3

b 2

Concept of Swapping “SWAP”- refers to exchange the values between 2 variables, if the 2 variables are taken as a & b with initial values a=2, b=3 then before swapping a=2,b=3, but after swapping a=3,b=2, indicating that the values are interchanged & this is achieved by using a temporary variable called “temp” to hold the value during the exchange process. Steps involved in the exchange process are  temp=a, Copy the value of a to temp  a=b, Copy the value of b to a  b=temp. Copy the value of temp to b

Algorithm Example # 3: Algorithm Swap This algorithm exchanges the values of a with b and vice versa

step 1: [start] Step 2: [ input the value of a and b] read a, b Step 3: [ perform the exchange operation] temp=a, the value of a is put to temp, hence a is empty a=b, the value of b is put to a, thus b is empty b=temp, temp contains the value of a and is put to b Step 4: [ output the exchanged values of a and b] write a & b Step 5: [finished] stop

Algorithm Example # 4: Algorithm Area_of_Triangle This algorithm calculates the area of a triangle where 3 sides a, b,c, are given

step 1: [start] Step 2: [ input the value of a ,b, c] read a, b, c Step 3: [ calculate the value of S] s= (a+b+c)/2. Step 4: [ compute the area of the triangle] area=sx(s-a)x(s-b)x(s-c) Step 5: [ display the calculated area] write area Step 6: [finished] stop

Algorithm Example # 5: Algorithm Simple_Interest This algorithm calculates the simple interest given principle, rate and time

step 1: [start] Step 2: [ input the value of p ,t, r] read p, t, r Step 3: [ calculate the value of Simple interest] S.I.= (p*t*r)/100. Step 4: [ display the calculated simple interest] write S.I. Step 5: [finished] stop

Decision making Decision making is an integral part of every one’s life, in contrast to the computer languages have ”language constructs”, by which decisions are made, 2-way decision making being the most general Example: given a number its type is determined depending upon it being greater or lesser than 0. For example in c programming language the construct if..else provides a 2 way decision making facility

Format of a if..else statement If (logical expression) { True block statements } Else { False block statements }

Algorithm Example # 6: Algorithm odd_Even This algorithm determines whether the given number is odd or even

step 1: [start] Step 2: [ input the value of n] read n Step 3: [ determine whether the given number is odd or even] if(n/2=0) write n as even else write n as odd end if Step 4: [finished] stop

Algorithm Example # 7: Algorithm Pos_Neg_Zero This algorithm checks whether the given number is positive, negative or zero

step 1: [start] Step 2: [ input the value of n] read n Step 3: [ determine whether the given number is positive, negative, zero] if(n>0) write n as positive goto step 4 else write n as negative goto step 4 endif write n as zero Step 4: [finished] stop

Algorithm Example # 8: Algorithm biggest _of_ 2 numbers This algorithm determines the largest or biggest among 2 numbers

step 1: [start] Step 2: [ input the value of a,b] read a,b Step 3: [ assume that a is largest] largest=a Step 4: [ obtain the largest among b and largest] if (b> largest) largest=b end if Step 5: [ display the largest] write largest Step 6: [finished] stop

Algorithm Example # 9: Algorithm biggest _of_ 3 numbers This algorithm determines the largest or biggest among 3 numbers

step 1: [start] Step 2: [ input the value of a,b,c] read a,b,c Step 3: [ assume that a is largest] largest=a Step 4: [ obtain the largest among a and b] if (b> largest) largest=b End if Step 5:[ obtain the largest among a ,b,c] if (c> largest) largest=c End if Step 5: [ display the largest] write largest Step 7: [finished] stop

Using if..else statement step 1: [start] Step 2: [ input the value of a, b, c] read a, b, c Step 3: [ compare and b] if (a>b) and (a>c) write a else if (b>a) and (b>c) write b else write c End if Step 4: [finished] stop

Algorithm Example # 9: Algorithm roots_of_ a Quadratic equation This algorithm determines the roots of a quadratic equation step 1: [start] Step 2: [ input the coefficients of the quadratic equation] read a,b,c Step 3: [ check whether the roots can be formed] if(a=b=c=0) write roots cannot be formed exit Step 3: [ find the 2 equal roots ] if (b2-4ac=0)then root 1=root 2= -b/(2xa) write (“equal roots”, root 1, root2) goto step 6 end if Step 4:[ find the 2 distinct roots ] if (b2-4ac=0)then root 1=-b+ b2-4ac/(2xa) root 2= -b-b2-4ac/(2xa) write (“distinct roots”, root 1, root2) goto step 6 end if Step 4:[ find the 2 complex roots ] if (b2-4ac<0)then r1=-b/(2xa) r2=|b2-4ac|/(2xa) write (“complex roots”, root 1=r1+ir2, root2=r1-ir2) end if Step 6: [finished] stop

@ a=1,b=-4,c=4, solve the Q.E.

Divide and conquer Strategy When a given problem is large it is always natural to divide it into smaller independent sub problems and then to solve these sub problems independently and to merge the results of all these sub problems together to get the final solution. A central program that “puts together”, the smaller sub programs are referred to as the main programs or main functions & this strategy is commonly referred to as the divide and conquer strategy.

The subprograms are referred differently in the programming languages for example in PASCAL they are referred as PROCEDURES, in C as FUNCTIONS and in FORTRAN as SUBPROGRAMS etc.

From Algorithms to Programs Problem

Algorithm: A sequence of instructions describing how to do a task (or process)

C Program

Flow Chart Flowcharts use standard symbols to represent a type of operation or process to be performed. The use of standardized symbols provides a common language for people to visualize problems and also makes flowcharts easier to read and understand. Types of Flowcharts There are four basic types of flowcharts: Basic, Process, Deployment, and Opportunity. Basic flowcharts quickly identify all the major steps in a process. They are used to orient a team with the major steps by just giving a broad overview of the process. Process flowcharts examine the process in great detail. They provide a comprehensive listing of all the major and sub-steps in a process. Deployment flowcharts are similar to Process flowcharts in that they are very detailed but also indicate the people who are involved in the process. This could be very useful when the process involves cooperation between functional areas. Opportunity flowcharts highlight decision step and check point. They are used for very complicated processes because they highlight specific opportunities for improvement.

Flow Chart - Symbols Ovals are used to represent starting and ending points to the flowchart process Rectangles are used to describe an action taken or a task completed.

Diamonds contain questions requiring a "Yes" or "No" decision. Data Input/Output uses a skewed rectangle to represent a point in the process where data is entered or retrieved. Rectangles with dividers are used to describe a function or a pre defined process Rectangles with triangle edges are used to define looping functions Circle – used as connector Flow lines

Terminators Start

Stop

Oval Shape One line in or out Used to indicate the beginning and end of a process

Data Boxes Input

Output

Parallelogram shaped One line in, One line out Used to indicate the input or output of data from the system.

Process Boxes Rectangle shaped One line in, One line out Used to indicate a process step Process

Decision Boxes

Yes/No Question

Diamond shaped One line in, two lines out Must contain a binary question (Yes/No, True/False, 0/1, etc) Used to branch a program dependent upon a condition being met

Subprocess Box

Subprocess

Rectangle shaped, with bars on the sides One line in, One line out Used to include a predefined process

Simple Flowchart This chart indicates a typical example of Input, Process, Output

Three basic structures All flowcharts are composed of three basic control structures… Sequence Decision Repetition

Sequence Events happen one after the other, with no branching Flow is directly from top to bottom

Decision Uses a decision box to branch to one of two options Flow is downwards Lines rejoin the flow at lines, NOT boxes.

Repetition Used to repeat a process, or wait until a condition is met before proceeding. Flow is upwards. Lines join at lines, NOT boxes.

Bad design… What is wrong with this chart? The box has two lines in, one line out… Lines must join other lines, never boxes!

Bad design… What is wrong with this flowchart? Never use curved lines. Always straight Always vertical or horizontal.

Bad design… What is wrong with this flowchart? Never use curved lines. Always straight Always vertical or horizontal.