Algorithms Design and Analysis, Ch.1
Uploaded by
medomedo200464Algorithms Design and Analysis, Ch.1
Uploaded by
medomedo200464Algorithms
Design and Analysis
Ch.1: Introduction to Algorithms
The Goals of this Course
In this course we will learn:
– To think algorithmically and get the spirit of
how algorithms are designed.
– To get to know a toolbox of classical
algorithms.
– The various ways of writing an algorithm
– The concept of designing an algorithm
– A number of algorithm design techniques (such
as divide-and-conquer).
– To reason (in a precise and formal way) about
the efficiency and the correctness of algorithms.
Outline
Introduction
Importance of Algorithms
Algorithm: Definition
Characteristics of an Algorithm
Ways of Writing an Algorithm
Design and Analysis vs Analysis and Design
Present and Future
Points to Remember
Key Terms
Why Study Algorithms?
Reasons why one should study algorithms :
The study of algorithms helps in enhancing the
thinking process. They are like brain stimulants
that will give a boost to your thinking process.
The study of algorithms helps in solving many
problems in Computer Science, Computational
Biology and Economics.
Without the knowledge of algorithms you can
become a coder but not a programmer.
Algorithm
Algorithms : refer to the steps to be carried out in
order to accomplish a particular task.
A good algorithm should use the resources like
the CPU time and memory judiciously بحرص. It
should also be unambiguous and understandable.
The five most essential things are to be considered
while writing an algorithm are as follows:
• Time taken
• Memory usage
• Input
• Process
• Output.
Characteristics of an Algorithm
An algorithm is a sequence of steps in order to
carry out a particular task.
It can have zero or more inputs (pseudorandom number
generator (PRNG)).
It must have at least one output.
It should be efficient both in terms of memory and time.
It should be finite(the algorithm should have countable
number of steps).
Every statement should be unambiguous.
An example to demonstrate the
importance of algorithms
Nowadays, algorithms have become important
even for biological endeavours.
Governments across the world want to make a
global database of DNAs to combat the menace of
terrorism. This would be possible only if sorting
and searching algorithms are developed, which
can extract information from billions of DNAs.
Ways of Writing an Algorithm
• English like Algorithm: It can be written in simple
English but this methodology comes with its
package. i.e. this methodology also has some
demerits.
• Natural languages can be ambiguous and therefore
lack the characteristic of being definite.
• Since, each step of an algorithm should be clear
and should not have more than one meaning,
English language like algorithms are not
considered good for most of the tasks.
Ways of Writing an Algorithm
However, Algorithm 1.1, in spite of being simple,
is not commonly used.
Ways of Writing an Algorithm
Flowchart:
• Flowcharts pictorially depict a process.
• They are easy to understand and are commonly used in case
of simple problems.
Flowchart of linear search
Ways of Writing an Algorithm
Ways of Writing an Algorithm
Pseudo Code :
• The pseudo code has an advantage of being easily
converted into any programming language.
• This way of writing algorithm is most acceptable and most
widely used.
• In order to be able to write a pseudo code, one must be
familiar with the conventions of writing it.
Ways of Writing an Algorithm
5. a>b
6. a<b
7. a >= b
8. a <= b
Ways of Writing an Algorithm
9. a != b
10. a == b
11. if<condition>then<statement>
12. if<condition>then<statement1> else<statement2>
13. Case
{
:<condition 1>: <statement 1>
:<condition n>: <statement n>
:default: <statement n+1>
}
Ways of Writing an Algorithm
Design and Analysis
In order to accomplish a task, a solution needs to
be developed. This is called designing of an
algorithm.
The next step would be to analyze the time
complexity of the algorithm.
max
m
max
ax
Analysis and Design
First of all you have to analyze the maximum time
complexity, CPU usage, memory complexity etc.
and then you will decide on the algorithms you
may be using in order to accomplish the tasks.
It may be stated at this point that a general
approach is being used in Design and Analysis,
however Analysis and Design is far more practical
and hence implementable.
Present and Future
To summarize, in developing an algorithm, the
following things are taken care of:
1. Make sure that the solution is correct.
2. Try to make sure that the time consumption is least.
3. Try to make sure that the memory consumption is also
least.
4. Try to keep each statement unambiguous and definite.
Points to Remember
An algorithm is different from a program. An algorithm is
finite; a program can be infinite.
An algorithm can be pictorially depicted by a flow chart.
The analysis of an algorithm is essential in order to judge
whether it can be implemented in the given conditions.
The analysis of an algorithm may consider time or space
or both.
The design of an algorithm can follow the analysis of the
requirements. This approach is referred to as analysis
and design.
The algorithm can be designed in order to accomplish a
task, and then can be analyzed. This approach is referred
to as design and analysis.
Any Questions?
