Analysis-of-Algorithms-and-Researching-Computing-munotes

Page 1

1Chapter 1: Design Strategies - Role of Algorithm
Unit I
1 DESIGN STRATEGIES
ROLE OF ALGORITHM
Unit Structure
1.0 Objective
1.1 Introduction
1.2 The Role of Algorithms in Computing
1.2.1 Algorithms
1.2.2 Algorithms as a technology
1.3 Getting Started
1.3.1 Insertion sort
1.3.2 Analyzing algorithms
1.3.3 Designing algorithms
1.4 Growth of Functions
1.4.1 Asymptotic notation
1.4.2 Standard notations and common functions
1.6 Let us Sum Up
1.7 List of References
1.8 Exercises



munotes.in

Page 2

2ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING
1.0 Objective
After going through this unit, you will be able to:
• What is an algorithm?
• What is the need of algorithm?
• What is the role of algorithm in computing?
• How to analyse algorithm?
• How to design an algorithm?
• What is Growth function?
• List of standard notation and common functions?
1.1 Introduction
In this chapter, you will learn what is an algorithm and its importance in computer
technologies. It covers some suitable examples as well. Along with we will get the
idea about growth function , standard notations and functions which are addit ional
interesting ingredient s of the algorithm s.
1.2 The Role of Algorithms in Computing
1.2.1 Algorithms
Algorithm is step by step procedure which takes input value, process it or
apply some computation al techniques and produce some output value. In
another way we can state the algorithm as a list of steps which transform the
input to output using some processing function. We can also consider
algorithm is a tool for solving some computational problems. Algorithm sta te
the relationship of input and output.



Fig1: Illustration of Algorithm Input Output Algorithm munotes.in

Page 3

3Chapter 1: Design Strategies - Role of Algorithm
For example – if we need to sort the numbers in ascending order then it requires
the formulate the problem as follows:
Input: A sequence of n numbers ( n1,n2,n3,…,nn )
Output: (n1’,n2’,n3’,…,nn’ ) such that n1’ <=n2’ <=…<=nn’ )
Now we can take one example to solve this problem with numerical values.
So, the input is (5,2,4,6,1), and after sorting the output should be (1,2,4,5,6). Input
sequence is called as instance of a problem.
An algorithm is to accurate if for every input it halts with the accurate output. We
can use flowchart to represent the sequence of steps i n pictorial form.
Characteristics of Algorithm
The Algorithm designed is language independent, i.e. they are just plain
instructions set that can be implemented in any language, and the output will be
the same, as expected.
Following are the key characteristics of algorithm -
• Well -Defined Inputs : If an algorithm says to take inputs instance , it should
be clear that which type of inputs in required for processing .
• Well -Defined Outputs: The algorithm must clearly define that what type
of output will be generated.
• Finiteness: The algorithm should not end up in an infinite loop .
• Feasib ility: The algorithm must be generic and practical, such that it can
be executed upon available resources.
• Language Independent: It must be just plain instruc tions set that can be
implemented in any language, and yet the output will be same, as expected.
1.3 Algorithms as a technology
Consider the scenario, computers were tremendously fast and memory of computer
was free as well . You would still like to prove that your solution method terminates
with the correct answer. If computers were tremendously fast, any accurate method
for solving a problem would give accurate result . munotes.in

Page 4

4ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING
Every implementation should be in the proper bounded softwar e engineering
practice environment. But as a human being, we use to like to work on simple and
easiest method to implement the solution for problem. As if we consider that
computer is very fast but not infinite fast and memory also the integral part of
scenario as memory costing is also very expensive .
So, c omputing time is a bounded resource, and so is space in memory. You should
use these resources sensibly or as per your project need , and algorithms that are
efficient in terms of time or space will help you do so.
Algorithms and other technologies
As algorithm should be effective and correct algorithm selection is the art and for
implementation purpose, selection of hardware is also important part. As
technological changes are happened at every single d ay and which help us to do
our work more effectively. Algorithm is also get the similar importance as it save
your reverse engineering or reframing the implementation of problem. Ultimately
it helps for different technologies to take proper decision such a s web technology,
networking, wired and wireless network; etc.
1.4 Getting Started
1.3.1 Insertion sort
First algorithm is insertion sort. It is just like playing cards game as you can insert
the card in between two cards and make the sequence. The logic is to arrange list
in ascending order using insertion sort.
Input: A sequence of n numbers ( n1,n2,n3,…,n n)
Output: (n1’,n2’,n3’,…,nn’ ) such that n1’<=n2’<=…<=nn’)
So, firstly we have our number in the form of array with size n and the numbers we
need to sort can be called as keys . We can implement it in any language but in this
chapter, we will illustrate it using C programming language. In insertion sort,
procedure should be follow in following steps – munotes.in

Page 5

5Chapter 1: Design Strategies - Role of Algorithm
Pseudo code
Insertion _Sort(Arr)
For j = 2 to Arr.length
key =Arr[j]
i = j-1
while( i > 0 and Arr[i] > key)
Arr[i+1] = Arr[i]
i =i – 1
Arr[i+1] = key
Loop invariants help us to check the algorithm is correct understand why an
algorithm is correct. We must show three things about a loop invariant:
• Initialization: It is first iteration of the loop.
• Maintenance: If it is true before an iteration of the loop, it remains true before
the next iteration.
• Termination: When the loop terminates, the invariant gives us a useful
property that helps show that the algorithm is cor rect.
For example –
22, 21, 23, 15, 16
Let us loop for i = 1 (second element of the array) to 4 (last element of the array)
i = 1 . Since 21 is smaller than 22, move 22 and insert 21 before 22
21, 22, 23, 15, 16
i = 2. 23 will remain at its position as all elements in A[0..i -1] are smaller than 23
21, 22, 23, 15, 16
i = 3. 15 will move to the beginning and all other elements from 21 to 23 will
move one position ahead of their current position.
15, 21, 22, 23, 16 munotes.in

Page 6

6ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING
i = 4. 16 will move to position after 15, and elements from 21 to 23 will move
one position ahead of their current position.
15, 16, 21, 22, 23
Program –
void insertionSort(int a 1[], int n)
{
int i, key, j;
for (i = 1; i < n; i++) {
key = a 1[i];
j = i - 1;
/* Move elements of a 1[0..i-1], that are greater than key, to one
position ahead
of their current position */
while (j >= 0 && a 1[j] > key) {
a1[j + 1] = a 1[j];
j = j - 1;
}
a1[j + 1] = key;
}
}
Pseudocode conventions
We use the following conventions in our pseudocode. Indentation indicates block
structure. For example,
1. the body of the for loop that begins on line 1 consists of lines 2 –8
2. body of the while loop that begins on line 5 contains lines 6 –7 but not line 8.
Our indentation style applies to if -else statements2 as well. Using indentation
instead of conventional indicators of block structure, such as begin and end munotes.in

