MODULE 1

ALGORITHM

Definition: An algorithm is a sequence of unambiguous instructions for solving

a problem. It is a step by step procedure with the input to solve the problem in a
finite amount of time to obtain the required output.

Characteristics of an algorithm: Every algorithm must be satisfied the

following characteristics.

Input: Zero / more quantities are externally supplied.

Output: At least one quantity is produced.

Definiteness: Each instruction is clear and unambiguous.

Finiteness: If the instructions of an algorithm is traced then for all cases the
algorithm must terminates after a finite number of steps.

Efficiency: Every instruction must be very basic and runs in short time with
effective results better than human computations.

Pseudo code for Expressing Algorithms:

1. An algorithm is a procedure. It has two parts; the first part is head and the
second part is body.

2. The Head section consists of keyword Algorithm and Name of the algorithm
with parameter list. E.g. Algorithm name1(p1, p2,…,p3) The head section also
has the following: //Problem Description: //Input: //Output:

3. In the body of an algorithm various programming constructs like if, for, while
and some statements like assignments are used.

4. The compound statements may be enclosed with { and } brackets. if, for,
while can be open and closed by {, } respectively. Proper indention is must for
block.

5. Comments are written using // at the beginning.

6. The identifier should begin by a letter and not by digit. It contains alpha
numeric letters after first letter. No need to mention data types.
7. The left arrow “:=” used as assignment operator. E.g. v:=10

8. Boolean operators (TRUE, FALSE), Logical operators (AND, OR, NOT) and
Relational operators (<,<=, >, >=,=, ≠, <>) are also used. 9. Input and Output
can be done using read and write.

10. Array[], if then else condition, branch and loop can be also used in
algorithm.

Example: Algorithm to Find the Largest Number in an Array

Problem: Find the largest number in a list of numbers.

Algorithm:

i. Start
ii. Assume the first element is the largest → max = arr[0]
iii. Compare max with each element in the array
iv. If any element is greater than max, update max
v. Repeat until all elements are checked
vi. Display max
vii. Stop

Fundamentals Algorithm, Problem Solving:

(i) Understanding the Problem

 This is the first step in designing of algorithm.
 Read the problem‟s description carefully to understand the
problem statement completely.
 Ask questions for clarifying the doubts about the problem.
 Identify the problem types and use existing algorithm to find
solution. Input (instance) to the problem and range of the input
get fixed.
(ii) Decision making

Choosing between Exact and Approximate Problem Solving

 The principal decision is to choose between solving the

problem exactly or solving it approximately.
 ii. An algorithm used to solve the problem exactly and
produce correct result is called an exact algorithm.
  If the problem is so complex and not able to get exact
solution, then we have to choose an algorithm called an
approximation algorithm. i.e., produces an approximate
answer. E.g., extracting square roots, solving nonlinear
equations, and evaluating definite integrals.
(iii) Algorithm Design Techniques
1. An algorithm design technique (or “strategy” or “paradigm”) is a
general approach to solving problems algorithmically that is
applicable to a variety of problems from different areas of computing.
2. Algorithms+ Data Structures = Programs
3. Though Algorithms and Data Structures are independent, but they
are combined to develop program. Hence the choice of proper data
structure is required before designing the algorithm.
4. Implementation of algorithm is possible only with the help of
Algorithms and Data Structures
5. Algorithmic strategy / technique / paradigm is a general approach
by which many problems can be solved algorithmically. E.g., Brute
Force, Divide and Conquer, Dynamic Programming, Greedy
Technique and so on.

(iii) Methods of Specifying an Algorithm

There are three ways to specify an algorithm. They are:

a. Natural language

b. Pseudocode

c. Flowchart

Pseudocode and flowchart are the two options that are most widely used
nowadays for specifying algorithms.

a. Natural Language
It is very simple and easy to specify an algorithm using natural
language. But many times, specification of algorithm by using natural
language is not clear and thereby we get brief specification.
b. Pseudocode
 Pseudocode is a mixture of a natural language and
