Unit 2-Algorithms PDF

INTRODUCTION TO ALGORITHMS
Logic
Logic is a tool to develop reasonable conclusions
based on a given set of data. Logic is free of
emotion and deals very specifically with
information in its purest form.
1. Informal logic is the mode used in everyday
reasoning and argument analysis.
2. Formal logic deal with deductive reasoning
and the validity of the inferences produced.
Steps involved solving a particular problem:
Analyze the problem.
Identify the Inputs
Identify the Outputs
Identify the Process
Write the steps in english to solve the problem.
Draw a control flow diagram to link these steps.
Write the program for the solution.
Execute the program with different inputs and
verify for output.
1.1. PROGRAMMING
A typical programming task can be divided into two phases:
Problem solving phase
Produce an ordered sequence of steps that describe solution of problem
This sequence of steps is called an algorithm
Implementation phase
Implement the program in some programming language
1.2. PROBLEM SOLVING

Programming is a process of problem solving
Problem solving techniques
Analyze the problem
Outline the problem requirements
Design steps (algorithm) to solve the problem
Algorithm:
o Step-by-step problem-solving process
o Solution achieved in finite amount of time
1.3. ANALYZE THE PROBLEM

Thoroughly understand the problem
Understand problem requirements
Does program require user interaction?
Does program manipulate data?
What will be the output?
If the problem is complex, divide it into subproblems
Analyze each subproblem as above
An informal definition of an algorithm is:
Algorithm: a step-by-step method for solving a

problem or doing a task.
Formal definition
• Algorithm:
• An ordered set of unambiguous steps that produces a
result and terminates in a finite time.
ALGORITHM
“Algorithm" is a formally defined procedure for performing some calculation. If a procedure is
formally defined, then it must be implemented using a programming language. The algorithm
gives logic of the program, that is, a step-by-step description of how to arrive at a solution.
Algorithm provides a blueprint to write a program to solve a particular problem in finite
number of steps. Algorithms are mainly used to achieve software re-use
In order to qualify as an algorithm, a sequence of instructions must process the following
characteristics:
Instructions must be precise
Instructions must be unambiguous
Not even a single instruction must be repeated infinitely
After the algorithm gets terminated, the desired result must be obtained
PROPERTIES OF ALGORITHM
1. Input:- an algorithm accepts zero or more inputs
2. Output:- it produces at least one output.
3. Finiteness:- an algorithm terminates after a finite numbers of steps.
4. Definiteness:- each step in algorithm is unambiguous. This means that the
action specified by the step cannot be interpreted (explain the meaning of) in
multiple ways & can be performed without any confusion.
5. Effectiveness:- it consists of basic instructions that are realizable. This means
that the instructions can be performed by using the given inputs in a finite
amount of time.
DEVELOPING AN ALGORITHM
1.Identify the Inputs
What data do I need?
How will I get the data?
In what format will the data be?
2. Identify the Processes

How can I manipulate data to produce meaningful results?
Data vs. Information
3. Identify the Outputs

What outputs do I need to return to the user?
What format should the output take?
4. Top-down design approach is often used.

How can I break larger problems into smaller, more manageable pieces?
First try to break the process into a number of steps, which are smaller and
simpler than that for the entire process.
The sub-algorithms can themselves be broken down into smaller portions.
KEY FEARTURES OF AN ALGORITHM
Any algorithm has a finite number of steps and some steps may involve decision making,
repetition. Broadly speaking, an algorithm exhibits three key features that can be given as:
Sequence: Sequence means that each step of the algorithm is executed in the specified order.
Decision: Decision statements are used when the outcome of the process depends on some
condition.
Repetition: Repetition which involves executing one or more steps for a number of times can be
implemented using constructs like the while, do-while and for loops. These loops executed one
or more steps until some condition is true.
Three constructs
Algorithm
• Find area of a rectangle
• Step 1: Input L,B
Step 2: area=L*B
Step 3: Print area
Step 4: Exit
• Find the area of a circle
• Step 1: Input R
Step 2: area=3.14*R*R
Step 3: Print area
Step 4: Exit
• Step 1: Input SP,CP
Step 2: if (SP>CP) then
p=SP-CP
Print p
else
l=CP-SP
Print l
endif
Step 3:Exit
• Detailed Algorithm
• Step 1: Input M1,M2,M3,M4
Step 2: GRADE  (M1+M2+M3+M4)/4
Step 3: if (GRADE < 50) then
Print “FAIL”
else
Print “PASS”
endif
Step 4:Exit
• Detailed Algorithm
• Step 1: Input M1,M2,M3,M4
Step 2: GRADE  (M1+M2+M3+M4)/4
Step 3: if (GRADE > 60) then
Print “Ist”
elseif (GRADE > 50)and (GRADE <60) then
Print “IInd”
else
Print “Fail”
endif
Step 4:Exit
• Step 1: Input the value of N
Step 2: Set i=1
Step 3: Repeat until i<=N
Step 5: Print i
Step 4: Set i=i+1
end loop
Step 5: Exit
Concept of a subalgorithm
Translators
• Translators are just computer programs which
accept a program written in high level or low
level language and produce an equivalent
machine level program as output. Translators
are of three types :
• Assembler
• Compiler
• Interpreter
• Assembler is used for converting the code of low level language
(assembly language) into machine level language.
• Compilers and interpreters are used to convert the code of high