Page 7

7Chapter 1: Design Strategies - Role of Algorithm
statements, greatly reduces clutter while preserving, or even enhancing, clarity. The
looping constr ucts while, for, and repeat -until and the if -else conditional construct
have interpretations similar to those in C, C++, Java, Python, and Pascal.
1.3.2 Analyzing algorithms
Analysing an algorithm mean s predicting the required resources for the solving
problem statement . Resources means computer hardware such as memory, bandwidth and communication channel. But the majorly computer hardware used
for solving problem statement is primary concern, but most often it is computational time that we want to measure.
Generally, we used to do analysis of several algorithm and then pick up the efficient
one. It is our practice to check whether we are using right algorithm or not . Before
we can analyze an algorithm, we must have a model of the implementation
technology that we will use, including a model for the resources of that technology
and their costs.
Most of times, we shall assume a generic one processor, random -access machine
(RAM) model of computation as our implementation technology and understand
that our alg orithms will be implemented as computer programs. In the RAM model,
instructions are executed one after another, with no concurrent operations.
So, following example will gives you the detail idea about how to analyse the
problem and how the algorithm plays important role to solve the problem.
Analysis of insertion sort
Following program will gives you the idea about insertion sort.
void insertionSo rt(int a 1[], int n)
{
int i, key, j;
for (i = 1; i < n; i++) {
key = a 1[i];
j = i - 1;
/* Move elements of a 1[0..i-1], that are greater than key, to one
position ahead munotes.in

Page 8

8ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING
of their current position */
while (j >= 0 && a 1[j] > key) {
a1[j + 1] = a 1[j];
j = j - 1;
}
a1[j + 1] = key;
}
}
Observations are –
1. Its total time requires is based on number of inputs. (sorting 5 numbers will take
less time as compare to sorting 50 numbers)
2. If the size of array or list is same but some number of the first list is sorted and
another list is fully unsorted then first list will take less time as compare to
whole unsorted list.
3. The time taken by an algorithm raises with the size of the input, so it is
traditional to define the running time of a program as a function of the size of
its input.
4. So, most important part of analysis is “running time” and “size of input”.
5. The running time of an algorithm on a particular input is the number of
primitive processes or “steps” executed.
6. It is suitable to define the notion of step so that it is as machine -independent as
possible.
Analysis of bubble sort
The main body of the code for bubble sort looks something like this:
for (i = n -1; i<=i; j++)
if (a[j] > a[j+1])
swap a[j] and a[j+1]; munotes.in

Page 9

9Chapter 1: Design Strategies - Role of Algorithm
Observations are -
1. This looks like the double. The innermost statement, the if, takes O(1) time. It
GRHVQெWQHFHVVDUL ly 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.
2. 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.
1.3.3 Designing algorithms
We can choose from a wide range of algorithm design techniques.
Design techniques are –
1. Brute force/ Exhaustive search
2. Divide and Conquer
3. Transformation
4. Dynamic programming
5. Greedy programming
6. Iterative improvement/ incremental approach
7. Randomization
munotes.in

Page 10

10ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING
For insertion sort, we used an incremental approach: having sorted the subarray
A[1 .. j – 1], we inserted the single element A [j] into its proper place, yielding the
sorted subarray A [1.. j].
The divide and conquer approach
Many algorithm has different designing techniques like merge sort or quick sort
has recursive structure. So, the observation is –
1. Many algorithms are recursive in structure: to solve a given problem, they call themselves recursively one or more times to deal with closely related subproblems.
2. These algorithms follow a divide -and-conquer approach: they break the
problem into several s ubproblems that are similar to the original problem but
smaller in size, solve the subproblems recursively, and
3. Combine these solutions to create a solution to the original problem.
The divide -and-conquer paradigm involves three steps at each level of th e
recursion:
1. Divide the problem into a number of subproblems that are smaller instances of
the same problem.
2. Conquer the subproblems by solving them recursively. If the subproblem sizes
are small enough, however, just solve the subproblems in a straightforward
manner.
3. Combine the solutions to the subproblems into the solution for the original
problem. 5 2 3 1 4 7 9 8 6 10

1 2 3 4 5 6 7 8 9 10 munotes.in

Page 11

11Chapter 1: Design Strategies - Role of Algorithm

The merge sort algorithm closely follows the divide -and-conquer paradigm. Intuitively, it operates as follows.
• Divide: Divide the n -element sequence to be sorted into two sub -sequences of n=2 elements each.
• Conquer: Sort the two sub -sequences recur sively using merge sort.
• Combine: Merge the two sorted sub -sequences to produce the sorted answer

1.5 Growth of Functions
Growth function g ives a simple description of the algorithm’s efficiency and also
allows us to compare the relative performance of alternative algorithms. Following
steps need to consider –
1. Once the input size n becomes large enough, merge sort, with its ‚ șnlg n)
worst -case running time, beats in sertion sort, whose worst -case running time is
șn2).
2. The extra precision is not usually worth the effort of computing it.
3. For large enough inputs, the multiplicative constants and lower -order terms of
an exact running time are dominated by the effects of the input size itself.
munotes.in

Page 12

12ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING
4. When we look at input sizes large enough to make only the order of growth of
the running time relev ant, we are studying the asymptotic efficiency of
algorithms.
That is, we are concerned with how the running time of an algorithm increases with
the size of the input in the limit, as the size of the input increases without bound.
Usually, an algorithm tha t is asymptotically more efficient will be the best choice
for all but very small inputs.
Complexity of Algorithms
The complexity of an algorithm M is the function f(n) which gives the running time
and/or storage space necessity of the algorithm in terms of the size n of the input
data. The storage space essential by an algorithm is simply a multiple of the data
size n.
Complexity shall refer to the running time of the algorithm. The function f(n), gives
the running time of an algorithm, depends not only on the size n of the input data
but also on the particular data.
The complexity function f(n) for certain cases are:
1. Best Case : The minimum possible value of f(n) is called the best case.
2. Average Case : The expected value of f(n).
3. Worst Case : The maximum value of f(n) for any key possible input.
The field of computer science, which studies efficiency of alg orithms, is known as
analysis of algorithms. Algorithms can be evaluated by a variety of criteria. Most
often we shall be interested in the rate of growth of the time or space required to
solve larger and larger instances of a problem. We will associate wi th the problem
an integer, called the size of the problem, which is a measure of the quantity of
input data. 1.4.1 Asymptotic notation
The notations we use to define the asymptotic running time of an algorithm are
defined in terms of functions whose domains are the set of natural numbers
N={0,1,2,…}.
Such notations are suitable for describing the worst -case running -time function
T(n), which frequently is defined only on integer input sizes. We sometimes find it
convenient, however, to abuse asymptotic notation i n a variation of ways. munotes.in