programming language constructs. Pseudocode is usually more precise
than natural language.
c. Flowchart
In the earlier days of computing, the dominant method for specifying
algorithms was a flowchart, this representation technique has proved
to be inconvenient. Flowchart is a graphical representation of an
algorithm. It is a method of expressing an algorithm by a collection of
connected geometric shapes containing descriptions of the algorithm‟s
steps.
(iv) Proving an Algorithm‟s Correctness Once an algorithm has been specified
then its correctness must be proved. An algorithm must yields a required
resultfor every legitimate input in a finite amount of time. Example:
Addition of for every legitimate input in a finite amount of time.
Example: Addition of a and b
Start
Input the value of a;
Input the value of b;
c: = a + b;
Display the value of c;
Stop
(v) Analyzing an Algorithm
For an algorithm the most important is efficiency. In fact, there are
two kinds of algorithm efficiency. They are:
Time efficiency, indicating how fast the algorithm runs, and
Space efficiency, indicating how much extra memory it uses.
The efficiency of an algorithm is determined by measuring both time
efficiency and space efficiency. So factors to analyze an algorithm are:
1. Time efficiency of an algorithm
2. Space efficiency of an algorithm
3. Simplicity of an algorithm
4. Generality of an algorithm
(vi) Coding an Algorithm coding/ implementation of an algorithm is done by
language like C, C++, JAVA.
1. The transition from an algorithm to a program can be done either
incorrectly or very inefficiently. Implementing an algorithm correctly
 is necessary. The Algorithm power should not reduce by inefficient
implementation.
2. Standard tricks like computing a loop‟s invariant (an expression that
does not change its value) outside the loop, collecting common sub
expressions, replacing expensive operations by cheap ones, selection
of programming language and so on should be known to the
programmer.
3. Typically, such improvements can speed up a program only by a
constant factor, whereas a better algorithm can make a difference in
running time by orders of magnitude. But once an algorithm is
selected, a 10–50% speedup may be worth an effort.
4. It is very essential to write an optimized code (efficient code) to
reduce the burden of compiler

Performance Analysis:

The efficiency of an algorithm can be in terms of time and space. The algorithm
efficiency can be analyzed by the following ways.

a) Analysis Framework.

b) Asymptotic Notations and its properties.

c) Mathematical analysis for Recursive algorithms.

d) Mathematical analysis for Non-recursive algorithms.

a) Analysis Framework: There are two kinds of efficiencies to analyze the

efficiency of any algorithm. They are:
Time efficiency, indicating how fast the algorithm runs, and
Space efficiency, indicating how much extra memory it uses.

The algorithm analysis framework consists of the following:

i. Measuring an Input‟s Size
ii. Units for Measuring Running Time
iii. Orders of Growth
iv. Worst-Case, Best-Case, and Average-Case Efficiencies
(i) Measuring an Input‟s Size: An algorithm‟s efficiency is defined as a function
of some parameter n indicating the algorithm‟s input size. In most cases,
selecting such a parameter is quite straightforward. For example, it will be the
size of the list for problems of sorting, searching.

(ii) Units for Measuring Running Time : Some standard unit of time
measurement such as a second, or millisecond, and so on can be used to
measure the running time of a program after implementing the algorithm.
Drawbacks :

a) Dependence on the speed of a computer.

b) Dependence on the quality of a program implementing the algorithm.

c) The compiler used in generating the machine code.

d) The difficulty of clocking the actual running time of the program.

So, we need metric to measure an algorithm‟s efficiency that does not depend
on these extraneous factors. One possible approach is to count the number of
times each of the algorithm‟s operations is executed. This approach is
excessively difficult. The most important operation (+, -, *, /) of the algorithm,
called the basic operation. Computing the number of times the basic operation is
executed is easy. The total running time is determined by basic operations
count.

(iii) Orders of Growth: A difference in running times on small inputs is not what
really distinguishes efficient algorithms from inefficient ones. For large values
of n, it is the function‟s order of growth that counts just like the Table 1.1,
which contains values of a few functions particularly important for analysis of
algorithms. Table 1.1 Growth of function order
Worst-Case, Best-Case, and Average-Case Efficiencies Consider linear oR
Sequential Search algorithm some search key K