level language into machine language. The high level program is
known as source program and the corresponding machine level
program is known as object program. Although both compilers and
interpreters perform the same task but there is a difference in their
working.
• A compiler searches all the errors of a program and lists them. If the
program is error free then it converts the code of program into
machine code and then the program can be executed by separate
commands.
• An interpreter checks the errors of a program statement by

statement. After checking one statement, it converts that
statement into machine code and then executes that statement.
The process continues until the last statement of program occurs.
Difference between Compiler and Interpreter
• Compiler scans the entire program once and then converts

it into machine language which can then be executed by
computer's processor. In short compiler translates the
entire program in one go and then executes it. Interpreter
on the other hand first converts high level language into an
intermediate code and then executes it line by line. This
intermediate code is executed by another program.
• The execution of program is faster in compiler than
interpreter as in interpreter code is executed line by line.
• Compiler generates error report after translation of entire
code whereas in case of interpreter once an error is
encountered it is notified and no further code is scanned.
Programming Languages:
• Machine Language (Low Level)
• Assembly Language
• High level Language
Machine Language
• The fundamental language of the computer’s
processor, also called Low Level Language.
• All programs are converted into machine language
before they can be executed.
• Consists of combination of 0’s and 1’s that represent
high and low electrical voltage.
Assembly Language
• A low level language that is similar to machine
language.
• Uses symbolic operation code to represent the

machine operation code.
High Level Language
• Computer (programming) languages that are
easier to learn.
• Uses English like statements.
• Examples are C ++, Visual Basic, Pascal,
Fortran and …....
Design Methodologies
• Functional decomposition (Top-Down)

–The whole system is characterized by
a single function, and then the
function is decomposed into a set of
functions in a process of stepwise
refinement.
Functional decomposition
The System
Function1 Function2 Function3 ... ...

Desk Table top Filing cabinet Bookshelves
... ...
Function11 Function12 ... ...
Left drawer Middle drawer Right drawer

Design Methodologies
• Functional composition (bottom-up)

– You can have different components of
functions such as that from a function
library
– You can compose them into a module
with a more significant function.
Functional composition
The System
Function1 Function2 Function3 ... ...

Desk Table top Filing cabinet Bookshelves
... ...
Function11 Function12 ... ...
Left drawer Middle drawer Right drawer

Unit 2-Algorithms PDF

Uploaded by

Copyright:

Available Formats

Unit 2-Algorithms PDF

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Unit 2-Algorithms PDF

Uploaded by

Copyright:

Available Formats

INTRODUCTION TO ALGORITHMS

1.2. PROBLEM SOLVING

1.3. ANALYZE THE PROBLEM

Algorithm: a step-by-step method for solving a

2. Identify the Processes

3. Identify the Outputs

4. Top-down design approach is often used.

• Compilers and interpreters are used to convert the code of high

• An interpreter checks the errors of a program statement by

• Compiler scans the entire program once and then converts

• Uses symbolic operation code to represent the

• Functional decomposition (Top-Down)

Function1 Function2 Function3 ... ...

Function11 Function12 ... ...

Left drawer Middle drawer Right drawer

• Functional composition (bottom-up)

Function1 Function2 Function3 ... ...

Function11 Function12 ... ...

Left drawer Middle drawer Right drawer

You might also like