Page 13

13Chapter 1: Design Strategies - Role of Algorithm
For example, we might extend the notation to the domain of real numbers or,
alternatively, restrict it to a subset of the natural numbers. We should make sure,
however, to understand the precise meaning of the notation so that when we abuse,
we do not misuse it.
This section defines the basic asymptotic notations and also presents some common
abuses. The following notations are commonly use notations in performance
analysis and used to characterize the complexity of an algorithm:
 Big–OH (O) 1,
 Big–OMEGA (Ÿ),
 Big–THETA ( ș) and
 Little –OH (o)
1. Big-OH (Upper Bound)
IQ 2JQ (pronounced order of or big oh), says that the
growth rate of f(n) is less than or equal ( <) that of g(n).

2. Big OMEGA Ÿ (Lower Bound)
IQ ŸJQ(pronounced omega), says that the growth rate of f(n) is greater
than or equal to ( >) that of g(n).
munotes.in

Page 14

14ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

In 1892, P. Bachmann invented a notation for characterizing the asymptotic behaviour of functions. His invention has come to be known as big oh notation . 3. Big-THETA ș6DPHRUGHU
IQ șJQ(pronounced theta), says that the growth rate of f(n) equals (=) the
growth rate of g(n) [if f(n) = O(g(n)) and T(n) = Ÿ (g(n)].
4. Little -OH (o)
7Q RSQ (pronounced little oh), says that the growth rate of T(n) is less
than the growth rate of p(n) [if T(n) = O(p(n)) and T(n) ș(p(n))].
1.4.2 Standard notations and common functions.
Monotonicity
1. A function f(n) is PRQRWRQLFDOO\LQFUHDVLQJ if m ” n implies f(m) ” f(n).
2. Similarly, it is PRQRWRQLFDOO\GHFUHDVLQJ if m ” n implies f(m) • f(n).
3. A function f(n) is VWULFWO\ LQFUHDVLQJ if m < n implies f(m) < f(n) and VWULFWO\
GHFUHDVLQJ if m < n implies f(m) > f(n).


munotes.in

Page 15

15Chapter 1: Design Strategies - Role of AlgorithmFloors and ceilings For any real number x, we denote the greatest integer less than or equal to x by ہxۂ (read "the floor of x") and the least integer greater than or equal
to x by ڿxۀ (read "the ceiling of x").
For all real x, (3.3) For any integer n,
ڿn/2ۀ + ہn/2ۂ = n,
and for any real number n • 0 and integers a, b > 0, (3.4) (3.5) (3.6) (3.7) The floor function f(x) = ہxۂ is monotonically increasing, as is the ceiling function f(x) = ڿxۀ.
Modular arithmetic
For any integer a and any positive integer n, the value a mod n is
the UHPDLQGHU (or UHVLGXH) of the quotient a/n: (3.8) Given a precise notion of the remainder of one integer when divided by another, it
is convenient to provide special notation to specify equality of remainders.
If (a mod n) = (b mod n), we write a Ł b (mod n) and say that a is HTXLYDOHQW to b,
modulo n. In other words, a Ł b (mod n) if a and b have the same remainder when
divided by n. Equivalently, a Ł b (mod n) if and only if n is a divisor of b - a.
We write a ء b (mod n) if a is not equivalent to b, modulo n.

munotes.in

Page 16

16ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING
Polynomials
Given a nonnegative integer d, a SRO\QRPLDOLQQRIGHJUHHG is a function p(n) of
the form

• where the constants a0, a1, ..., ad are the FRHIILFLHQWV of the polynomial and ad  0. A polynomial is asymptotically positive if and only if ad > 0.
• For an asymptotically positive polynomial p(n) of degree d, we have p(n)
= Ĭ(nd).
• For any real constant a • 0, the function na is monotonically increasing, and for
any real constant a ” 0, the function na is monotonically decreasing.
We say that a function f(n) is SRO\QRPLDOO\ ERXQGHG if f(n) = O(nk) for some
constant k.
Exponentials
For all real a > 0, m, and n, we have the following identities: a0 = 1, a1 = a, a-1 = 1/a, (am)n = amn, (am)n = (an)m, am an = am+n. For all n and a • 1, the function an is monotonically increasing in n. When convenient, we shall assume 00 = 1.
The rates of growth of polynomials and exponentials can be related by the
following fact. For all real constants a and b such that a > 1, (3.9)
from which we can conclude that
nb = o(an).
munotes.in

Page 17

17Chapter 1: Design Strategies - Role of Algorithm
Thus, any exponential function with a base strictly greater than 1 grows faster than
any polynomial function.
Using e to denote 2.71828..., the base of the natural logarithm function, we have
for all real x, (3.10)
where "!" denotes the facto rial function defined later in this section. For all real x,
we have the inequality (3.11) where equality holds only when x = 0. When | x| ” 1, we have the approximation (3.12) When x ĺ 0, the approximation of ex by 1 + x is quite good:
ex = 1 + x + Ĭ(x2).
(In this equation, the asymptotic notation is used to describe the limiting behavior
as x ĺ 0 rather than as x ĺ ’.) We have for all x, (3.13)

Logarithms
We shall use the following notations: lg n = log2 n (binary logarithm) , ln n = loge n (natural logarithm) , lgk n = (lg n)k (exponentiation) , lg lg n = lg(lg n) (composition) . An important notational convention we shall adopt is that logarithm functions will
apply only to the next term in the formula , so that lg n + k will mean (lg n) + k and
not lg( n + k). If we hold b > 1 constant, then for n > 0, the function log b n is strictly
increasing.

munotes.in

Page 18

18ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING
For all real a > 0, b > 0, c > 0, and n, (3.14)
(3.15)
where, in each equation above, logarithm bases are not 1.
By equation (3.14) , changing the base of a logarithm from one constant to another
only changes the value of the logarithm by a constant factor, and so we shall often
use the notation "lg n" wh en we don't care about constant factors, such as in O-
notation. Computer scientists find 2 to be the most natural base for logarithms
because so many algorithms and data structures involve splitting a problem into
two parts.
There is a simple series expans ion for ln(1 + x) when | x| < 1:

We also have the following inequalities for x > -1: (3.16)
where equality holds only for x = 0.
We say that a function f(n) is SRO\ORJDULWKPLFDOO\ERXQGHG if f(n) = O(lgk n) for
some constant k. We can relate the growth of polynomials and polylogarithms by
substituting lg n for n and 2a for a in equation (3.9) , yielding

From this limit, we can conclude that
lgb n = o(na)
munotes.in

Page 19

19Chapter 1: Design Strategies - Role of Algorithm
for any constant a > 0. Thus, any positive polynomial function grows faster than
any polylogarithmic function.
Factorials
The notation n! (read " n factorial") is defined for integers n • 0 as

Thus, n! = 1 · 2 · 3 n.
A weak upper bound on the factorial function is n! ” nn, since each of the n terms
in the factorial product is at most n. 6WLUOLQJ
VDSSUR[LPDWLRQ , (3.17)
where e is the base of the natural logarithm, gives us a tighter upper bound, and a
lower bound as well . (3.18)
where Stirling's approximation is helpful in proving equation (3.18) . The following
equation also holds for all n • 1: (3.19)
where (3.20)

Functional iteration
We use the notation f(i)(n) to denote the function f(n) iteratively applied i times to
an initial value of n. Formally, let f(n) be a function over the reals. For nonnegative
integers i, we recursively define

For example, if f(n) = 2 n, then f(i)(n) = 2in.
munotes.in

Page 20

20ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING
The iterated logarithm function
We use the notation lg* n (read "log star of n") to denote the iterated logarithm,
which is defined as follows. Let lg(i) n be as defined above, with f(n) = lg n. Because
the logarithm of a nonpositive number is undefined, lg(i) n is defined only if lg(i-
1) n > 0. Be sure to distinguish lg(i) n (the logarithm function applied i times in
succession, starting with argument n) from lgi n (the logarithm of n raised to the ith
power). The iterated logarithm function is defined as
lg* n = min { i = 0: lg(i) n ” 1}.
The iterated logarithm is a very slowly growing function: lg* 2 = 1, lg* 4 = 2, lg* 16 = 3, lg* 65536 = 4, lg*(265536) = 5. Since the number of atoms in the observable universe is estimated to be about 1080,
which is much less than 265536, we rarely encounter an input size n such that
lg* n > 5.
)LERQDFFLQXPEHUV 
The )LERQDFFLQXPEHUV are defined by the following recurrence: (3.21)
Thus, each Fibonacci number is the sum of the two previous ones, yielding the
sequence
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... .
Fibonacci numbers are related to the JROGHQUDWLR ij and to its conjugate , which
are given by the following formulas:
munotes.in