ALGORITHM SequentialSearch(A[0..n - 1], X)

//Searches for a given value in a given array by sequential search

//Input: An array A[0..n - 1] and a search key X

//Output: The index of the first element in A that matches K or -1 if there

are no // matching elements

i ←0;

while i < n and A[i] ≠ X do

i ←i + 1;

if i < n return i

else return -1;

Clearly, the running time of this algorithm can be quite different for the same
list size n. In the worst case, there is no matching of elements or the first
matching element can found at last on the list. In the best case, there is matching
of elements at first on the list.

Worst-case efficiency

The worst-case efficiency of an algorithm is its efficiency for the worst case
input of size n. The algorithm runs the longest among all possible inputs of that
size. For the input of size n, the running time is Cworst(n) = n.

Best case efficiency

The best-case efficiency of an algorithm is its efficiency for the best case input
of size n. The algorithm runs the fastest among all possible inputs of that size n.
In sequential search, If we search a first element in list of size n. (i.e. first
element equal toa search key), then the running time is Cbest(n) = 1
Average case efficiency

The Average case efficiency lies between best case and worst case. To analyze
the algorithm‟s average case efficiency, we must make some assumptions about
possible inputs of size n.

Asymptotic notations

Asymptotic notation is a notation, which is used to take meaningful statement

about the efficiency of a program. The efficiency analysis framework
concentrates on the order of growth of an algorithm‟s basic operation count as
the principal indicator of the algorithm‟s efficiency. To compare and rank such
orders of growth, computer scientists use five notations, they are:

O - Big oh notation

Ω - Big omega notation

Θ - Big theta notation

o- Little oh notation

ω-Little omega notation

Asymptotically Non-Negative: A function g(n) is asymptotically nonnegative, if

g(n)>=0 for all n>=n0 where n0 in N={0,1,2,3,…}

Asymptotic Upper Bound: O(Big-oh)

Definition: Let f(n) and g(n) be asymptotically non-negative functions. We say

f (n) is in O ( g ( n )) if there is a real positive constant c and a positive Integer
n0 such that for every n >= n0 , 0 <=f (n) <= c * g (n ).

(Or)

O(g(n))= { f(n) | there exist a positive constant c and a positive integer n0

such that 0 <=f( n) <= c * g (n ) for all n >= n0 }

The Figure 1.1 shows the growth function of f(n) and g(n) for case of
asymptotic upper bound
Asymptotic Lower Bound: Ω(Big-Omega)

Definition:

Let f(n) and g(n) be asymptotically non-negative functions. We say f (n) is Ω ( g

( n )) if there is a positive real constant c and a positive integer n0 such that for
every n >= n0 0 <= c * g (n ) <= f ( n).

(Or)

Ω ( g ( n )) = { f (n) | there exist positive constant c and a positive integer n0

such that 0 <= c * g (n ) <= f ( n) for all n >= n0 }
Asymptotic Tightly Bound: θ(Theta)

Definition: Let f (n) and g(n) be asymptotically non-negative functions. We say

f (n) is θ( g ( n )) if there are positive constants c, d and a positive integer n0
such that for every n >=n0 0 <= c * g (n ) <= f ( n) <= d * g ( n ). (Or )

n0 θ (g(n))={f(n)|there exist positive constants c, d and a positive integer n0

such that 0 <= c * g (n ) <= f ( n) <= d * g ( n ). for all n >= n0 }
Calculating the running time of programs

Example:

Analysis of simple for loop

Now let’s consider a simple for loop:

for (i = 1; i<=n; i++)

v[i] = v[i] + 1;

This loop will run exactly n times, and because the inside of the loop takes
constant time, the total running time is proportional to n. We write it as O(n).
The actual number of instructions might be 50n, while the running time might
be 17n microseconds. It might even be 17n+3 microseconds because the loop
needs some time to start up. The big-O notation allows a multiplication factor
as well as an additive factor. As long as it‟s a linear function which is
proportional to n, the correct notation is O(n) and the code is said to have linear
running time.

Example:

Analysis for nested for loop

Now let‟s look at a more complicated example, a nested for loop:

