Unit I

CSE68D:ANALYSIS AND DESIGN OF
ALGORITHM
Unit I
Basics of Algorithms
History of algorithm
• The word Algorithm comes from the name of the muslim
author Abu Ja’far Mohammad ibn Musaal-Khowarizmi.
• He was born in the eighth century in Uzbekistan. He also

wrote a book titled al Kitab al-mukhatasar fi hisab al-jabrwa’l-
muqabalah (The Compendious Book on Calculation by
Completion and Balancing).
• He is regarded as the most outstanding mathematician of his

time. He died around 840 C.E.
What is Algorithm ?
An algorithm
is any well-defined computational procedure
that takes some values, or set of values, as
input and produces some value, or set of
values, as output.
Cont..
Informally,
• A tool for solving a well-specified computational
• problem.
Example: sorting
• input: A sequence of numbers.
• output: An ordered permutation of the input.
• issues: correctness, efficiency, storage, etc.
• Input Algorithm Output
OR
• An algorithm is a step-by-step problem-solving
procedure, especially an established, recursive
computational procedure for solving a
problem in a finite number of steps.
A better one: An algorithm is a sequence of

unambiguous instructions for solving a well-
specified computational problem in a finite
number of steps.
Characteristic of an algorithm
• An algorithm has the following characteristics:
All algorithms must satisfy the following characteristic :
• Input: An algorithm requires some input values. An algorithm

can be given a value other than 0 as input.
• Output: At the end of an algorithm, you will have one or more
outcomes.
• Unambiguity: A perfect algorithm is defined as unambiguous,
which means that its instructions should be clear and
straightforward.
All algorithms must satisfy the following characteristic :
• Finiteness: An algorithm must be finite. Finiteness in this

context means that the algorithm should have a limited
number of instructions, i.e., the instructions should be
countable.
• Effectiveness: Because each instruction in an algorithm affects
the overall process, it should be adequate.
• Language independence: An algorithm must be language-
independent, which means that its instructions can be
implemented in any language and produce the same results.
Algorithms and Programming
• A good understanding of algorithms is
essential for a good understanding of the
most basic element of computer science:
programming.
• Algorithm design is all about the
mathematical theory behind the design of
good programs.
Why study algorithm design?
• Good algorithm design is one of many facets
to good program design and an important
one.
Two major types of issues
in any important programming project
1. Macro issues
2. Micro issues
The Macro Issues
• Macro issues involve elements such as how
does one coordinate the efforts of many
programmers working on a single piece of
software.
• How does one establish that a complex
programming system satisfies its various
requirements.
The Micro Issues
The micro issues involve
how best to deal with these small critical
sections.
How to Write an Algorithm?
• There are no well-defined standards for writing algorithms. It is, however,
a problem that is resource-dependent. Algorithms are never written with
a specific programming language in mind.
• As you all know, basic code constructs such as loops like do, for, while,
all programming languages share flow control such as if-else, and so on.
An algorithm can be written using these common constructs.
• Algorithms are typically written in a step-by-step fashion, but this is not

always the case. Algorithm writing is a process that occurs after the
problem domain has been well-defined. That is, you must be aware of the
problem domain for which you are developing a solution.
Example
• Now, use an example to learn how to write
algorithms.
• Problem: Create an algorithm that multiplies
two numbers and displays the output.
Example Cont..
• Step 1 − Start
• Step 2 − declare three integers x, y & z
• Step 3 − define values of x & y
• Step 4 − multiply values of x & y
• Step 5 − store result of step 4 to z
• Step 6 − print z
• Step 7 − Stop
Cont..
• Algorithms instruct programmers on how to

write code. In addition, the algorithm can be
written as:
• Step 1 − Start mul
• Step 2 − get values of x & y
• Step 3 − z ← x * y
• Step 4 − display z
• Step 5 − Stop
Cont..
• In algorithm design and analysis, the second
method is typically used to describe an algorithm.
• It allows the analyst to analyze the algorithm
while ignoring all unwanted definitions easily.
They can see which operations are being used
and how the process is progressing.
• It is optional to write step numbers.
• To solve a given problem, you create an
algorithm. A problem can be solved in a variety of
ways.
Factors of an Algorithm
• The following are the factors to consider when designing an
algorithm:
• Modularity: This feature was perfectly designed for the algorithm if
you are given a problem and break it down into small-small
modules or small-small steps, which is a basic definition of an
algorithm.
• Correctness: An algorithm's correctness is defined as when the

given inputs produce the desired output, indicating that the
algorithm was designed correctly. An algorithm's analysis has been
completed correctly.
• Maintainability: It means that the algorithm should be designed in a

straightforward, structured way so that when you redefine the
algorithm, no significant changes are made to the algorithm.
Cont..
• Functionality: It takes into account various logical steps
to solve a real-world problem.
• Robustness: Robustness refers to an algorithm's ability
to define your problem clearly.
• User-friendly: If the algorithm is difficult to understand,
the designer will not explain it to the programmer.
• Simplicity: If an algorithm is simple, it is simple to
understand.
• Extensibility: Your algorithm should be extensible if
another algorithm designer or programmer wants to
use it.
Analyzing Algorithms
• In order to design good algorithms, we must first
agree the criteria for measuring algorithms,
measuring algorithms in terms of the amount of
computational resources that the algorithm
requires.
• In practice there are many issues that need to be
considered in the design algorithms.
• Thus, in practice it is often necessary to design
algorithms that are simple, and easily modified if
problem parameters and specifications are
slightly modified.

Unit I

Uploaded by

Copyright:

Available Formats

Unit I

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 I

Uploaded by

Copyright:

Available Formats

CSE68D:ANALYSIS AND DESIGN OF

• He was born in the eighth century in Uzbekistan. He also

• He is regarded as the most outstanding mathematician of his

A better one: An algorithm is a sequence of

• Input: An algorithm requires some input values. An algorithm

• Finiteness: An algorithm must be finite. Finiteness in this

• Algorithms are typically written in a step-by-step fashion, but this is not

• Algorithms instruct programmers on how to

• Correctness: An algorithm's correctness is defined as when the

• Maintainability: It means that the algorithm should be designed in a

You might also like