Page 21

21Chapter 1: Design Strategies - Role of Algorithm(3.22)
Specifically, we have (3.23)
which can be proved by induction . Since , we have , so
that the ith Fibonacci number Fi is equal to rounded to the nearest integer.
Thus, Fibonacci numbers grow exponentially.
1.6 Let us Sum Up
In this chapter , we have learn the concept of Algorithm, characteristics of algorithm, asymptotic notation and standard functions. As per given in the
“Introduction to Algorithm” book by CORMEN’s, all authors define the asymptotic notations in the different way, although the various descriptions settle
in most common situations. Some of the substitute definitions include functions
that are not asymptotically nonnegative, as long as their absolute values are
appropriately bounded.
1.7 List of References
1. Introduction to Algorithms, Third Edition, Thomas H. Cormen, Charles E.
Leiserson, Ronald L. Rivest, Clifford Stein, PHI Learning Pvt. Ltd -New
Delhi (2009).
2. https://www.javatpoint.com/ algorithms -and-functions
3. Dr. L. V. N. Prasad, Professor, lecture notes on Design And Analysis Of
Algorithms
4. http://serverbob.3x.ro/IA/DDU0020.html#!/stealingyourhisto ry


munotes.in

Page 22

22ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING
1.8 Bibliography
Exercises
1. Calculate the analysis of simple for loop
for (i = 1; i<=n; i++)
v[i] = v[i] + 1;
2. Calculate analysis of matrix multiply
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];
3. Suppose we are comparing implementations of insertion sort and merge sort
on the same machine. For inputs of size n, insertion sort runs in 8n2 steps,
while merge sort runs in 64n lg n steps. F or which values of n does insertion
sort beat merge sort?
4.What is the smallest value of n such that an algorithm whose running time is
100n2 runs faster than an algorithm whose running time is 2n on the same
machine?
munotes.in

Page 23

23Chapter 2: Divide and Conquer and Randomized Algorithm
Unit I
2 DESIGN STRATEGIES
DIVIDE AND CONQUER AND
RANDOMIZED ALGORITHM
Unit Structure
1.0 Objective
2.1 Introduction
2.2 Divide -and-Conquer
2.2.1 The maximum -subarray problem
2.2.2 Strassen’s algorithm for matrix multiplication
2.2.3 The substitution method for solving recurrences
2.3 Probabilistic Analysis and Randomized Algorithms
2.3.1 The hiring problem
2.3.2 Indicator random variables
2.3.3 Randomized algorithms
2.4 Let us Sum Up
2.5 List of references
2.6 Bibliography
2.7 Exercise
2.0 Objective
After going through this unit, you will be able to:
• What is divide and conquer concept ?
• What is the need of Probabilistic algorithm?
• What is Randomized Algorithms ? munotes.in

Page 24

24ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING2.1 Introduction In this chapter, we will learn more algorithms based on divide -and-conquer. The first one solves the maximum-subarray problem: it is takings as input an array of numbers, and it determines the contiguous subarray whose values have the greatest sum. Then we shall see two divide-and-conq uer algorithms for multiplying n x n matrices. We can also learn Strassen’s algorithm, probabilistic Analysis and randomised algorithm. 2.2 Divide -and-Conquer Divide and conquer is a design algorithm technique which is well known to breaking down efficiency barriers. Divide and conquer algorithm consists of three parts: Divide: Divide the problem into sub problems. The sub problems are solved recursively. Conquer: The solution to the original problem is then formed from the solutions to the sub problems (patching together the answers). Combine: Combine the solutions to the subproblems into the solution for the original problem. Traditionally, routines in which the text contains at least two recursive calls are called divide and conquer algorithms, while routines whose text contains only one recursive call are not. Divide–and–conquer is a very powerful use of recursion. When the subproblems are large enough to solve recursively, we call that the recursive case. Once the subproblems become small enough that we no longer recurse, we say that the recursion “bottoms out” and that we have gotten down to the base case. Sometimes, in addition to subproblems that are smaller instances of the same problem, we have to solve subproblems that are not quite the same as the original problem. We consider solving such subproblems as part of the combine step. Recurrences Recurrences go hand in hand with the divide-and-conquer paradigm, because they give us a natural way to characterize the running times of divide -and-conquer algorithms. A recurrence is an equation or inequality that describes a function in munotes.in

Page 25

25Chapter 2: Divide and Conquer and Randomized Algorithm
terms of its value on smaller inputs. For example, the worst -case running time T (n)
of the MERGE -SORT procedure by the recurrence .