for (i = 1; i<=n; i++)

for (j = 1; j<=n; j++)
a[i,j] = b[i,j] * x;

The outer for loop executes N times, while the inner loop executes n times for
every execution of the outer loop. That is, the inner loop executes n*n=n2 times.
The assignment statement in the inner loop takes constant time, so the running
time of the code is O(n2) steps. This piece of code is said to have quadratic
running time.

Example:

Analysis of matrix multiply

Let‟s start with an easy case , Multiply two n*n matrices. The code to compute
the matrix product C = A * B is given below

for (i = 1; i<=n; i++)

for (j = 1; j<=n; j++)
C[i, j] = 0;
for (k = 1; k<=n; k++)
C[i, j] = C[i, j] + A[i, k] * B[k, j];

There are 3 nested for loops, each of which runs n times. The innermost loop
therefore executes n*n*n = n3 times. The innermost statement, which contains a
scalar sum and product takes constant O(1) time. So the algorithm overall takes
O(n3) time.

Example : Analysis of bubble sort

The main body of the code for bubble sort looks something like this:
for (i = n-1; i<1; i--)
for (j = 1; j<=i; j++)
if (a[j] > a[j+1])
swap a[j] and a[j+1];

This looks like the double. The innermost statement, the if, takes O(1) time. It
doesn‟t necessarily take the same time when the condition is true as it does
when it is false, but both times are bounded by a constant. But there is an
important difference here. The outer loop executes n times, but the inner loop
executes a number of times that depends on i. The first time the inner for
executes, it runs i = n-1 times. The second time it runs n-2 times, etc. The total
number of times the inner if statement executes is therefore:

(n-1) + (n-2) + ... + 3 + 2 + 1

This is the sum of an arithmetic series.

The value of the sum is n(n-1)/2. So the running time of bubble sort is O(n(n-
1)/2), which is O((n2-n)/2). Using the rules for big-O given earlier, this bound
simplifies to O((n2)/2) by ignoring a smaller term, and to O(n2), by ignoring a
constant factor. Thus, bubble sort is an O(n2) algorithm.
Example: Analysis of binary search

Binary search is a little harder to analyze because it doesn‟t have a for loop. But
it‟s still pretty easy because the search interval halves each time we iterate the
search. The sequence of search intervals looks something like this:

n, n/2, n/4, ..., 8, 4, 2, 1

It‟s not obvious how long this sequence is, but if we take logs, it is: log2n,
log2 n - 1, log2n - 2, ..., 3, 2, 1, 0

Since the second sequence decrements by 1 each time down to 0, its length must
be log2 n + 1. It takes only constant time to do each test of binary search, so the
total running time is just the number of times that we iterate, which is log2n + 1.
So binary search is an O(log2 n) algorithm. Since the base of the log doesn‟t
matter in an asymptotic bound, we can write that binary search is O(log n).

General rules for the analysis of programs

In general the running time of a statement or group of statements may be

parameterized by the input size and/or by one or more variables. The only
permissible parameter for the running time of the whole program is „n‟ the input
size.

1. The running time of each assignment read and write statement can
usually be taken to be O(1). (There are few exemptions, such as in PL/1,
where assignments can involve arbitrarily larger arrays and in any
language that allows function calls in arraignment statements).

2. The running time of a sequence of statements is determined by the sum

rule. I.e. the running time of the sequence is, to with in a constant factor,
the largest running time of any statement in the sequence.

3. The running time of an if–statement is the cost of conditionally executed

statements, plus the time for evaluating the condition. The time to
evaluate the condition is normally O(1) the time for an if–then–else
construct is the time to evaluate the condition plus the larger of the time
 needed for the statements executed when the condition is true and the
time for the statements executed when the condition is false.

4. The time to execute a loop is the sum, over all times around the loop, the
time to execute the body and the time to evaluate the condition for
termination (usually the latter is O(1)). Often this time is, neglected
constant factors, the product of the number of times around the loop and
the largest possible time for one execution of the body, but we must
consider each loop separately to make sure.

STUDY SEARCHING AND SORTING TECHNIQUE WITH

IMPLEMENTATION