Algorithm
Created by Rahman ullah Shirzad
what is an Algorithm?
• The word algorithm comes from the name of a Persian author: Abu Jafer
Mohammed ibn al Khwarizmi(c.825 A.D), who wrote a textbook on
mathematics. This word has taken on a special significance in computer
science, where “algorithm” has come to refer to a method that be used by
a computer for the solution of a problem. This is what makes algorithm
different from words as process, technique or method.
Definition of Algorithm
An Algorithm is a finite sequence of instructions, each of which has a clear meaning and can
be performed with a finite amount of effort in a finite length of time. No matter what the
input values may be, an algorithm terminates after executing a finite number of instructions
Algorithm ’a set of steps to accomplish or complete a task that is described precisely
enough that a computer can run it’’.
Described precisely: very difficult for a machine to know how much water, milk to be added
etc. in the above tea making algorithm. These algorithms run on computers or computational
devices. For example, GPS in our smartphones, Google hangouts. GPS uses shortest path
algorithm. Online shopping uses cryptography which uses RSA algorithm
Characteristics of an algorithm
• Must take an input.
• Must give some output(yes/No, valuetc.)
• Definiteness –each instruction is clear and unambiguous.
• Finiteness –algorithm terminates after a finite number of steps.
• Effectiveness –every instruction must be basic i.e. simple instruction.
We represent algorithm using a pseudo language that is a combination
of the constructs of a programming language together with informal
English statements
Performance of a program
• The performance of a program is the amount of computer
memory and time needed to run a program. We use two
approaches to determine the performance of a program.
One is analytical, and the other experimental. In
performance analysis we use analytical methods, while in
performance measurement we conduct experiments.
Time Complexity
• The time needed by an algorithm expressed as a function
of the size of a problem is called the time complexity of
the algorithm. The time complexity of a program is the
amount of computer time it needs to run to completion.
• The limiting behavior of the complexity as size increases is
called the asymptotic time complexity. It is the asymptotic
complexity of an algorithm, which ultimately determines
the size of problems that can be solved by the algorithm.
Space Complexity
• The space complexity of a program is the amount of memory it needs to
run to completion. The space need by a program has the following
components:
• Instruction space: Instruction space is the space needed to store the
compiled version of the program instructions.
• Data space: Data space is the space needed to store all constant and
variable values. Data space has two components:
Space needed by constants and simple variables in program.
Space needed by dynamically allocated objects such as arrays and class
instances.
• Environment stack space: The environment stack is used to save
information needed to resume execution of partially completed
functions.
• Instruction Space: The amount of instructions space that is
needed depends on factors such as:
The compiler used to complete the program into machine code.
The compiler options in effect at the time of compilation
The target computer
Algorithm Design Goals
• The three basic design goals that one should strive for in a program
are:
Try to save Time
Try to save Space
Try to save Face
A program that runs faster is a better program, so saving time is an
obvious goal. Like wise, a program that saves space over a competing
program is considered desirable. We want to “save face” by preventing
the program from locking up or generating reams of garbled data.
Classification of Algorithms
• If ‘n’ is the number of data items to be processed or degree of polynomial or the
size of the file to be sorted or searched or the number of nodes in a graph etc:
• Next instructions of most programs are executed once or at most only a few
times. If all the instructions of a program have this property, we say that its
running time is a constant.
• Log n When the running time of a program is logarithmic, the program gets
slightly slower as n grows. This running time commonly occurs in programs that
solve a big problem by transforming it into a smaller problem, cutting the size
by some constant fraction.
• When n is a million, log n is a doubled. Whenever n doubles, log n increases by a
constant, but log n does not double until n increases to n 2 .
Assignment_I
Continue….