whose solution we claimed to be

There are 3 methods to solving recurrences
1. In the substitution method, we guess a bound and then use mathematical
induction to prove our guess correct.
2. The recursion -tree method converts the recurrence into a tree whose nodes represent the costs incurred at various levels of the recursion. We use techniques for bounding summations to solve the recurrence.
3. The master method provides bounds for recurrences of the form. It is used to
determine the running times of the divide -and-conquer algorithms for the
maximum -subarray problem and for matrix multi plication .
2.2.1 The maximum -subarray problem
As we can consider problem of maximum subarray sum. The problem of maximum
subarray sum is basically finding the part of an array whose elements has the largest
sum. If all the elements in an array are positive then it is easy, find the sum of all
the elements of the array and it has the largest sum over any other subarrays you
can make out from that array.
For example – 2,1,4,3,5
Maximum sum = 2+1+4+3+5 = 15
But the problem gets more interesting when so me of the elements are negative then
the subarray whose sum of the elements is largest over the sum of the elements of
any other subarrays of that element can lie anywhere in the array.
For example – 2,-1,4,-3,5
Maximum sum = 2 -1+4-3+5 = 7

munotes.in

Page 26

26ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING
Brute force sol ution
The Brute Force technique to solve the problem is simple. Just iterate through every
element of the array and check the sum of all the subarrays that can be made starting
from that element i.e., check all the subarrays and this can be done in nC2 ways i.e.,
choosing two different elements of the array to make a subarray. Thus, the brute
IRUFHWHFKQLTXHLVRIĬQWLPH+RZHYHU ZHFDQVROYHWKLVLQĬQORJQWLPH
using divide and conquer.
As we know that the divide and conquer solves a problem by breaking into
subproblems, so let's first break an array into two parts. Now, the subarray with
maximum sum can either lie entirely in the left subarray or entirely in the right
subarray or in a subarray consisting both i.e., crossing the middle element .

The first two cases where the subarray is entirely on right or on the left are
actually the smaller instances of the original problem. So, we can solve them
recursively by calling the function to calculate the maximum sum subarray on
both the parts.
Max_sum_subarray(array, low, high)
{
if (high == low) // only one element in an array
{
return array[high]
}
mid = (high+low)/2
Max_sum_subarray(array, low, mid)
Max_sum_subarray(array, mid+1, high)
}
munotes.in

Page 27

27Chapter 2: Divide and Conquer and Randomized Algorithm
We are making Max_sum_subarray is a function to calculate the maximum sum
of the subarray in an array. Here, we are calling the
function Max_sum_subarray for both the left and the right subarrays i.e.,
recursively checking the left and the right subarrays for the maximum sum
subarray.
Now, we have to handle the third case i.e., when the subarray with the maximum
sum contains both the right and the left subarrays (containing the middle
element). At a glance, this could look like a smaller instance of the original
problem also but it is not because it contains a restriction that the subarray must
contain the middle element and thus makes our problem much more narrow and
less time taking.
So, we will now make a function called Max_crossing_subarray to calculate the
maximum sum of the subarray crossing the middle element and then call it
inside the Max_sum_subarray function.
max_sum_subarray(array, low, high)
{
if (high == low) // only one element in an array
{
return array[high];
}
mid = (high+low)/2;
maximum_sum_left_subarray = max_sum_subarray(array, low, mid)
maximum_sum_right_subarray = max_sum_subarray(array, mid+1, high)
maximum_sum_crossing_subarray = max_crossing_subarray(array, low, mid,
high);
// returning the maximum among the above thr ee numbers
return maximum(maximum_sum_left_subarray, maximum_sum_right_subarray,
maximum_sum_crossing_subarray);
} munotes.in

Page 28

28ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING
Here, we are covering all three cases mentioned above to and then just returning
the maximum of these three.
Now, let's write the max_crossing_subarray function.
The max_crossing_subarray function is simple, we just have to iterate over the
right and the left sides of the middle element and find the maximum sum.
max_crossing_subarray(int ar[], int low, int mid, int high) {
left_sum = -infinity
sum = 0
for (i=mid downto low)
{
sum = sum+ar[i]
if (sum>left_sum)
left_sum = sum
}
right_sum = -infinity;
sum = 0
for (i=mid+1 to high)
munotes.in

Page 29

29Chapter 2: Divide and Conquer and Randomized Algorithm
{
sum=sum+ar[i]
if (sum>right_sum)
right_sum = sum
}
return (left_sum+right_sum)
}
Here, our first loop is iterating from the middle element to the lowest element of
the left subarray to find the maximum sum and similarly the second loop is iterating
from the middle+1 element to the highest element of the subarray to calculate the
maximum sum of the subarray on the right side. An d finally, we are returning
summing both of them and returning the sum which is calculated from the subarray
crossing the middle element.
2.2.2 Strassen’s algorithm for matrix multiplication
The matrix multiplication of algorithm due to Strassens is the mo st dramatic
example of divide and conquer technique (1969). The usual way to multiply two n
x n matrices A and B, yielding result matrix C as follows :
for i := 1 to n do
for j :=1 to n do
c[i, j] := 0;
for K: = 1 to n do
c[i, j] := c[i, j] + a[i, k] * b[k, j];
7KLVDOJRULWKPUHTXLUHVQVFDODUPXOWLSOLFDWLRQெVLHPXOWLSOLFDWLRQRIVLQJOH
numbers) and n3 scalar additions. So we naturally cannot improve upon. We apply divide and conquer to this problem. For example let us considers three multiplic ation like this:

munotes.in

Page 30

30ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING
Then Cij can be found by the usual matrix multiplication algorithm,

This leads to a divide –and–conquer algorithm, which performs nxn matrix
multiplication by partitioning the matrices into quarters and performing eight
(n/2)x(n/2) matrix multiplications and four (n/2)x(n/2) matrix additions.

Which leads to T (n) = O (n3), where n is the power of 2. Strassens insight was to
find an al ternative method for calculating the Cij, requiring seven (n/2) x (n/2)
matrix multiplications and eighteen (n/2) x (n/2) matrix additions and subtractions:

This method is used recursively to perform the seven (n/2) x (n/2) matrix
multiplications, then the recurrence equation for the number of scalar multiplications performed is:
munotes.in

Page 31

31Chapter 2: Divide and Conquer and Randomized Algorithm

6RFRQFOXGLQJWKDW6WUDVVHQெV algorithm is asymptotically more efficient than the
standard algorithm. In practice, the overhead of managing the many small matrices
GRHVQRWSD\RIIXQWLOÄQெUHYROYHVWKHKXQGUHGV
2.2.3 The substitution method for solving recurrences
One way to solve a divide -and-conquer recurrence equation is to use the iterative
VXEVWLWXWLRQPHWKRG7KLVLVD³SOXJ -and-FKXJ´PHWKRG,QXVLQJWKLVPHWKRGZH
assume that the problem size n is fairly large and we than substitute the general
form of the recurrence for each occurrence of the function T on the right -hand side.
For example, performing such a substitution with the merge sort recurrence
equation yields the equation.
T(n) = 2 (2 T(n/22 ) + b (n/2)) + b n
= 22 T(n/22 ) + 2 b n
Plugging the general equati on for T again yields the equation.
T(n) = 22 (2 T(n/23 ) + b (n/22 )) + 2 b n
= 23 T(n/23 ) + 3 b n
munotes.in

Page 32

32ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING
The hope in applying the iterative substitution method is that, at some point, we
will see a pattern that can be converted into a general closed -form equ ation (with
T only appearing on the left -hand side). In the case of merge -sort recurrence
equation, the general form is:
T(n) = 2i T (n/2i) + i b n
Note that the general form of this equation shifts to the base case, T(n) = b, where
n = 2i, that is, when i = log n, which implies:

T(n) = b n + b n log n.
In other words, T(n) is O(n log n). In a general application of the iterative
substitution technique, we hope that we can determine a general pattern for T(n)
and that we can also figure out when the gen eral form of T(n) shifts to the base
case.
2.3 Probabilistic Analysis and Rando mized Algorithms
Probabilistic analysis of algorithms is an approach to estimate the computational
complexity of an algorithm or a computational problem. It starts from an assumption about a probabilistic distribution of the set of all possible inputs. This
assumption is then used to design an efficient algorithm or to derive the complexity
of a known algorithm.
2.3.1 The hiring problem
Suppose that you need to hire a new of fice assistant. Your previous attempts at
hiring have been unsuccessful, and you decide to use an employment agency. The
employment agency sends you one candidate each day. You interview that person
and then decide either to hire that person or not. You mu st pay the employment
agency a small fee to interview an applicant. To actually hire an applicant is more
costly, however, since you must fire your current office assistant and pay a
substantial hiring fee to the employment agency. You are committed to hav ing, at
all times, the best possible person for the job. Therefore, you decide that, after
interviewing each applicant, if that applicant is better qualified than the current
office assistant, you will fire the current office assistant and hire the new app licant.
You are willing to pay the resulting price of this strategy, but you wish to estimate
what that price will be. The procedure HIRE -ASSISTANT, given below, expresses
this strategy for hiring in pseudocode. It assumes that the candidates for the offic e munotes.in

Page 33

33Chapter 2: Divide and Conquer and Randomized Algorithm
assistant job are numbered 1 through n. The procedure assumes that you are able
to, after interviewing candidate i, determine whether candidate i is the best
candidate you have seen so far. To initialize, the procedure creates a dummy
candidate, numbered 0, who is less qualified than each of the other candidates.
HIRE -ASSISTANT(n)
best =0 // candidate 0 is a least -qualified dummy candidate
for i = 1 to n
interview candidate i
if candidate i is better than candidate best
best = i
hire candidate i
We focus not on the running time of HIRE -ASSISTANT, but instead on the costs
incurred by interviewing and hiring. On the surface, analyzing the cost of this
algorithm may seem very different from analyzing the running time of, say, merge
sort. The analytical techniques used, however, are identical whether we are
analyzing cost or running time. In either case, we are counting the number of times
certain basic operations are executed.
Interviewing has a low cost, say ci, whereas hiring is expensive, costing ch. Letting
m be the number of people hired, the total cost associated with this algorithm is
O(cin+chm). No matter how many people we hire, we always interview n
candidates and thus always incur the cost cin associated with interviewing. We
therefore concentrate on analyzing chm, the hiring cost. This quantity varies with each run of the algorithm. This scenario serves as a model for a common computational paradigm. We often need to find the maximum or minimum value
in a sequence by examining each element of the sequence and maintaining a current
“winner.” The hiring problem models how often we update our notion of which
element is currently winning.
Worst -case analysis
In the worst case, we actually hire every candidate that we interview. This situation
occurs if the candidates come in strictly increasing order of quality, in which case
we hire n times, for a total hiring cost of O (Chn). Of course, the candidates do not
always come i n increasing order of quality. In fact, we have no idea about the order munotes.in

Page 34

34ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING
in which they arrive, nor do we have any control over this order. Therefore, it is
natural to ask what we expect to happen in a typical or average case.
Probabilistic analysis
Probabil istic analysis is the use of probability in the analysis of problems. Most
commonly, we use probabilistic analysis to analyze the running time of an
algorithm. Sometimes we use it to analyze other quantities, such as the hiring cost
in procedure HIRE -ASSIS TANT. In order to perform a probabilistic analysis, we
must use knowledge of, or make assumptions about, the distribution of the inputs.
Then we analyze our algorithm, computing an average -case running time, where
we take the average over the distribution of the possible inputs. Thus we are, in
effect, averaging the running time over all possible inputs. When reporting such a
running time, we will refer to it as the average -case running time. We must be very
careful in deciding on the distribution of inputs . For some problems, we may
reasonably assume something about the set of all possible inputs, and then we can
use probabilistic analysis as a technique for designing an efficient algorithm and as
a means for gaining insight into a problem. For other proble ms, we cannot describe
a reasonable input distribution, and in these cases we cannot use probabilistic
analysis. For the hiring problem, we can assume that the applicants come in a
random order. What does that mean for this problem? We assume that we can
compare any two candidates and decide which one is better qualified; that is, there
is a total order on the candidates. Thus, we can rank each candidate with a unique
number from 1 through n, using rank (i) to denote the rank of applicant i, and adopt
the co nvention that a higher rank corresponds to a better qualified applicant. The
ordered list (rank(1),rank(2),… rank(n)) is a permutation of the list (1,2,…,n) .
Saying that the applicants come in a random order is equivalent to saying that this
list of ranks i s equally likely to be any one of the n ! permutations of the numbers 1
through n. Alternatively, we say that the ranks form a uniform random permutation;
that is, each of the possible n ! permutations appears with equal probability.
Randomized algorithms
In order to use probabilistic analysis, we need to know something about the
distribution of the inputs. In many cases, we know very little about the input
distribution. Even if we do know something about the distribution, we may not be
able to model this k nowledge computationally. Yet we often can use probability
and randomness as a tool for algorithm design and analysis, by making the behavior
of part of the algorithm random. In the hiring problem, it may seem as if the
candidates are being presented to us in a random order, but we have no way of
knowing whether or not they really are. Thus, in order to develop a randomized munotes.in

Page 35

35Chapter 2: Divide and Conquer and Randomized Algorithm
algorithm for the hiring problem, we must have greater control over the order in
which we interview the candidates. We will, therefore, change the model slightly.
We say that the employment agency has n candidates, and they send us a list of the
candidates in advance. On each day, we choose, randomly, which candidate to
interview. Although we know nothing about the candidates (besides the ir names),
we have made a significant change. Instead of relying on a guess that the candidates
come to us in a random order, we have instead gained control of the process and
enforced a random order. More generally, we call an algorithm randomized if its
behavior is determined not only by its input but also by values produced by a
random -number generator. We shall assume that we have at our disposal a random -
number generator RANDOM. A call to RANDOM (a,b) returns an integer between
a and b, inclusive, with each such integer being equally likely. For example,
RANDOM (0,1) produces 0 with probability 1 /2, and it produces 1 with probability
1/2. A call to RANDOM (3,7) returns either 3, 4, 5, 6, or 7, each with probability
1/5. Each integer returned by RANDOM is i ndependent of the integers returned on
previous calls. You may imagine RANDOM as rolling a (b-a+1) -sided die to obtain
its output. (In practice, most programming environments offer a pseudorandom -
number generator: a deterministic algorithm returning numbers that “look” statistically random.) When analyzing the running time of a randomized algorithm,
we take the expectation of the running time over the distribution of values returned
by the random number generator. We distinguish these algorithms from those in
which the input is random by referring to the running time of a randomized
algorithm as an expected running time. In general, we discuss the average -case
running time when the probability distribution is over the inputs to the algorithm,
and we discuss the expected running time when the algorithm itself makes random
choices.
2.3.2 Indicator random variables
In order to analyze many algorithms, including the hiring problem, we use indicator
random variables. Indicator random variables provide a convenient method for
converting between probabilities and expectations. Suppose we are given a sample
space S and an event A. Then the indicator random variable I {A} associated with
event A is defined as

As a simple example, let us determine the expected number of heads that we obtain
when flipping a fair coin. Our sample space is S = {H, T}, with Pr{H} = Pr{T}=1/2.
munotes.in

Page 36

36ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING
We can then define an indicator random variable XH , associated with the coin
coming up hea ds, which is the event H. This variable counts the number of heads
obtained in this flip, and it is 1 if the coin comes up heads and 0 otherwise. We
write

The expected number of heads obtained in one flip of the coin is simply the
expected value of our indicator variable XH :

Thus the expected number of heads obtained by one flip of a fair coin is 1/2. As the
following lemma shows, the expected value of an indicator random variable
associated with an event A is equal to the probability that A occurs.
2.3.3 Randomized algorithms
In the previous section, we showed how knowing a distribution on the inputs can
help us to analyze the average -case behavior of an algorithm. Many times, we do
not have such knowledge, thus precluding an average -case analysis. As mentioned
in Section 5.1, we may be able to use a randomized algorithm. For a problem such
as the hiring problem, in which it is helpful to assume tha t all permutations of the
input are equally likely, a probabilistic analysis can guide the development of a
randomized algorithm. Instead of assuming a distribution of inputs, we impose a
distribution. In particular, before running the algorithm, we random ly permute the
candidates in order to enforce the property that every permutation is equally likely.
Although we have modified the algorithm, we still expect to hire a new office
assistant approximately ln n times. But now we expect this to be the case for any
input, rather than for inputs drawn from a particular distribution. Let us further explore the distinction between probabilistic analysis and randomized algorithms. In Section 5.2, we claimed that, assuming that the
candidates arrive in a random orde r, the expected number of times we hire a new
office assistant is about ln n. Note that the algorithm here is deterministic; for any
particular input, the number of times a new office assistant is hired is always the
munotes.in

Page 37

37Chapter 2: Divide and Conquer and Randomized Algorithm
same. Furthermore, the number of times we hire a new office assistant differs for
different inputs, and it depends on the ranks of the various candidates. Since this
number depends only on the ranks of the candidates, we can represent a particular
input by listing, in order, the ranks of the candidates, i.e., ((rank(1), rank(2),…rank(n) ). Given the rank list A1 = (1,2,3,4,5,6,7,8,910), a new office
assistant is always hired 10 times, since each successive candidate is better than the
previous one, and lines 5 –6 are executed in each iteration. Gi ven the list of ranks
A2 =(10,9,8,7,6,5,4,3,2,1) , a new office assistant is hired only once, in the first
iteration. Given a list of ranks A3 =(5, 2, 1, 8, 4, 7, 10, 9, 3, 6), a new office assistant
is hired three times, upon interviewing the candidates wit h ranks 5, 8, and 10.
Recalling that the cost of our algorithm depends on how many times we hire a new
office assistant, we see that there are expensive inputs such as A1, inexpensive
inputs such as A2, and moderately expensive inputs such as A3. Consider, on the
other hand, the randomized algorithm that first permutes the candidates and then
determines the best candidate. In this case, we randomize in the algorithm, not in
the input distribution. Given a particular input, say A3 above, we cannot say how
many times the maximum is updated, because this quantity differs with each run of
the algorithm. The first time we run the algorithm on A3, it may produce the
permutation A1 and perform 10 updates; but the second time we run the algorithm,
we may produce the permutation A2 and perform only one update. The third time
we run it, we may perform some other number of updates. Each time we run the
algorithm, the execution depends on the random choices made and is likely to differ
from the previous execution of the algorithm. For this algorithm and many other
randomized algorithms, no particular input elicits its worst -case behavior. Even
your worst enemy cannot produce a bad input array, since the random permutation
makes the input order irrelevant. The randomized a lgorithm performs badly only if
the random -number generator produces an “unlucky” permutation. For the hiring
problem, the only change needed in the code is to randomly permute the array.
RANDOMIZED -HIRE -ASSISTANT(n)
randomly permute the list of candidate s
best = 0 // candidate 0 is a least -qualified dummy candidate
for i = 1 to n
interview candidate i
if candidate i is better than candidate best
best = i
hire candidate i munotes.in

Page 38

38ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTINGWith this simple change, we have created a randomized algorithm whose performance matches that obtained by assuming that the candidates were presented
in a random order.
2.4 Let us Sum Up
In this chapter we have learned various probabilistic Analysis and Randomised
algorithms.
2.5 List of references
1. https://www.codesdope.com/blog/article/maximum -subarray -sum-using -
divide -and-conquer/
2. Introduction to Algorithms, Third Edition, Thomas H. Cormen, Charles E.
Leiserson, Ronald L. Rivest, Clifford Stein, PHI Learning Pvt. Ltd -New
Delhi (2009).
3. https://www.javatpoint.com/algorithms -and-functions
4. Dr. L. V. N. Prasad, Professor, lecture notes on Design And Analysis Of
Algorithms
2.6 Exercise
1. Explain the concept of divide and con quer.
2. Explain the idea of Strassen’s algorithm for matrix multiplication.
3. Describe the concept of randomized algorithm. Write down algorithm for the
same. munotes.in

Page 39

39Chapter 3: Advanced Design And Analysis Techniques - Role Of Algorithm
Unit II
3 ADVANCED DESIGN AND ANALYSIS
TECHNIQUES
ROLE OF ALGORITHM
Unit Structure
3.0 Objective
3.1 Introduction
3.2 Dynamic Programming
3.2.1 Rod cutting
3.2.2 Elements of dynamic programming
3.2.3 Longest common subsequence
3.3 Greedy algorithm
3.3.1 An activity -selection problem
3.3.2 Elements of the greedy strategy
3.3.3 Huffman codes
3.4 Elementary Graph Algorithms
3.4.1 Representations of graphs
3.4.2 Breadth -first search
3.4.3 Depth -first search
3.5 Minimum Spanning Trees
3.5.1 Growing a minimum spanning tree
3.5.2 Algorithms of Kruskal and Prim
3.6 Single -Source Shortest Paths
3.6.1 The Bellman -Ford algorithm
3.6.2 Single -source shortest paths in directed acyclic graphs
3.6.3 Dijkstra’s algorithm
3.7 Let us Sum Up
3.8 List of References
3.9 Exercises munotes.in

Page 40

40ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING
3.1 Objective
After going through this unit, you will be able to:
• What is dynamic programming ?
• What is the need of greedy algorithm ?
• What is the elementary graph algorithm ?
• How to solve the single source shortest path problems ?
3.2 Introduction
In this section, we will learn dynamic programming, greedy algorithms, graph
algorithms, representation of graph, spanning tree and single source shortest path.
3.3 Dynamic Programming
We typically apply dynamic programming to optimization problems. Such problems can have many possible solutions. Each solution has a value, and we wish
to find a solution with the optimal (minimum or maximum) value. We call such a
solution an optimal solution to the problem, as opposed to the optimal soluti on,
since there may be several solutions that achieve the optimal value.
When developing a dynamic -programming algorithm, we follow a sequence of four
steps:
1. Characterize the structure of an optimal solution.
2. Recursively define the value of an opt imal solution.
3. Compute the value of an optimal solution, typically in a bottom -up fashion.
4. Construct an optimal solution from computed information.
3.3.1 Rod cutting
Given a rod of length n inches and an array of prices that contains prices of all
pieces of size smaller than n. Determine the maximum value obtainable by cutting
up the rod and selling the pieces. For example, if length of the rod is 8 and the
values of different pieces are given as following, then the maximum obtainable
value is 22 (b y cutting in two pieces of lengths 2 and 6) munotes.in

Page 41

41Chapter 3: Advanced Design And Analysis Techniques - Role Of Algorithm
length | 1 2 3 4 5 6 7 8
--------------------------------------------
price | 1 5 8 9 10 17 17 20
And if the prices are as following, then the maximum obtainable value is 24 (by
cutting in eight pieces of length 1)
length | 1 2 3 4 5 6 7 8
--------------------------------------------
price | 3 5 8 9 10 17 17 20
A naive solution for this problem is to generate all configurations of different
pieces and find the highest priced configuration. This solution is exponential in
term of time complexity. Let us see how this problem possesses both important
properties of a Dynamic Programming (DP) Problem and can efficiently solved
using Dynamic Programming.
1) Optimal Substructure:
We can get the best price by making a cut at different positions and
comparing the values obtained after a cut. We can recursively call the
same function for a piece obtained after a cut.
Let cutRod (n) be the required (best possible price) value for a rod of
length n. cutRod(n) can be written as following.
cutRod(n) = max(price[i] + cutRod(n -i-1)) for all i in {0, 1 .. n -1}
2) Overlapping Subproblems
Following is simple recursive implementation of the Rod Cutting problem.
The implementation simply follows the recursive structure.
3.3.2 Elements of dynamic programming
There are basically three elements that characterize a dynamic programming
algorithm: -
1. Substructure: Decompose the given problem into smaller subproblems.
Express the solution of the original problem in terms of the solution for
smaller problems.
2. Table Structure: After solving the sub -problems, store the results to the
sub problems in a table. This is done because subproblem solutions ar e munotes.in

Page 42

42ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING
reused many times, and we do not want to repeatedly solve the same
problem over and over again.
3. Bottom -up Computation: Using table, combine the solution of smaller
subproblems to solve larger subproblems and eventually arrives at a
solution to complete p roblem.
Bottom -up means: -
i. Start with smallest subproblems.
ii. Combining their solutions obtain the solution to sub -problems of
increasing size.
iii. Until solving at the solution of the original problem.
Development of Dynamic Programming Algorithm
It can be broken into four steps:
1. Characterize the structure of an optimal solution.
2. Recursively defined the value of the optimal solution. Like Divide and
Conquer, divide the problem into two or more optimal parts recursively.
This helps to determine what th e solution will look like.
3. Compute the value of the optimal solution from the bottom up (starting with
the smallest subproblems)
4. Construct the optimal solution for the entire problem form the computed
values of smaller subproblems.
Applications of dynamic programming
1. 0/1 knapsack problem
2. Mathematical optimization problem
3. All pair Shortest path problem
4. Reliability design problem
5. Longest common subsequence (LCS)
6. Flight control and robotics control
7. Time -sharing: It schedules the job to maximize CPU usage munotes.in

Page 43

43Chapter 3: Advanced Design And Analysis Techniques - Role Of Algorithm
3.3.3 Longest common subsequence
The longest common subsequence problem is finding the longest sequence which
exists in both the given strings.
Subsequence
Let us consider a sequence S = .
A sequence Z = over S is cal led a subsequence of S, if and
only if it can be derived from S deletion of some elements.
Common Subsequence
Suppose, ; and < are two sequences over a finite set of elements. We can say
that = is a common subsequence of ; and <, if = is a subsequence of b oth ; and <.
If a set of sequences are given, the longest common subsequence problem is to find
a common subsequence of all the sequences that is of maximal length.
Algorithm

LCS-LENGTH takes two sequences X = (x1, x2,…, xm) and Y = (y1, y2,…,yn )
as inputs. It stores the c[i, j] values in a table c[0..m, 0..n] and it computes the
entries in row -major order. (That is, the procedure fills in the first row of c from
left to right, then the second row, and so on.) The procedure also maintains the
table b[1..m,1..n] to help us construct an optimal solution. Intuitively, b[i, j] points
munotes.in