CS8451-DAA - by WWW - LearnEngineering.in PDF

For More Visit : www.Learnengineering.
in CS8451 - DAA
ENGINEERING COLLEGES
2016 – 17 Even Semester
IMPORTANT QUESTIONS AND ANSWERS
Department of CSE & IT
SUBJECT CODE: CS6402
SUBJECT NAME: DESIGN AND ANALYSIS OF ALGORITHMS
Regulation: 2013 Year and Semester: II Year/IV Sem
DEPARTMENT OF CSE
SUBJECT CODE: CS8451
SUBJECT NAME: DESIGN AND ANALYSIS OF ALGORITHMS
REGULATION
Prepared by : 2017
YEAR: II
Sl. No. Name of the Faculty Designation Affiliating College
SEM : IV
1. Dr.M.Duraipandian HOD/VP SCADIT
Verified by DLI, CLI and Approved by the Centralized Monitoring Team

dated
Copyright @ SCAD
For More Visit : www.Learnengineering.in

Page 1 of 120
For More Visit : www.Learnengineering.in CS8451 - DAA
SYLLABUS
CS8451 DESIGN AND ANALYSIS OF ALGORITHMS
OBJECTIVES: The student should be made to:

 Learn the algorithm analysis techniques.
 Become familiar with the different algorithm design techniques.
 Understand the limitations of Algorithm power.
UNIT I INTRODUCTION 9
Notion of an Algorithm – Fundamentals of Algorithmic Problem Solving –
Important Problem Types – Fundamentals of the Analysis of Algorithm Efficiency –
Analysis Framework – Asymptotic Notations and its properties – Mathematical
analysis for Recursive and Non- recursive algorithms.
UNIT II BRUTE FORCE AND DIVIDE-AND-CONQUER 9

Brute Force - Closest-Pair and Convex-Hull Problems-Exhaustive Search -
Traveling Salesman Problem - Knapsack Problem - Assignment problem. Divide
and conquer methodology – Merge sort – Quick sort – Binary search –
Multiplication of Large Integers – Strassen‟s Matrix Multiplication-Closest-Pair
and Convex-Hull Problems.
UNIT III DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE 9

Computing a Binomial Coefficient – Warshall‟s and Floyd‟ algorithm – Optimal
Binary Search Trees – Knapsack Problem and Memory functions. Greedy
Technique– Prim‟s algorithm- Kruskal's Algorithm- Dijkstra's Algorithm-Huffman
Trees.
UNIT IV ITERATIVE IMPROVEMENT 9

The Simplex MeFthod-The Maximum-Flow Problem – Maximum Matching in
Bipartite Graphs- The Stable marriage Problem.
UNIT V COPING WITH THE LIMITATIONS OF ALGORITHM POWER 9

Limitations of Algorithm Power-Lower-Bound Arguments-Decision Trees-P,
NP and NP- Complete Problems--Coping with the Limitations - Backtracking –
n-Queens problem – Hamiltonian Circuit Problem – Subset Sum Problem-Branch
and Bound – Assignment problem – Knapsack Problem – Traveling Salesman
Problem- Approximation Algorithms for NP – Hard Problems – Traveling
Salesman problem – Knapsack problem.
TOTAL: 45 PERIODS

Page 2 of 120
OUTCOMES: At the end of the course, the student should be able to:
 Design algorithms for various computing problems.

 Analyze the time and space complexity of algorithms.
 Critically analyze the different algorithm design techniques for a
given problem.
 Modify existing algorithms to improve efficiency.
TEXT BOOK:
1. Anany Levitin, ―Introduction to the Design and Analysis of
Algorithms‖, Third Edition, Pearson Education, 2012.
REFERENCES:
1. Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest and
Clifford Stein, ―Introduction to Algorithms‖, Third Edition, PHI Learning Private
Limited, 2012.
2. Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman, ―Data Structures
and Algorithms‖,Pearson Education, Reprint 2006.
3. Donald E. Knuth, ―The Art of Computer Programming‖, Volumes 1& 3
Pearson Education, 2 009.
4. Steven S. Skiena, ―The Algorithm Design Manual‖, Second Edition, Springer,
2008.
5. http://nptel.ac.in/

Page 3 of 120
INDEX
PAGE
S.NO CONTENTS NO.
1 Aim and objective 5
2 Detailed Lesson plan 7
Unit I – Introduction
3 Part A 10
4 Part B 15
5 Fundamentals of algorithmic problem solving 15
6 Important problem types 17
7 Mathematical Analysis of non-recursive 18
8 Asymptotic notations 19
9 Sequential Search 22
10 Mathematical Analysis of recursive 23
11 PART-C 25
Unit II - Brute force and Divide & Conquer
12 Part A 26
13 Part B 30
14 Exhaustive search 30
15 Merge sort 32
16 Binary search 34
17 Quick sort 35
18 Strassen‘s matrix multiplication 39
19 Closest pair and convex hull 42
20 PART-C 43
Unit III – Dynamic Programming & Greedy Technique
21 Part A 46
22 Part B 49
23 All pair shortest path problem 49
24 Knapsack problem 51
25 Optimal binary search tree 53

Page 4 of 120
26 Minimum spanning tree 59

27 Huffman coding 63
28 PART-C 64
Unit IV – Iterative improvement
29 Part A 67
30 Part B 70
31 Stable marriage problem 70
32 Maximum flow problem 72
33 Bipartite graphs 78
34 Simplex method 81
35 PART-C 84
Unit V – Coping with the limitations of algorithmic power
36 Part A 86
37 Part B 88
38 N-Queen‘s Problem 88
39 Hamiltonian and subset problem 90
40 Traveling salesman problem 93
41 Knapsack problem 96
42 Job Assignment problem 99
43 Approximation algorithms – TSP 102
44 Approximation algorithms – Knapsack Problem 105
45 PART-C 107
46 Industrial/Practical Connectivity of the subject 111
47 Question Bank 112

Page 5 of 120
AIM AND OBJECTIVE OF THE SUBJECT
The student should be made to:
 Learn the algorithm analysis techniques.

 Become familiar with the different algorithm design techniques.
 Understand the limitations of Algorithm power.
Need and Importance for Study of the Subject:
 Design and analysis is the basis for all problems since it

teaches how to design an algorithm based up on time and
space efficiency
 It also holds importance in such a way that there are various
methods to analyze the designed algorithms

Page 6 of 120
DETAILED LESSON PLAN
Text Book
1. Anany Levitin, ―Introduction to the Design and Analysis of
Algorithms‖, Third
Edition, Pearson Education, 2012. (Available in the library)
References
1. Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest and
Clifford Stein,
―Introduction to Algorithms‖, Third Edition, PHI Learning Private Limited,
2012.
(Available in the library)
2. Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman, ―Data
Structures and
Algorithms‖, Pearson Education, Reprint 2006. (Available in the library)
3. Donald E. Knuth, ―The Art of Computer Programming‖, Volumes 1& 3
Pearson
Education, 2009. (Not available in the Library)
4. Steven S. Skiena, ―The Algorithm Design Manual‖, Second Edition,
Springer, 2008.
(Not available in the Library)
5. http://nptel.ac.in/
S. Unit Hrs Cumilative Books

No No Topic/Portions to be covered Hrs Referred
Req
UNIT – I ITERATIVE AND RECURSIVE ALGORITHMS
1 I Introduction - Notion of an Algorithm 1 1 T1 , R1
Fundamentals of Algorithmic
2 I 1 2 T1
Problem
Solving
3 I Algorithm design technique 1 3 T1
4 I Important Problem Types 1 4 T1
Fundamentals of the Analysis

5 I 2 6 T1
of
Algorithm Efficiency
6 I Asymptotic Notations & Properties 1 7 T1, R1
7 I Mathematical analysis for 1 T1

8
Recursive
Algorithms
Mathematical analysis for No
8 I 1 9 T1
recursive
Algorithms

Page 7 of 120
Example : Formula and Algorithm

9 I 1 10 T1
for
Fibonacci Number generation
UNIT – II BRUTE FORCE AND DIVIDE-AND-CONQUER
Brute Force - Closest-Pair and
10 II 1 11 T1
Convex- Hull Problems
Exhaustive Search - Traveling
11 II 1 12 T1
Salesman
Problem
12 II Knapsack Problem 1 13 T1
13 II Assignment problem 1 14 T1
Divide and conquer

14 II 1 15 T1
methodology - Merge sort
15 II Quick sort 1 16 T1
16 II Binary search 1 17 T1
17 II Multiplication of Large 2 T1
19
Integers, Stassen‗s Matrix
18 II Multiplication
Closest-Pair and Convex-Hull 1 T1
20
Problems.
UNIT-III DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE

Dynamic Programming - Computing
19 III 1 21 T1
a
Binomial Coefficient
20 III Warshall‗s algorithm 1 22 T1
21 III Floyd‗s algorithm 1 23 T1, R1
22 III Optimal Binary Search Trees 2 25 T1, R1
Knapsack Problem and

23 III 2 27 T1
Memory functions
25 III Greedy Algorithm - Prim‗s Algorithm 1 28 T1, R1
26 III Kruskal's Algorithm 1 29 T1, R1
27 III Dijkstra's Algorithm 1 30 T1, R1
28 III Huffman Trees 1 31 T1, R1

Page 8 of 120
UNIT IV ITERATIVE IMPROVEMENT
Geometric Interpretation of Linear

29 IV 1 32 T1, R1
Programming
30 IV Steps in simplex method 1 33 T1, R1
31 IV Problem on Simplex Method 1 34 T1, R1
The Maximum-Flow
32 IV 2 36 T1, R1
Problem: Flow graph and
34 IV maximum
Maximum flow problem
Matching in Bipartite 2 T1, R1
38
Graphs
35 IV The Stable marriage Problem. 1 39 T1
UNIT V COPING WITH THE LIMITATIONS OF ALGORITHM POWER
36 V Lower-Bound Arguments 1 40 T1
37 V Decision Trees 1 41 T1
38 V P, NP and NP-Complete Problems 1 42 T1
39 V Backtracking – n-Queens problem 1 43 T1
40 V Hamiltonian Circuit Problem 1 44 T1
41 V Subset Sum Problem 1 45 T1
42 V Branch and Bound - Assignment 1 46 T1

problem
43 V Branch and Bound -Knapsack 1 47 T1
Problem
44 V Branch and Bound - TSP 1 48 T1
Approximation Algorithms for NP –

45 V 1 49 T1, R1
Hard
Problems: Traveling
Approximation Salesman
Algorithms for NP –
46 V problem 1 50 T1
Hard
Problems: Knapsack problem

Page 9 of 120
UNIT I – INTRODUCTION
Notion of an Algorithm – Fundamentals of Algorithmic Problem Solving –
Important Problem Types – Fundamentals of the Analysis of Algorithm Efficiency –
Analysis Framework – Asymptotic Notations and its properties – Mathematical
analysis for Recursive and Non-recursive algorithms.
PART – A
1. Define: Algorithm. May / June 2013 Nov/Dec 2016
An algorithm is a sequence of unambiguous instructions for solving a
problem, i.e., for obtaining a required output for any legitimate input in finite
amount of time. An algorithm is step by step procedure to solve a problem.
2. Differentiate time and space complexity. April / May 2010, Nov / Dec
2011
Time efficiency: indicates how fast the algorithm runs
Space efficiency: indicates how much extra memory the algorithm needs
3. What is recurrence equation? April / May 2010, Nov/Dec

2016
A recurrence equation or recurrence relation is an equation that recursively
defines a sequence, once one or more initial terms are given. Each further term of
the sequence is defined as the function of the preceding terms.
4. Write an algorithm to find the number of binary digits in the

binary representation of positive decimal integer. April / May
2015
Binary (n)
//Input: A positive decimal
integer n
//Output: The number of binary digits in n 's binary
representation
count ←1
while n >
1 do

Page 10 of 120
count← count + 1
n ← n/2
return
count
5. List out the properties of asymptotic notations. April / May 2015

 f(n)€ O(f(n))
 f(n) € O(g(n)) iff g(n) € (f(n))
 If
f (n) €O(g (n)) and g(n) € O(h(n)) , then f(n) €O(h(n)) similarity with a ≤ b
 I
f f1(n) €O(g1(n)) and f2(n) €O(g2(n)) , then f1(n) + f2(n) €O(max{g1(n),
g2(n)})
6. What do you mean by linear search? Nov / Dec 2011, May / June 2012
Linear Search or Sequential Search searches for the key value in the
given set of items sequentially and returns the position of the key value else returns
-1.
7. What are average, best and worst case efficiency? May / June 2014
The average case efficiency of an algorithm is its efficiency for an average
case input of size n. It provides information about an algorithm behavior on a typical
or random input.
The best-case efficiency of an algorithm is its efficiency for the best-
case input of size n, which is an input or inputs for which the algorithm runs the
fastest among all possible inputs of that size.
The worst-case efficiency of an algorithm is its efficiency for the worst-
case input of size n, which is an input or inputs of size n for which the
algorithm runs the longest among all possible inputs of that size.
8. What is asymptotic notation? Mention its uses.

Asymptotic notations are mathematical tools to represent time complexity of
algorithms for asymptotic analysis by identifying its behavior as the input size for
the algorithm increases. This is also known as an algorithms growth rate.
9. What are the components of fixed and variable parts in space complexity?
Nov / Dec 2013
Space Complexity of an algorithm is the amount of memory it needs to run to
completion i.e. from start of execution to its termination. Space need by any
algorithm is the sum of following components:
 Fixed Component: This is independent of the characteristics of
the inputs and outputs. This part includes: Instruction Space, Space of
simple variables, fixed size component variables, and constants variables.

Page 11 of 120
 Variable Component: This consist of the space needed by component

variables whose size is dependent on the particular problems
instances(Inputs/Outputs) being solved, the space needed by referenced
variables and the recursion stack space is one of the most prominent
components. Also this included the data structure components like Linked
list, heap, trees, graphs etc.
 Therefore the total space requirement of any algorithm 'A' can be
provided as
Space(A) = Fixed Components(A) + Variable Components(A)
10. Define O-notation. List the properties of Big Oh notation. Nov/Dec 2011, 12
A function t(n) is said to be in O(g(n)), denoted by t(n) ε O(g(n)), if t(n) is
bounded above by some constant multiple of g(n) for all large n, i.e., if there exists
some positive constant c and some non-negative integer n0 such that
t (n) <=cg (n) for all n >= n0
11. What are little Oh and omega notations? Nov / Dec 2013
Little Oh notation: A function t(n) is said to be in o(g(n)) denoted by t(n) € o(g(n)) if
there exists some positive constant c and some non-negative integer such that
t(n) < c g(n)
Little Omega notation: It is used to describe the best case analysis of

algorithms and concerned with small values of n. The function t(n)=ω(g(n)) iff
12. Define: Ω-notation.

A function t(n) is said to be in Ω (g(n)), denoted t(n) € Ω (g(n)), if t(n) is bounded
below by some positive constant multiple of g(n) for all large n, i.e., if
there exist some positive constant c and some nonnegative integer n0 such that
t(n) ≥ cg(n) for all n ≥ no.
13. Define: θ-notation.

A function t(n) is said to be in θ(g(n)), denoted t(n)€θ(g(n)), if t(n) is bounded
both above and below by some positive constant multiples of g(n) for all large n,
i.e., if there exist some positive constant c1 and c2 and some nonnegative
integer n0 such that c2g(n) ≤ t(n) ≤ c1g(n) for all n ≥ no.
14. Write master’s theorem, L – Hospital’s rule and Sterling’s formula.

Master Theorem:

Page 12 of 120
The limit -based approach is often more convenient than the one based on the
definitions because it can take advantage of the powerful calculus techniques
developed for computing limits, such as L'Hopital's rule:
15. Write down the basic asymptotic efficiency classes.

1 constant
log n logarithmic
N linear
n log n n-log-n
n2 quadratic
n3 cubic
2n exponential
n! factorial
16. Give the Euclid’s algorithm for computing gcd(m, n).

(May/June 2016)
ALGORITHM
Euclid_gcd(m, n)
//Computes gcd(m, n) by Euclid‗s algorithm
//Input: Two nonnegative, not-both-zero integers m and n
//Output: Greatest common divisor of m and n
while n ≠ 0 do
r ←m mod n m←n n←r
return m
Example: gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12.

Page 13 of 120
17. Compare the order of grouth n(n-1) and n2. (May/June 2016)
N n(n-1)/2 n2
Polynomial Quadratic Quadratic
1 0 1
2 1 4
4 6 16
8 28 64
10 45 102
102 4950 104
Complexity Low High
Growth Low high
18. The (log n)th smallest number of n unsorted numbers can be

determined in O(n) average- case time (True/False).
(Nov/Dec 2015)
False. Because naive method to solve this problem is to search all
positive integers, starting from 1 in the given array. We may have to search at most
n+1 numbers in the given array. So this solution takes O(n^2) in worst case.
19. Write t h e recursive Fibonocial algorithm and its recurrence relation.

(Nov/Dec 2015)
n! = 1•2•3...n and 0! = 1
(called initial case) so the
recursive definition n! = n•
(n-1)!
Algorithm F(n)
if n = 0 then return 1 // base case
else F(n-1)•n // recursive call
20. The ( log n)th smallest number of n unsorted numbers can b e

determined in
O(n) average-case time (True/False). (Nov/Dec 2015)
This is called finding the k-th order statistic. There's a very simple randomized
algorithm (called quick select) taking O(n) average time, O(n^2) worst case time, and
a pretty complicated non-randomized algorithm (called introselect) taking O(n) worst
case time.

Page 14 of 120
PART – B
1. Explain in detail about fundamentals of algorithmic problem solving.
FUNDAMENTALS OF ALGORITHMIC PROBLEM SOLVING
 We can consider algorithms to be procedural solutions to problems.

 These solutions are not answers but specific instructions for getting
answers.
 We now list and briefly discuss a sequence of steps one
typically goes through in designing and analyzing an
algorithm
ALGORITHM DESIGN AND ANALYSIS PROCESS

Understanding the Problem:
Read the problem‗s description carefully and ask questions if
you have any doubt s about the problem, do a few small examples by
hand, think about special cases, and ask questions again if needed. It helps to
understand how such an algorithm works and to know its strengths and
weaknesses, especially if you have to choose among several available
algorithms. But often you will not find a readily available algorithm and will
have to design your own.
Determining the Capabilities of the
Computational Device:
Once you completely u n d e r s t a n d a problem, you need to
determine the capabilities of the computational device. The central
assumption of the RAM model does not hold for some newer computers that
can execute operations concurrently, i.e., in parallel. Algorithms that take
advantage of this capability are called parallel algorithms.

Page 15 of 120
Choosing between Exact and Approximate Problem Solving:

The next principal decision is to choose between solving the
problem exactly or solving it approximately.
Algorithm Design Techniques:
An algorithm design technique is a general approach to solving problems
algorithmically that is applicable to a variety of problems from different areas of
computing.
Algorithm design techniques make it possible to classify algorithms
according to an underlying design idea..
Methods of specifying an algorithm:
Once you have designed an algorithm, you need to specify it. These are the
two options that are most widely used nowadays for specifying algorithms.
(i) Pseudo code is a mixture of a natural language and programming
language. Pseudo code is usually more precise than natural language.
(ii) Flowchart is a method of expressing an algorithm by a collection of
connected geometric shapes containing descriptions of the algorithm‘s
steps.
Ex: An algorithm to determine a student‗s final grade and indicate whether it
is passing or failing.
The final grade is calculated as the average of four marks.
Pseudo code:
Step 1: Input M1,M2,M3,M4
Step 2: GRADE= (M1+M2+M3+M4)/4
Step 3: if (GRADE < 50) then
Print ―FAIL‖
else
Print ―PASS
Proving an Algorithm’s Correctness:
Once an algorithm has been specified, you have to prove its correctness.
That is, you have to prove that the algorithm yields a required result for every
legitimate input in a finite amount of time.
In order to show that an algorithm is incorrect, you need just one instance
of its input for which the algorithm fails
Analyzing an Algorithm:
While analyzing an algorithm, we should consider the following factors.
Time efficiency: It is indicating how fast the algorithm runs.
Space efficiency: It is indicating how much extra memory it uses.
Simplicity: It means generating sequence of instructions which are easy to
understand.
Generality: We should write general algorithms for similar problems.
So we can reuse the same algorithms. If you are not satisfied with the
algorithm‘s efficiency, simplicity or generality you must redesign the
algorithm.
Coding an algorithm:
The coding of an algorithm is done by suitable programming language.
2. Discuss in detail about the important problem types available in

computer programming.

Page 16 of 120
IMPORTANT PROBLEM TYPES

The two motivating forces for any problem is its practical importance
and some specific characteristics.
The different types are:
1. Sorting
2. Searching
3. String processing
4. Graph problems
5. Combinatorial problems
6. Geometric problems
7. Numerical problems.
1. Sorting
Sorting problem is one which rearranges the items of a given list in
ascending order. For e.g. in student‘s information, sorting is carried out in the
student information either based on student‘s register number or by their
names. Such pieces of information are called as key.
Some of the sorting techniques are bubble sort, quick sort, merge
sort, etc.
2. Searching
The searching problem deals with finding a given value, called a search key,
in a given set. The searching can be either a straightforward algorithm or
binary search algorithm which is a different form. These algorithms play an
important role in real-life applications because they are used for storing and
retrieving information from large databases. Some algorithms work faster but
require more memory; some are very fast but applicable only to sorted
arrays. Searching, mainly deals with addition and deletion of records. In
such cases, the data structures and algorithms are chosen to balance among
the required set of operations.
3. String processing
A String is a sequence of characters. It is mainly used in string handling
algorithms. Most common ones are text strings, which consists of letters,
numbers and special characters. Bit strings consist of zeroes and ones. The
most important problem is the string matching, which is used for searching a
given word in a text. For e.g. sequential searching and brute- force string
matching algorithms.
4. Graph problems
One of the interesting area in algorithmic is graph algorithms. A graph is a
collection of points called vertices which are connected by line segments
called edges. Graphs are used for modeling a wide variety of real-life
applications such as transportation and communication networks.
It includes graph traversal, shortest-path and topological sorting algorithms.
Some graph problems are very hard, only very small instances of the problems
can be solved in realistic amount of time even with fastest computers.
There are two common problems: The traveling salesman problem,
finding the shortest tour through n cities that visits every city exactly once
The graph-coloring problem is to assign the smallest number of colors to
vertices of a graph so that no two adjacent vertices are of the same color. It
arises in event-scheduling problem, where the events are represented by
vertices that are connected by an edge if the corresponding events cannot be

Page 17 of 120
scheduled in the same time, a solution to this graph gives an optimal schedule.
5. Combinatorial problems
The traveling salesman problem and the graph-coloring problem are examples
of combinatorial problems. These are problems that ask us to find a
combinatorial object such as permutation, combination or a subset that
satisfies certain constraints and has some desired (e.g. maximizes a value or
minimizes a cost).
These problems are difficult to solve for the following facts. First, the number
of combinatorial objects grows extremely fast with a problem‘s size.
Second, there are no known algorithms, which are solved in acceptable
amount of time.
6. Geometric problems
Geometric algorithms deal with geometric objects such as points, lines and
polygons. It also includes various geometric shapes such as triangles, circles
etc. The applications for these algorithms are in computer graphic, robotics
etc. The two problems most widely used are the closest-pair problem,
given ‗n‗ points in the plane, finds the closest pair among them. The
convex-hull problem is to find the smallest convex polygon that would
include all the points of a given set.
7. Numerical problems
This is another large special area of applications, where the problems involve
mathematical objects of continuous nature: solving equations computing
definite integrals and evaluating functions and so on. These problems
can be solved only approximately. These require real numbers, which can be
represented in a computer only approximately. If can also lead to an
accumulation of round-off errors. The algorithms designed are mainly used in
scientific and engineering applications.
3. Give the mathematical analysis for non-recursive algorithm. (Nov/Dec

2016) Steps in mathematical analysis of non-recursive algorithms:
 Decide on parameter n indicating input size
 Identify algorithm‘s basic operation Check whether the number of times
the basic operation is executed depends only on the input size n. If it also
depends on the type of input, investigate worst, average, and best case
efficiency separately.
 Set up summation for C(n) reflecting the number of times the algorithm‘s
basic operation is executed.
 Example: Finding the largest element in a given array
 Analysis:
Let us denote C(n) the number of times this comparison is executed

Page 18 of 120
and try to find a formula expressing it as a function of size n. The

algorithm makes one comparison on each execution of the loop, which
is repeated for each value of the loop's variable i within the bounds 1
and n - 1 (inclusively). Therefore, we get the following sum for C(n):
This is an easy sum to compute because it is nothing else but 1 repeated n –
1 times. Thus,
4. Explain in detail about asymptotic notations. (May/June 2016)
(Nov/Dec 2016)
ASYMPTOTIC NOTAIONS
Asymptotic notations are mathematical tools used to analyse the

algorithm in terms of time efficiency.
3 Asymptotic Notations:
1. O Notation (Big Oh)
2. Ω Notation (Big Omega)
3. θ Notation (Big Theta)
1. O Notation (Big Oh):
Definition:A function f(n) is said to be in O(g(n)), denoted f(n) ∈

O(g(n)), if f(n) is bounded above by some constant multiple of g(n) for all
large n, i.e., if there exist some positive constant c and some nonnegative
integer n0 such that
f(n) ≤ cg(n) for all n ≥ n0 and c > 0.
O notation analyses the worst case for the given function.
The definition is illustrated in the following figure.

t
Here n is size of an input &f(n) is a function of n.

Page 19 of 120
When the input size increases, then the time is also increases.
Example:
Let take f(n)=3n+2 and g(n)=n.
We have to prove f(n) ∈O(g(n)).
By the definition,
f(n)≤c g(n)
3n+2≤ c * n where c>0, n0≥1.
We can substitute any value for c.
The best option is,
When c=4, 3n+2≤ 4 * n.
Most of the cases, 4*n is greater than

3n+2. Where n≥2.
Reason for taking n≥2:
If n=1, 3(1)+2 ≤ 4(1)=> 5≤4=> Becomes False.
If n=2, 3(2)+2 ≤ 4(2)=> 8≤8=> Becomes True.
If n=3, 3(3)+2 ≤ 4(3)=> 11≤12=> Becomes True.
If n=4, 3(4)+2 ≤ 4(4)=> 14≤16=> Becomes True.
And so on.
Therefore 3n+2 ∈ O(n).
2. Ω Notation (Big Omega):
Definition: A function f(n) is said to be in Ω(g(n)), denoted f(n) ∈

Ω(g(n)), if f(n) is bounded below by some positive constant multiple of g(n) for
all large n, i.e., if there exist some positive constant c and some nonnegative
integer n0 such that
f(n) ≥ cg(n) for all n ≥ n0 and c > 0.
Ω notation analyses the best case for the given function.

Page 20 of 120
Here n is size of an input & f(n) is a function of n.
Example:

Why we always choose n0 ≥ 1?
We have to prove f(n) ∈Ω(g(n)).
Because n is an input value. It
By the definition, has to be at least 1.
f(n)≥c g(n)
3n+2≥ c n where c>0, n0≥1.
We can substitute any value for c.
The best option is,
Even if c=1, 3n+2≥1*n.
For any cases, 1*n is smaller than

3n+2. Where n≥1.
Reason for taking n≥1:
If n=1, 3(1)+2 ≥1(1)=> 5≥1=> Becomes True.
If n=2, 3(2)+2 ≥1(2)=> 8≥2=> Becomes True.
If n=3, 3(3)+2 ≥1(3)=> 11≥3=> Becomes True.
And so on.
Therefore 3n+2 ∈ Ω(n).
3. θ Notation (Big Theta):

Page 21 of 120
Definition: A function f(n) is said to be in θ(g(n)), denoted f(n) ∈

θ(g(n)), if f(n) is bounded both above and below by some positive constant
multiples of g(n) for all large n, i.e., if there exist some positive constants c1
and c2 and some nonnegative integer n 0 such that c1g(n) ≤ f(n) ≤ c2g(n) for all
n ≥ n0.
θ notation analyses the average case for the given function.
Here n is size of an input &f(n) is a function of n.
c1 and c2 are different constants.
f(n) is bounded by both upper and lower i.e) c1g(n) ≤ f(n) ≤ c2g(n).
Example:
We have to prove f(n) ∈θ(g(n)).
By the definition,
c1g(n) ≤ f(n) ≤ c2g(n)
c1 * n ≤ 3n+2 ≤ c2 * n
3n+2 ≤ c2 * n when c2=4
and
3n+2≥ c1 * n when c1=1.
Such that, 1*n ≤ 3n+2 ≤ 4*n. Where n≥2.
Therefore 3n+2 ∈ θ(n).

Page 22 of 120
5. With an algorithm explain in detail about the linear search. Give its
efficiency.
SEQUENTIAL SEARCH
Sequential Search searches for the key value in the given set of items
sequentially and returns the position of the key value else returns -1.
Algorithm sequentialsearch(A[0….n-1],K)
//Searches for a given array by sequential search
//Input: An array A[0….n-1} and a search key K
// the index of the first element of A that matches K or -1 if there are no matching
elements i←0
while i<n and A[i]≠K do
i←i+1 if i<n return i else return -1
Analysis:
For sequential search, best-case inputs are lists of size n with their first
elements equal to a search key; accordingly, Cbw(n) = 1.
Average Case Analysis:

The standard assumptions are that :
a. the probability of a successful search is equal top (0 <=p<-=1) and
b. the probability of the first match occurring in the ith position of the list is
the same for every i. Under these assumptions- the average number of key
comparisons Cavg(n) is found as
follows.
In the case of a successful search, the probability of the first
match occurring in the i th position of the list is p / n for every i,
and the number of comparisons made by the algorithm in such a
situation is obviously i.
6. Explain in detail about mathematical analysis of recursive algorithm
MATHEMATICAL ANALYSIS FOR RECURSIVE ALGORITHMS
General Plan for Analysing the Time Efficiency of Recursive Algorithms:
1. Decide on a parameter (or parameters) indicating an input’s size.
2. Identify the algorithm‘s basic operation.

Page 23 of 120
3. Check whether the number of times the basic operation is executed

can vary on different inputs of the same size; if it can, the worst-case,
average-case, and best-case efficiencies must be investigated separately.
4. Set up a recurrence relation, with an appropriate initial condition, for the

number of times the basic operation is executed.
5. Solve the recurrence. (Using Backward Substitution method)
Example 1:
//Computes n! recursively
//Input: A nonnegative integer n
//Output: The value of n!
if(n = = 0)
return 1
else
return Factorial (n – 1) * n
Example 2:
//Tower of Hanoi problem-Moves n disks from peg A to peg C
//Input: n disks
//Output: The disks are placed in peg c by correct order
//if one disk has to be moved
TOH(n,A,C,B)
If(n==1) then
Move disk 1 from peg a to peg c

Page 24 of 120
PART-C
1. Give an algorithm to check whether all the Elements in a given array

of n elements are distinct. Find the worst case complexity of the same.
Element uniqueness problem: check whether all the Elements in a given

array of n elements are distinct.
ALGORITHM UniqueElements(A[0..n − 1])
//Determines whether all the elements in a given
array are distinct
//Input: An array A[0..n − 1]
//Output: Returns ―true‖ if all the elements in A are distinct and ―false‖
otherwise
for i ←0 to n − 2 do
for j ←i + 1 to n − 1 do
if A[i]= A[j ] return false
return true
Worst case Algorithm analysis

The natural measure of the input‗s size here is again n (the number
of elements in the array).
Since the innermost loop contains a single operation (the comparison
of two elements),
we
should consider it as the algorithm‗s basic operation.
The number of element comparisons depends not only on n but also
on whether there are equal elements in the array and, if there are,
which array positions they occupy. We will limit our investigation to
the worst case only.
One comparison is made for each repetition of the innermost loop,
i.e., for each value of the loop variable j between its limits i + 1 and n − 1;
this is repeated for each value of the outer loop, i.e., for each value of the
loop variable i between its limits 0 and n − 2.
2. Give the recursive algorithm which finds the number of binary

digits in the binary representation of a positive decimal integer. Find
the recurrence relation and complexity. (May/June 2016)

Page 25 of 120
An investigation of a recursive version of the algorithm which finds the

number of binary digits in the binary representation of a positive
decimal integer.
ALGORITHM BinRec(n)
//Input: A positive decimal integer n
//Output: The number of binary digits in n‗s binary representation
if n = 1 return 1
else return BinRec( n/2 )+ 1
Algorithm analysis
The number of additions made in computing BinRec( n/2 ) is A( n/2 ),
plus one more addition is made by the algorithm to increase the returned
value 1.This lead to the recurrence
A(n) = A( n/2 ) + 1 for n > 1.
Since the recurrence call end when n is equal to 1 and there are no
addition made then the initial condition is A(1)=0
The standard approach to solving such a recurrence is to solve it
only for n = 2k

Page 26 of 120
UNIT II - BRUTE FORCE AND DIVIDE-AND-CONQUER
Brute Force – Closest-Pair and Convex-Hull Problems-Exhaustive Search -

Traveling Salesman Problem - Knapsack Problem - Assignment problem.
Divide and conquer methodology – Merge sort – Quick sort – Binary search
– Multiplication of Large Integers – Strassen‟s Matrix Multiplication-Closest-
Pair and Convex-Hull Problems.
PART – A
1. Define: Brute force. (Nov/Dec 2016)

A straightforward approach, usually based directly on the problem‘s
statement and definitions of the concepts involved.
2. What is exhaustive search?

Exhaustive search is simply a brute-force approach to combinatorial
problems. It suggests generating each and every element of the problem's
domain, selecting those of them that satisfy all the constraints, and then
finding a desired element (e.g., the one that optimizes some objective
function).
3. Give the general plan of exhaustive search.

Method:
• Generate a list of all potential solutions to the problem in a systematic
manner.
• Evaluate potential solutions one by one, disqualifying infeasible ones
and, for an optimization problem, keeping track of the best one found so far
• when search ends, announce the solution(s) found
4. How does a divide and conquer algorithm work? May / June 2013,
2016
Divide and conquer is an algorithm design paradigm based on multi
branched recursion. The general plan is as follows:
• A problems instance is divided into several smaller instances of
the same problem, ideally about the same size
• The smaller instances are solved, typically recursively
• If necessary the solutions obtained are combined to get the
solution of the original problem
5. What is travelling salesman problem? Nov / Dec 2011

The travelling salesman problem is to find the shortest tour that passes
through all the cities exactly once before returning to the starting city for the
given n cities with known distances between each pair.
6. What is knapsack problem? Nov / Dec 2011

It is the problem of finding t h e most valuable s u b s e t o f
items that fit into the knapsack, given n items with

Page 27 of 120
• Weights: w1 w2 … wn
• Values: v1 v2 … vn
• A knapsack of capacity W
7. Give the control abstraction of divide and conquer techniques. Nov
/Dec 2012,13
Control abstraction for recursive divide and conquer, with
problem instance P
divide_and_conquer ( P )
{
divide_and_conquer ( P2 ),
...
divide_and_conquer ( Pk ) ) );
}
8. Differentiate linear search and binary search. Nov / Dec 2014
Linear search: Linear Search or Sequential Search searches for
the key value in the given set of items sequentially and returns the position
of the key value else returns -1. Binary search: Binary search is a
remarkably efficient algorithm for searching in a sorted array. It works by
comparing a search key K with the arrays middle element A[m]. If they
match the algorithm stops; otherwise the same operation is repeated
recursively for the first half of the array if K < A[m] and the second half if K >
A[m].
9. Derive the complexity for binary search algorithm. April / May 2012,15
Nov/Dec 2016
10.. Distinguish between quick sort and merge sort. Nov/ Dec 2011
Merge Quick
Sort
For merge sort the arrays are In quick sort theSort
arrays are
partitioned partitioned
according to their position according to the element values.
11. Give the time complexity of merge sort.
Cworst(n) = 2Cworst(n/2) + n- 1 for n> 1, Worst(1)=0
Cworst(n) € Θ(n log n) (as per master‗s theorem)
12. Define: Convex and Convex hull.

Convex: A set of points (finite or infinite) in the plane is called convex if
for any two points P and Q in the set, the entire line segment with the
Page 28 of 120
endpoints at P and Q belongs to the set.

Convex hull: The convex hull of a set S of points is the smallest
convex set containing S. The "smallest" requirement means that the
convex hull of S must be a subset of any convex set containing S.
13. What is Closest-Pair Problem?(May/June 2016)

The closest-pair problem finds the two closest points in a set of n
points. It is the simplest of a variety of problems in computational
geometry that deals with proximity of points in the plane or higher-
dimensional spaces
14. Write down the advantages and disadvantages of divide and
conquer algorithm.
Advantages of divide and conquer algorithm:
 Solving difficult problems,
 Algorithm efficiency,
 Parallelism, Memory access and
 Round off control.
Disadvantages of divide and
conquer algorithm:
 Conceptual
 difficulty
 Recursion overhead
 Repeated sub problems

Page 29 of 120
PART – B
1. Using exhaustive search solve traveling salesman problem,
knapsack problem and assignment problem for the given data.
EXHAUSTIVE
SEARCH
(i) Traveling Salesman Problem:
Solution:
(ii) Knapsack Problem:

W = 10

Page 30 of 120
Item weight value

1 7 $42
2 3 $12
3 4 $40
4 5 $25
Solution:
Subset Total weight Totalvalue
F 0 $0
{1} 7 $42
{2} 3 $12
{3} 4 $40
{4} 5 $25
{1,2} 10 $36
{1,3} 11 Not feasible
{1,4} 12 Not feasible
{2,3} 7 $52
{2,4} 8 $37
{3,4} 9 $65
{1,2,3} 14 Not feasible
{1,2,3,4} 19 Not feasible
(iii)Assignment Problem: (Nov/Dec 2016)

Job1 Job2 Job3 Job4
Person1 9 2 7 8
Person2 6 4 3 7
Person3 5 8 1 8
Person4 7 6 9 4
Solution:
C = 9 2 7 8
6 4 3 7
5 8 1 8
7 6 9 9
<1,2,3,4> cost = 9+4+1+4=18

<1,2,4,3> cost = 9+4+8+9=30
<1,3,2,4> cost = 9+3+8+4=24
<1,3,4,2> cost = 9+3+8+6=26

Page 31 of 120
<1,4,2,3> cost = 9+7+8+9=33

<1,4,3,2> cost = 9+7+1+6=23
2. Explain the merge sort using divide and conquer technique give an
example. April / May 2010,May/June 2016
Devise an algorithm to perform merge sort.
Trace the steps of merge sort algorithm for the elements 8, 3, 2, 9,
7, 1, 5, 4 and also compute its time complexity.
MERGE SORT
o It is a perfect example of divide-and-conquer.
o It sorts a given array A [0..n-1] by dividing it into two halves
A[0…(n/2-1)] and A[n/2…n-1], sorting each of them recursively
and then merging the two smaller sorted arrays into a single sorted
one.
Algorithm for merge sort:
//Input: An array A [0…n-1] of
orderable elements //Output:
Array A [0..n-1] sorted in
increasing order
if n>1
Copy A[0…(n/2-1)] to
B[0…(n/2-1)] Copy
A[n/2…n-1] to
C[0…(n/2-1)] Merge
sort (B[0..(n/2-1)]
Merge sort (C[0..(n/2-
1)] Merge (B,C,A)
Merging process:
The merging of two sorted arrays can be done as follows:
o Two pointers are initialized to point to first elements of the arrays
being merged.
o Then the elements pointed to are compared and the smaller of them
is added to a new array being constructed;
o After that, that index of that smaller element is incremented to
point to its immediate successor in the array it was copied from.
This operation is continued until one of the two given arrays are
exhausted then the remaining elements of the other array are
copied to the end of the new array.
Algorithm for merging:
Algorithm Merge (B[0…P-1], C[0…q-1], A[0…p + q-1])
//Merge two sorted arrays into one sorted array.
//Input: Arrays B[0..p-1] and C[0…q-1] both sorted
//Output: Sorted Array A [0…p+q-1] of the elements of B & C
i = 0; j = 0; k = 0

Page 32 of 120
while i < p and j < q do if B[i] ≤ C[j]

A[k] = B[i]; i = i+1
if i=p
else
k =k+1
A[k] = B[j]; j = j+1
copy C[j..q-1] to A[k..p+q-1]
else
copy B[i..p-1] to A[k..p+q-1]

Example:

Page 33 of 120
3. Explain the binary search with suitable example. Nov/ Dec 2011 (Nov/Dec
15) Write an algorithm to perform binary search on a sorted list of elements
and analyze the algorithm. April / May 2011
BINARY SEARCH
It is an efficient algorithm for searching in a sorted array. It is an example for
divide and conquer technique.
Working of binary search:

It works by comparing a search key k with the array‘s middle element A [m].
If they match, the algorithm stops; otherwise the same operation is
repeated recursively for the first half of the array if K < A (m) and for the
second half if K > A (m).
K
A [0] … A [m – 1] A [m] A [m+1] …. A [n-1]
Search here if K < A (m) Search here if K > A
(m)
Example:
Given set of elements
3 14 27 31 42 55 70 81 98
Search key: K=55
The iterations of the algorithm are given as:
A [m] = K, so the algorithm stops

Binary search can also implemented as a nonrecursive
algorithm. Algorithm Binarysearch(A[0..n-1], k)
// Implements nonrecursive binarysearch
// Input: An array A[0..n-1] sorted in ascending order and a search key k
// Output: An index of the array‗s element that is equal to k or -1 if there is no such element
l←0;
r←n-1
while l ≤ r do
m←[(l+r)/2]
if k = A[m] return m
else if k < A[m] r←m-1
else l←m+1

Page 34 of 120
return -1
Analysis:
The efficiency of binary search is to count the number of times the search key is
compared with an element of the array.
For simplicity, three-way comparisons are considered. This assumes that
after one comparison of K with A [M], the algorithm can determine whether K is smaller,
equal to, or larger than A [M]. The comparisons not only depend on ‗n‗ but also the
particular instance of the problem.
The worst case comparison Cw (n) includes all arrays that do not contain a search
key, after one comparison the algorithm considers the half size of the array.Cw (n) = Cw
(n/2) + 1 for n > 1, Cw (1) = 1 --------------------- eqn(1)
To solve such recurrence equations, assume that n = 2k to obtain the solution.
Cw ( k) = k +1 = log2n+1
For any positive even number n, n = 2i, where I > 0. now the LHS of eqn (1) is:
Cw (n) = [ log2n]+1 = [ log22i]+1 = [ log 22 + log2i] + 1 = ( 1 + [log2i]) + 1
= [ log2i] +2
The R.H.S. of equation (1) for n = 2 i is
Cw [n/2] + 1 = Cw [2i / 2] + 1
= Cw (i) + 1
= ([log2 i] + 1) + 1
= ([log2 i] + 2
Since both expressions are the same, the assertion is proved.
The worst – case efficiency is in θ (log n) since the algorithm reduces the size of the
array remained as about half the size, the numbers of iterations needed to reduce the initial
size n to the final size 1 has to be about log2n. Also the logarithmic functions grow so
slowly that its values remain small even for very large values of n.
The average-case efficiency is the number of key comparisons made which is
slightly smaller than the worst case.
More accurately, . e.Cavg (n) ≈ log2n
for successful search iCavg (n) ≈ log2n –1
for unsuccessful search Cavg (n) ≈ log2n + 1
3. Explain in detail about quick sort. (Nov/Dec 2016)
QUICK SORT
Quick sort is an algorithm of choice in many situations because it is not
difficult to implement, it is a good \"general purpose\" sort and it consumes relatively
fewer resources during execution.
Quick Sort and divide and conquer

Page 35 of 120
Divide: Partition array A[l..r] into 2 sub-arrays, A[l..s-1] and A[s+1..r] such that
each element of the first array is ≤A[s] and each element of the second array is ≥
A[s]. (Computing the index of s is part of partition.)
Implication: A[s] will be in its final position in the sorted array.
Conquer: Sort t h e t w o s u b - a r r a y s A [l...s-1] a n d A [s+1...r] b y r e c u r s i v e
c a l l s t o quicksort Combine: No work is needed, because A[s] is already in its
correct place after the partition is done, and the two sub arrays have been sorted.
Steps in Quicksort
 Select a pivot with respect to whose value we are going to divide the
sublist. (e.g., p = A[l])
 Rearrange the list so that it starts with the pivot followed by a ≤ sublist
(a sublist whose elements are all smaller than or equal to the pivot)
and a ≥ sublist (a sublist whose elements are all greater than or equal
to the pivot ) Exchange the pivot with the last element in the first
sublist(i.e., ≤ sublist) – the pivot is now in its final position.
The Quicksort Algorithm

ALGORITHM Quicksort(A[l..r])
//Sorts a subarray by quicksort
//Input: A subarray A[l..r] of A[0..n-1],defined by its left and right indices l and r
//Output: The subarray A[l..r] sorted in nondecreasing
order if l < r s Partition (A[l..r]) // s is a split
position
Quicksort(A[l..s-])
Quicksort(A[s+1..r
ALGORITHM Partition (A[l ..r])
//Partitions a subarray by using its first element as a pivot
//Input: A subarray A[l..r] of A[0..n-1], defined by its left and right indices l and r
(l < r)
//Output: A partition of A[l..r], with the split position returned as this function‗s
value
P <-A[l]
i <-l; j <- r + 1;
Repeat
repeat i <- i + 1 until A[i]>=p //left-right
scan repeat j <-j – 1 until A[j] <=
p//right-left scan
if (i < j) //need to continue with the scan swap(A[i],
a[j])

Page 36 of 120
until i >= j //no need

to scan swap(A[l], A[j])
return j
Advantages in Quick Sort

 It is in-place since it uses only a small auxiliary stack.
 It requires only n log(n) time to sort n items.
 It has an extremely short inner loop
 This algorithm has been subjected to a thorough mathematical analysis, a
very precise statement can be made about performance issues.
.
Disadvantages in Quick Sort
 It i s r e c u r s i v e . Especially if r e c u r s i o n i s n o t a v a i l a b l e , t h e
i m p l e m e n t a t i o n is extremely complicated.
 It requires quadratic (i.e., n2) time in the worst-case.
 It is fragile i.e., a simple mistake in the implementation can go unnoticed and
cause it to perform badly.
Efficiency of Quicksort
Based on whether the partitioning is balanced.
Best case: split in the middle — Θ (n log n)
C (n) = 2C (n/2) + Θ (n) //2 subproblems of size n/2 each
Worst case: sorted array! — Θ (n2)
C (n) = C (n-1) + n+1 //2 subproblems of size 0 and n-1 respectively
Average case: random arrays — Θ (n log n)
Conditions:
If i< j, swap A[i] and A[j]
If I > j, partition the array after exchanging pivot and A[j] If
i=j, the value pointed is p and thus partition the array
Example:
50 30 10 90 80 20 40 70
Step 1: P = A[l]
50 30 10 90 80 20 40 70
P I j
Step2: Inrement I; A[i] < Pivot
50 30 10 90 80 20 40 70
P I j
Step 3: Decrement j; A[j]>Pivot

Page 37 of 120
50 30 10 90 80 20 40 70
P I j
Step 4: i<j; swap A[i] & A[j]
50 30 10 40 80 20 90 70
P I j
Step 5: Increment i
50 30 10 40 80 20 90 70
P I j
Step 6: Decrement j
50 30 10 40 80 20 90 70
P I j
Step 7: i<j, swap A[i] & A[j]
50 30 10 40 20 80 90 70
P I j
Step 8: Increment I, Decrement j
50 30 10 40 20 80 90 70
P j i
Step 9: i>j, swap P & A[j]

20 30 10 40 50 80 90 70
Left sublist I Right sublist
Step 10: Increment I & Decrement j for the left sublist

20 30 10 40 50 80 90 70
P i j
20 10 30 40 50 80 90 70
P I j
Step 12: inc I, Dec j for left sublist
20 10 30 40 50 80 90 70
P j i
Step 13: i>j, swap P & A[j]
10 20 30 40 50 80
90 70 j
Step 14: inc I, Dec j for right sublist
10 20 30 40 50 80 90 70
P I j
10 20 30 40 50 80 70 90
P I j
Step 16: inc I, Dec j for right sublist
10 20 30 40 50 80 70 90
P p j i
Step 17: i>j, Exchange P & A[j]

10 20 40 50 80 90
p j i
The final s
Page 38 of 120
Master‗s Theorm:
C(n)=2c(n/2)+ 1
C(1) =
As per master‗s Theorem:
C(n)tq(ncnlogn)
Substitution method:
c(n)2c(n/2)+n n=2k
c(2k) = 2c(2k-1) +2k
=22c(2k-2) +2.2k
=23c(2k-3) +3.2k
=24c(2k-4) +4.2k
C(2k) = 2k c(2k-k) + k.2k
=2kc(1)+k.2k
C(2k)=k.2k N=2k
5. Explain in detail about Strassen’s Matrix Multiplication. (Nov/Dec 15)

STRASSEN’S MATRIX MULTIPLICATION
 This is a problem which is used for multiplying two n x n matrixes.
 Volker Strassen in 1969 introduced a set of formula with fewer
number of multiplications by increasing the number of additions.
 Based on straight forward or Brute-Force algorithm.
Where,
m1 = ( a00 + a11 ) * (b00 + b11)
m2 = ( a10 + a11 )* b00 m3 = a00 *
(b01 - b11) m4
= a11 * (b10 – b00) m5 = (
a00 + a01 * b11
m6 = (a10 – a00) * (b00 + b01)
Page 39 of 120
m7 = ( a01 - a11 ) * (b10 + b11)
Thus, to multiply two 2-by-2 matrixes, Strassen‗s algorithm requires seven

multiplications and 18 additions / subtractions, where as the brute-force algorithm requires
eight multiplications and 4 additions. Let A and B be two n-by-n matrixes when n is a power
of two. (If not, pad the rows and columns with zeroes). We can divide A, B and their product
Analysis:
The efficiency of this algorithm, M(n) is the number of multiplications in multiplying
two n by n matrices according to Strassen‗s algorithm. The recurrence relation is as
follows:
6. Write a brute force algorithm to find closest points in a set of n points and an
algorithm based on divide and conquer to solve convex hull problem.
April / May 2015Nov/Dec 15
Find the two closest points in a set of n points (in the two-dimensional Cartesian plane).
Brute-force algorithm
Compute the distance between every pair of distinct points and return the indexes of the
points for which the distance is the smallest.
Algortihm BruteForceClosestPoint(P)
//Input A list P of n (n≥2) points P1=(x1,y1),………Pn=(xn,yn)
//Output: Indices index1 and index 2 of the closest pair of points dmin←∞
for i←1 to n-1 do
for j←i+1 to n do
d←sqrt((xi-xj)2
(yi-yj)2
// sqrt – square root function if d<+)

Page 40 of 120
dmin
dmin←∞ index1←I; index2←j
return index1, index2
Efficiency: Θ(n^2) multiplications (or sqrt) Convex:

A polygon is convex if any line segment joining two points on the
boundary sta ys within the polygon. Equivalently, if you walk around t h e
boundary o f the polygon in counter- clockwise direction you always take left
turns.
Convex Hull:
The convex hull of a set of points in the plane is the smallest convex polygon
for which each point is either on the boundary or in the interior of the polygon.
A vertex is a corner of a polygon. For example, the highest, lowest,
leftmost and rightmost po in ts are all vertices of the convex hull.
Quick Hull Algorithm:

Algorithm used to find the convex hull.
Assumption: Points are sorted by x- coordinate values.
Step 1: Identify extreme points P1 and P2.
Step 2: Compute upper hull recursively
2.1 find point Pmax that is farthest away from line P1 P2.
2.2 Compute the upper hull of the points to the left of line P1
Pmax
2.3 Compute the upper hull of the points to the left of line Pmax
P2
Step 3: Compute the lower hull in a similar manner.
The convex hull of the entire set S is composed of the lower and upper hull.
Fig: Upper and lower hulls of a set of

points

Page 41 of 120
Fig: The idea of quick hull
 Finding points farthest away from line P1P2 can be done in linear time.
 Time efficiency: T(n) = T(x) + T(y) + T(z) + T(v) + O(n), where x + y + z +v <=
n.
7. Explain in detail about closest pair problem.
 Find the two closest points in a set of n points (in the two-dimensional
Cartesian plane).It computes the distance between every pair of distinct points and return
the indexes of the points for which the distance is the smallest.
Algorithm
 Step 0 Sort the points by x (list one) and then by y (list two).
 Step 1 Divide the points given into two subsets S1 and S2 by a vertical line x = c
so that half the points lie to the left or on the line and half the points lie to the right or
on the line.
 Step 2 Find recursively the closest pairs for the left and right subsets.
 Step 3 Set d = min{d1, d2}
 Limit the attention to the points in the symmetric vertical strip of width
2d as possible closest pair. Let C1 and C2 be the subsets of points in
the left subset S1 and of the right subset S2, respectively, that lie in
this vertical strip. The points in C1 and C2 are stored in increasing
order of their y coordinates, taken from the second list.
 Step 4 For every point P(x,y) in C1, we inspect points in C2 that may be closer to
P than d. There can be no more than 6 such points (because d ≤ d2)!

Page 42 of 120
Time Complexity:
 Running time of the algorithm (without sorting) is:
 T(n) = 2T(n/2) + M(n), where M(n)
Θ(n)
 By the Master Theorem (with a = 2, b = 2, d = 1)
 T(n) Θ(n log n)
 So the total time is Θ(n log n).
PART-C
1. Explain the method used for performing Multiplication of two large

integers.(May/June 2016)
Some applications like modern cryptography require manipulation of integers that
are over
100 decimal digits long. Since such integers are too long to fit in a single word of a
modern computer, they require special treatment.
In the conventional pen-and-pencil algorithm for multiplying two n-digit integers, each of the
n digits of the first number is multiplied by each of the n digits of the second number for the
total of n2 digit multiplications.
The divide-and-conquer method does the above multiplication in less than n2 digit
multiplications.
Example:
23 ∗ 14 = (2 • 101 + 3 • 100) ∗ (1 • 101 + 4 • 100)
= (2 ∗ 1)102 + (2 ∗ 4 + 3 ∗ 1)101 + (3 ∗ 4)100
= 2• 102 + 11• 101 + 12• 100
= 3• 102 + 2• 101 + 2• 100
= 322
The term (2 ∗ 1 + 3 ∗ 4) computed as 2 ∗ 4 + 3 ∗ 1= (2 + 3) ∗ (1+ 4) – (2 ∗ 1) − (3 ∗ 4). Here
(2 ∗ 1) and (3 ∗ 4) are already computed used. So only one multiplication only we have to
do. For any pair of two-digit numbers a = a1a0 and b = b1b0, their product c can be
computed by the formula c = a ∗ b = c2102 + c1101 + c0,
where

Page 43 of 120
c2 = a1 ∗ b1 is the product of their first digits,

c0 = a0 ∗ b0 is the product of their second digits,
c1 = (a1 + a0) ∗ (b1 + b0) − (c2 + c0) is the product of the sum of the a‘s digits
and the sum of the b‘s digits minus the sum of c2 and c0.
Now we apply this trick to multiplying two n-digit integers a and b where n is a
positive even number. Let us divide both numbers in the middle to take advantage of the
divide-and- conquer technique. We denote the first half of the a‘s digits by a1 and the
second half by a0; for b,
the notations are b1 and b0, respectively. In these notations, a = a1a0 implies that
a = a110n/2 + a0and b = b1b0 implies that b = b110n/2 + b0. Therefore, taking advantage
of the same trick we used for two-digit numbers, we get
C = a ∗ b = (a110n/2 + a0) * (b110n/2 + b0)
= (a1 * b1)10n + (a1 * b0 + a0 * b1)10n/2 + (a0 * b0)
= c210n + c110n/2 + c0,
where
c2 = a1 * b1 is the product of their first halves,
c0 = a0 * b0 is the product of their second halves,
c1 = (a1 + a0) * (b1 + b0) − (c2 + c0)
If n/2 is even, we can apply the same method for computing the products c2, c0, and c1.
Thus, if n is a power of 2, we have a recursive algorithm for computing the product of two
n-digit integers. In its pure form, the recursion is stopped when n becomes 1. It can also be
stopped when we deem n small enough to multiply the numbers of that size directly.
2. Solve the problem using Strassen’s Multiplication.
// Step 1: Split A and B into half-sized matrices of size 1x1 (scalars).
def a11 = 1
defa12 =3
def a21 = 7
def a22 = 5
def b11 = 6
def b12 = 8
def b21 = 4
def b22 = 2
// Define the "S" matrix.

def s1 = b12 - b22 // 6
def s2 = a11 + a12 // 4
def s3 = a21 + a22 // 12
def s4 = b21 - b11 // -2
def s5 = a11 + a22 // 6
def s6 = b11 + b22 // 8
Page 44 of 120
def s7 = a12 - a22 // -2

def s8 = b21 + b22 // 6
def s9 = a11 - a21 // -6
def s10 = b11 + b12 // 14
// Define the "P" matrix.

def p1 = a11 * s1 // 6
def p2 = s2 * b22 // 8
def p3 = s3 * b11 // 72
def p4 = a22 * s4 // -10
def p5 = s5 * s6 // 48
def p6 = s7 * s8 // -12
def p7 = s9 * s10 // -84
// Fill in the resultant "C" matrix.

def c11 = p5 + p4 - p2 + p6 // 18
def c12 = p1 + p2 // 14
def c21 = p3 + p4 // 62
def c22 = p5 + p1 - p3 - p7 // 66
RESULT:
C= [ 18 14]
[ 62 66]

Page 45 of 120
UNIT III - DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE
Computing a Binomial Coefficient – Warshall‗s and Floyd‗s algorithm – Optimal

Binary Search Trees – Knapsack Problem and Memory functions. Greedy
Technique– Prim‟s algorithm- Kruskal's Algorithm- Dijkstra's Algorithm-Huffman
Trees.
PART – A
1. What do you mean by dynamic programming? April / May 2015

Dynamic programming is an algorithm design method that can be
used when a solution to the problem is viewed as the result of sequence
of decisions. Dynamic programming is a technique for solving problems with
overlapping sub problems. These sub problems arise from a recurrence relating
a solution to a given problem with solutions to its smaller sub problems only
once and recording the results in a table from which the solution to the
original problem is obtained. It was invented by a prominent U.S
Mathematician, Richard Bellman in the 1950s.
2. List out the memory functions used under dynamic programming. April / May
2015
Let V[i,j] be optimal value of such an instance. Then

V[i,j]= max {V[i-1,j], vi + V[i-1,j- wi]} if j- wi 0
V[i-1,j] if j- wi < 0
Initial conditions: V[0,j] = 0 for j>=0 and V[i,0] = 0 for i>=0
3. Define optimal binary search tree. April / May 2010

An optimal binary search tree (BST), is a binary search tree which
provides the smallest possible search time (or expected search time) for
a given sequence of accesses (or access probabilities).
4. List out the advantages of dynamic programming. May / June 2014

 Optimal solutions to sub problems are retained so as to avoid re
computing their values.
 Decision sequences containing subsequences that are sub optimal are not
considered.
 It definitely gives the optimal solution always.
5. State the general principle of greedy algorithm. Nov / Dec 2010

Greedy technique suggests a greedy grab of the best alternative available in the
hope that a sequence of locally optimal choices will yield a globally optimal
solution to the entire problem. The choice must be made as follows

Page 46 of 120
 Feasible: It has to satisfy the problems constraints

 Locally optimal: It has to be the best local choice among all feasible
choices available on that step.
 Irrevocable: Once made, it cannot be changed on a subsequent step of the
algorithm
6. State the principle of optimality. Nov / Dec 2010 (Nov/Dec 2016)

It states that an optimal sequence of decisions has the property that
whenever the initial stage or decisions must constitute an optimal sequence with
regard to stage resulting from the first decision.
. Compare dynamic programming and greedy algorithm. Nov / Dec 2010
Greedy method:
1. Only one sequence of decision is generated.
2. It does not guarantee to give an optimal solution always.
Dynamic programming:
1. Many number of decisions are generated.
2. It definitely gives an optimal solution always.
8. What is greedy algorithm? Nov / Dec 2011

A greedy algorithm is a mathematical process that looks for
simple, easy-to- implement solutions to complex, multi-step problems by
deciding which next step will provide the most obvious benefit. Such
algorithms are called greedy because
while the optimal solution to each smaller instance will provide an immediate
output, the algorithm doesn‘t consider the larger problem as a whole.
Once a decision has been made, it is never reconsidered. A greedy algorithm
works as follows:
 Determine the optimal substructure of the problem.
 Develop a recursive solution.
 Prove that at any stage of recursion one of the optimal choices is
greedy choice. Thus it is always safe to make greedy choice.
 Show that all but one of the sub problems induced by having made the
greedy choice is empty.
 Develop a recursive algorithm and convert into iterative algorithm.
9. What is the drawback of greedy algorithm? May / June 2012

The disadvantage of greedy algorithm is that it is entirely possible
that the most optimal short-term solutions may lead to the worst
possible long-term outcome.
10. What is 0/1 knapsack problem? Nov / Dec 2013

Given a set of N item (vi, wi), and a container of capacity C, find a subset of
the items that maximizes the value ∑ vi while satisfying the
weight constraints ∑ wi< C. A greedy algorithm may consider the items in
order of decreasing value-per-unit weight vi/wi. Such an approach

Page 47 of 120
guarantees a solution with value no worst than 1/2 the optimal solution.
11. Write an algorithm to compute the binomial coefficient.

Algorithm Binomial(n,k)
//Computes C(n,k) by the dynamic programming algorithm
//Input: A pair of nonnegative integers n>=k>=0
//Output: The value of C(n,k)
for i ← 0 to n do
for j ←0 to min(i,k) do if j=0 or j=i
C[i,j] ←1
else C[i,j] ← C[i-1,j-1]+C[i-1,j]
return C[n,k]
12. Devise an algorithm to make a change using the greedy strategy.

Algorithm Change(n, D[1..m])
//Implements the greedy algorithm for the change-making problem
//Input: A nonnegative integer amount n and
// a decreasing array of coin denominations D
//Output: Array C[1..m] of the number of coins of each denomination
// in the change or the ‖no solution‖ message for i ← 1 to m do
C[i] ← n/D[i]
n ← n mod D[i]
if n = 0 return C
else return ‖no solution‖
13. What is the best algorithm suited to identify the topography for
a graph. Mention its efficiency factors. (Nov/Dec 2015)
Prim and Kruskal‘s are the best algorithm suited to identify the topography of graph
14. What is spanning tree and minimum spanning tree?

Spanning tree of a connected graph G: a connected acyclic sub graph of
G that includes all of G‗s vertices
Minimum spanning tree of a weighted, connected graph G: a spanning tree
of G of the minimum total weight
15. Define the single source shortest path problem. (May/June 2016)
(Nov/Dec 2016)
Dijkstra‗s algorithm solves the single source shortest path problem of finding
shortest paths from a given vertex( the source), to all the other vertices of a
weighted graph or digraph. Dijkstra‗s algorithm provides a correct solution for a
graph with non-negative weights.
PART-B
1. Write down and explain the algorithm to solve all pair shortest path
algorithm. April / May 2010

Page 48 of 120
Write and explain the algorithm to compute all pair source shortest
path using dynamic programming. Nov / Dec 2010
Explain in detail about Floyd’s algorithm. (Nov/Dec 2016)
ALL PAIR SHORTEST PATH

It is to find the distances (the length of the shortest paths) from each
vertex to all other vertices.
It‗s convenient to record the lengths of shortest paths in an n x n
matrix D called distance matrix.
It computes the distance matrix of a weighted graph with n vertices thru
a series of n x n matrices.
D0, D (1), …… D (k-1) , D (k),…… D(n)
Algorithm
//Implemnt Floyd‗s algorithm for the all-pairs shortest-paths problem
// Input: The weight matrix W of a graph
// Output: The distance matrix of the shortest paths lengths
D← w
for k ← 1 to n do
for i ← 1 to n do for j← 1 to n do
D[i,j] min {D[i,j], D[i,k] + D[k,j]}
Return D.
Example:

Page 49 of 120
Weigh Matrix Distance Matrix
2. Write the algorithm to compute the 0/1 knapsack problem using

dynamic programming and explain i Nov / Dec 2010, April / May 2015
Nov/Dec15

Page 50 of 120
KNAPSACK PROBLEM
Given n items of integer weights: w1 w2 … wn , values: v1 v2 … vn
and a knapsack of integer capacity W find most valuable subset of the items that
fit into the knapsack.
Consider instance defined by first i items and capacity j (j W).
Let V[i,j] be optimal value of such an instance. Then max
The Recurrence:
 To design a dynamic programming algorithm, we need to derive a
recurrence relation that expresses a solution to an instance of the
knapsack problem in terms of solutions to its smaller sub instances.
 Let us consider an instance defined by the first i items, 1≤i≤n, with
weights w1, ... , wi, values v1, ... , vi, and knapsack capacity j, 1 ≤j ≤
W. Let V[i, j] be the value of an optimal solution to this instance, i.e.,
the value of the most valuable subset of the first i items that fit into the
knapsack of capacity j.
Divide all the subsets of the first i items that fit the knapsack of
capacity j into two categories: those that do not include the ith item
and those that do.
Two possibilities for the most valuable subset for the sub problem P(i, j)
i. It does not include the ith item: V[i, j] = V[i-1, j]
ii. It includes the ith item: V[i, j] = vi+ V[i-1, j – wi] V[i, j] = max{V[i-1, j], vi+
V[i-1, j – wi] }, if j – wi 0

Page 51 of 120
Example: Knapsack of capacity W = 5
item weight value

1 2 $12
2 1 $10
3 3 $20
4 2 $15
0 1 2 3 4 5
0 0 0 0
w1 = 2, v1= 1 0 0 12
122 = 1, v2=
w 2 0 10 12 22 22 2
10
w3 = 3, v3= 3 0 10 12 22 30 2
3
w20
4 = 2, v4= 4 15 25 30 0 10 2
3
15 7
Thus, the maximal value is V[4, 5] = $37.
Composition of an optimal subset:

 The composition of an optimal subset can be found by tracing back the
computations of this entry in the table.
 Since V[4, 5] ≠ V[3, 5], item 4 was included in an optimal solution along
with an optimal subset for filling 5 - 2 = 3 remaining units of the knapsack
capacity.
 The latter is represented by element V[3, 3]. Since V[3, 3] = V[2, 3], item
3 is not a part of an optimal subset.
 Since V[2, 3] ≠ V[l, 3], item 2 is a part of an optimal selection, which leaves
element
o V[l, 3 -1] to specify its remaining composition.
 Similarly, since V[1, 2] ≠ V[O, 2], item 1 is the final part of the optimal solution
{item
o 1, item 2, item 4}.
Efficiency:
 The time efficiency and space efficiency of this algorithm are both in
Θ(n W).
 The time needed to find the composition of an optimal solution is in O(n
+ W).

Page 52 of 120
3. Write an algorithm to construct an optimal binary search tree with

suitable example.
OPTIMAL BINARY SEARCH TREE Problem:

Given n keys a1 < …< an and probabilities p1,
…, pn searching for them, find a BST with a minimum average
number of comparisons in successful search.Since total number of BSTs with n
nodes is given by C(2n,n)/(n+1), which grows exponentially, brute force is
hopeless.
Let C[i,j] be minimum average number of comparisons made in T[i,j],

optimal BST for keys ai < …< aj , where 1 ≤ i ≤ j ≤ n. Consider optimal BST
among all BSTs with some ak (i ≤ k ≤ j ) as their root; T[i,j] is the best among them.
The recurrence for C[i,j]:

C[i,j] = min {C[i,k-1] + C[k+1,j]} + ∑ ps for 1 ≤ i ≤ j ≤ n
C[i,i] = pi for 1 ≤ i ≤ j ≤ n
C[i, i- 1] = 0 for 1≤ i ≤ n+1 which can be interpreted as the number of
comparisons in the empty tree.
0 1 j n
1 0 p1 goal
p2
i C[i,j]
EXAMPLE

Page 53 of 120
Let us illustrate the algorithm by applying it to the four key set we used at the beginning of
this section:
KEY A B C D
PROBABILITY 0.1 0.2 0.4 0.3
Initial Tables:
Main Table Root Table
0 1 2 3 4 0 1 2 3 4
1 0 0.1 1 1
2 0 0.2 2 2
3 0 0.4 3 3
4 0 0.3 4 4
5 0 5
C(1,2): [i=1, j=2]
Possible key values k=1 and k=2.
K=1: c(1,2) = c(1,0) + c(2,2) + 0.1 + 0.2 = 0 + 0.2 + 0.1 + 0.2 = 0.5
K=2: c(1,2) = c(1,1) + c(3,2) + 0.1 + 0.2 = 0.1 + 0 + 0.1 + 0.2 = 0.4
0 1 2 3 4 0 1 2 3 4
1 0 0.1 0.4 1 1 2

Page 54 of 120
2 0 0.2 2 2
3 0 0.4 3 3
4 0 0.3 4 4
5 0 5
C(2,3): [i=2, j=3]
K=2: c(2,3) = c(2,1) + c(3,3) + 0.2 + 0.4 = 0 + 0.4 + 0.2 + 0.4 = 1.0
K=3: c(2,3) = c(2,2) + c(4,3) + 0.2 + 0.4 = 0.2 + 0 + 0.2 + 0.4 = 0.8
0 1 2 3 4 0 1 2 3 4
1 0 0.1 0.4 1 1 2
2 0 0.2 0.8 2 2 3
3 0 0.4 3 3
4 0 0.3 4 4
5 0 5
C(3,4): [i=3, j=4]

Page 55 of 120
K=3: c(3,4) = c(3,2) + c(4,4) + 0.4 + 0.3 = 0 + 0.3 + 0.4 + 0.3 = 1.0
K=4: c(3,4) = c(3,3) + c(5,4) + 0.4 + 0.3 = 0.4 + 0 + 0.4 + 0.3 = 1.1
0 1 2 3 4 0 1 2 3 4
1 0 0.1 0.4 1 1 2
2 0 0.2 0.8 2 2 3
3 0 0.4 1.0 3 3 3
4 0 0.3 4 4
5 0 5
C(1,3): [i=1, j=3]
Possible key values k=1, k=2 and k=3.
K=1: c(1,3) = c(1,0) + c(2,3) + 0.1 + 0.2 + 0.4 = 0 + 0.8 + 0.1 + 0.2 + 0.4 = 1.5
K=2: c(1,3) = c(1,1) + c(3,3) + 0.1 + 0.2 + 0.4 = 0.1 + 0.4 + 0.1 + 0.2 + 0.4 = 1.2
K=3: c(1,3) = c(1,2) + c(4,3) + 0.1 + 0.2 + 0.4 = 0.4 + 0 + 0.1 + 0.2 + 0.4 = 1.1
0 1 2 3 4 0 1 2 3 4
1 0 0.1 0.4 1.1 1 1 2 3
2 0 0.2 0.8 2 2 3
3 0 0.4 1.0 3 3 3

Page 56 of 120
4 0 0.3 4 4
5 0 5
C(2,4): [i=2, j=4]
Possible key values k=2, k=3 and k=4.
K=2: c(2,4) = c(2,1) + c(3,4) + 0.2 + 0.4 + 0.3 = 0 + 1.0 + 0.2 + 0.4 + 0.3 = 1.9
K=3: c(2,4) = c(2,2) + c(4,4) + 0.2 + 0.4 + 0.3 = 0.2 + 0.3 + 0.2 + 0.4 + 0.3 = 1.4
K=4: c(2,4) = c(2,3) + c(5,4) + 0.2 + 0.4 + 0.3 = 0.8 + 0 + 0.2 + 0.4 + 0.3 = 1.7
0 1 2 3 4 0 1 2 3 4
1 0 0.1 0.4 1.1 1 1 2 3
2 0 0.2 0.8 1.4 2 2 3 3
3 0 0.4 1.0 3 3 3
4 0 0.3 4 4
5 0 5
C(1,4): [i=1, j=4]
Possible key values k=1, k=2, k=3 and k=4.
K=1: c(1,4)=c(1,0)+c(2,4)+0.1+0.2+0.4+0.3= 0 + 1.4 + 0.1+ 0.2 + 0.4 + 0.3 = 2.4
K=2: c(1,4)=c(1,1)+c(3,4)+0.1+0.2+0.4+0.3= 0.1 + 1.0 + 0.1+ 0.2 + 0.4 + 0.3 = 2.1
K=3: c(1,4)=c(1,2)+c(4,4)+0.1+0.2+0.4+0.3= 0.4 + 0.3 + 0.1+ 0.2 + 0.4 + 0.3 = 1.7

Page 57 of 120
K=4: c(1,4)=c(1,3)+c(5,4)+0.1+0.2+0.4+0.3= 1.1 + 0 + 0.1+ 0.2 + 0.4 + 0.3 = 2.1
0 1 2 3 4 0 1 2 3 4
1 0 0.1 0.4 1.1 1.7 1 1 2 3 3
2 0 0.2 0.8 1.4 2 2 3 3
3 0 0.4 1.0 3 3 3
4 0 0.3 4 4
5 0 5
Thus, the average number of key comparisons in the optimal tree is equal to
1.7.
Since R(1, 4) = 3, the root of the optimal tree contains the third key, i.e., C.
Its left subtree is made up of keys A and B, and its right subtree contains just
key D.
Since R(1, 2) = 2, the root of the optimal tree containing A and B is B, with A
being its left child (and the root of the one node tree: R(1, 1) = 1).

Page 58 of 120
4. Explain in detail about Prim’s and Kruskal’s algorithm. (Nov/Dec 2016)

(Nov/Dec 15) Explain in detail about the algorithm which is used to
find the minimum spanning tree of a graph.
MINIMUM SPANNING TREE

Definition : A spanning tree of a connected graph is its connected acyclic
subgraph (i.e., a tree) that contains all the vertices of the graph
A minimum spanning tree of a weighted connected graph is its spanning tree of

the smallest weight, where the weight of a tree is defined as the sum of the
weights on all its edges. The minimum spanning tree problem is the problem of
finding a minimum spanning tree for a given weighted connected graph.

Page 59 of 120
Graph and its spanning trees; T 1 is the minimum

spanning tree
Prims’s Algorithm:
 Prim's algorithm constructs a minimum spanning tree through
a sequence of expanding sub trees.
 The initial sub tree in such a sequence consists of a single vertex
selected arbitrarily from the set V of the graph's vertices.
 On each iteration, the current tree is expanded in the greedy
manner by simply attaching to it the nearest vertex not in that tree.
 The algorithm stops after all the graph's vertices have been included
in the tree being constructed.
Since the algorithm expands a tree by exactly one vertex on each of its
iterations, the total number of such iterations is n - 1, where n is the number of
vertices in the graph. The tree generated by the algorithm is obtained as the set
of edges used for the tree expansions.

Page 60 of 120
Kruskals’s Algorithm:
o Discovered by Joseph Kruskal
o Constructs a minimum spanning tree for a weighted connected graph
G= (V, E) as an acyclic sub graph with |V| - 1 edges for which the sum
of edge weights is the smallest.
Procedure – Krusal’s Algorithm:

Page 61 of 120
o Sorted the edges in non decreasing order of weights.

o Grow the tree one edge at a time to procedure MST through a
series of expanding forests F1F2,……..Fn-1
o On each iteration , add the next edge on the sorted list unless
this would create a cycle. If, it would skip the edge.
o Algorithm stops when all vertices are included
ALGORITHM Kruskal(G)
//Kruskal's algorithm for constructing a minimum spanning tree
//Input: A weighted connected graph G = (V, E)
//Output: ET, the set of edges composing a minimum spanning tree of G
sort E in nondecreasing order of the edge weights w(e1) ≤ ...≤ w(ei|E|)
ET ←ϕ; ecounter ←0 //initialize the set of tree edges and its size
k ←0 //initialize the number of
processed edges while ecounter <
|V|- 1 do
k ←k+l
if ET U[eik} is acyclic
ET ←ET U ET {eik}; ecounter +--- ecounter + 1
returnET
Example:

Page 62 of 120
5. Let Compute the Huffman coding to compress the data effectively and
encode theString _AB_D. April / May 2015 (Nov/Dec 15)
Character A B C D _
Frequency 0.3 0.1 0.2 0.2 0.1

5 5
HUFFMAN CODING
Any binary tree with edges labeled with 0‗s and 1‗s yields a prefix-free code of
characters assigned to its leaves. Optimal binary tree minimizing the average
length of a code word can be constructed as follows:
Huffman’s algorithm
 Initialize n one-node trees with alphabet characters and the tree
weights with their frequencies.
 Repeat the following step n-1 times: join two binary trees with smallest weights
into one (as left and right subtrees) and make its weight equal the sum of the
weights of the two trees.
Mark edges leading to left and right subtrees with 0‗s and 1‗s, respectively.
Example:
character A B C D _
codeword 0.35 0.1 0.2 0.2 0.15

Page 63 of 120
Encoded bit string of _AB_D is 1011110010101
PART-C
1. Discuss about the algorithm and pseudocode to find the Minimum
Spanning Tree using Prim’s Algorithm. Find the Minimum Spanning Tree
for the graph shown below. And Discuss about the
efficiency of the algorithm. (May/June 16)
A spanning tree of an undirected connected graph is its connected acyclic

subgraph (i.e., a tree) that contains all the vertices of the graph. If such a graph
has weights assigned to its edges, a minimum spanning tree is its spanning tree
of the smallest weight, where the weight of a tree is defined as the sum of the
weights on all its edges. The minimum spanning tree problem is the problem
of finding a minimum spanning tree for a given weighted connected graph.
ALGORITM
Prim(G
)
//Prim‗s algorithm for constructing a minimum spanning tree
//Input: A weighted connected graph G = {V, E}
//Output: ET, the set of edges composing a minimum
spanning tree of G VT←{v0} //the set of tree vertices can
be initialized with any vertex ET←Φ
for i ←1 to |V| − 1 do

Page 64 of 120
find a minimum-weight edge e∗ = (v∗, u∗) among all the edges (v, u)
Minimum spanning tree cost = 2+3+1 = 6

2. Find all the solution to the travelling salesman problem (cities and
distance shown below) by exhaustive search. Give the optimal solutions.
(May/June 2016)

Page 65 of 120
Tour Length
a ---> b ---> c ---> d ---> a I = 2 + 8 + 1 + 7 = 18
a ---> b ---> d ---> c ---> a I = 2 + 3 + 1 + 5 = 11 optimal
a ---> c ---> b ---> d ---> a I = 5 + 8 + 3 + 7 = 23
a ---> c ---> d ---> b ---> a I = 5 + 1 + 3 + 2 = 11 optimal
a ---> d ---> b ---> c ---> a I = 7 + 3 +8 + 5 = 23 a ---> d ---> c ---> b ---> a I=7
+ 1 + 8 + 2 = 18

Page 66 of 120
UNIT IV - ITERATIVE IMPROVEMENT

The Simplex Method-The Maximum-Flow Problem – Maximum Matching in
Bipartite Graphs- the Stable marriage Problem.
PART – A
1. Define Bipartite Graph.

Bipartite graph: a graph whose vertices can be partitioned into two disjoint
sets V and U, not necessarily of the same size, so that every edge
connects a vertex in V to a vertex in U. A graph is bipartite if and only if it
does not have a cycle of an odd length
2. What is perfect matching in Bipartite Graph?

Let Y and X represents the vertices of a complete bipartite
graph with edges connecting possible marriage partners, then a
marriage matching is a perfect matching in such a graph.
3. What is the requirement of flow conservation?

A flow is an assignment of real numbers xij to edges (i,j) of a given
network that satisfy the following:
 flow-conservation requirements: The total amount of
material entering an intermediate vertex must be equal to the total
amount of the material leaving the vertex
 capacity constraints
0 ≤ xij ≤ uij for every edge (i,j) E
4. Differentiate feasible and optimal solution.

Feasible solution is any element of the feasible region of an optimization
problem. The feasible region is the set of all possible solutions of an
optimization problem. An optimal solution is one that either
minimizes or maximizes the objective function.
5. Define augmenting path.

An augmenting path for a matching M is a path from a free vertex in V
to a free vertex in U whose edges alternate between edges not in M and
edges in M
 The length of an augmenting path is always odd
 Adding to M the odd numbered path edges and deleting
from it the even numbered path edges increases the matching
size by 1 (augmentation)
 One-edge path between two free vertices is special case
of augmenting path

Page 67 of 120
6. What is min cut?

Define flow cut. April / May 2015 Nov/Dec 2015
A cut induced by partitioning vertices of a network into some subset X
containing the source and X , the complement of X, containing the sink is
the set of all the edges with a tail in X and a head in X .Capacity of a cut
is defined as the sum of capacities of the edges that compose the cut.
Minimum cut is a cut of the smallest capacity in a given network.
7. What is simplex method?
The simplex method is the classic method for solving the general linear
programming problem. It works by generating a sequence of adjacent
extreme points of the problem's feasible region with improving values of the
objective function.
8. What is blocking pair?

A pair (m, w) is said to be a blocking pair for matching M if man m and
woman w are not matched in M but prefer each other to their mates in M.
9. Determine the Dual linear program for the following LP, Maximize
3a + 2b + c .
Subject to,2a+b+c <=3 a+b+c <=4 3a+3b+6c<=6 a,b,c >= O.
(Nov/Dec 2015) Sol:
The basic solution is a = 0, b = 0, c = 0, d = 30, e = 24, f = 36, i.e. (0,0,0,
30,24,36). z = 0.
10. What is iterative improvement? (Nov/Dec 2016)
The iterative improvement technique involves finding a solution to an
optimization problem by generating a sequence of feasible solutions with
improving values of the problem's objective function. Each subsequent solution
in such a sequence typically involves a small, localized change in the previous
feasible solution. When no such change improves the value of the objective
function, the algorithm returns the last feasible solution as optimal and stops.
11. Define maximum cardinality matching.

(Nov/Dec 2016) Define maximum matching.
A maximum matching - more precisely, a maximum cardinality matching -
is a matching with the largest number of edges.
12. Define flow network.

Flow network is formally represented by a connected weighted digraph
with n vertices numbered from 1 to n with the following properties:
• contains exactly one vertex with no entering edges,
called the source (numbered 1)
• contains exactly one vertex with no leaving edges, called the
sink (numbered n)

Page 68 of 120
• has positive integer weight uij on each directed edge

(i.j), called the edge capacity, indicating the upper bound
on the amount of the material that can be sent from i to j
through this edge
13. When a bipartite graph will become two colorable?

A bipartite graph is 2-colorable: the vertices can be colored in two colors so
that every edge has its vertices colored differently
14. Define linear programming.

Many problems of optimal decision making can be reduced to an instance of
the linear programming problem, which is a problem of optimizing a linear
function of several variables subject to constraints in the form of linear
equations and linear inequalities. maximize (or minimize) c1 x1 + ...+ cn xn
subject to ai 1x1+ ...+ ain xn ≤ (or ≥ or =) bi , i = 1,...,m x1 ≥ 0, ... , xn ≥ 0
The function z = c1 x1 + ...+ cn xn is called the objective function;
constraints x1 ≥ 0, ..., xn ≥ 0 are called nonnegativity constraints
15. State Extreme point theorem.(May/June 2016)
Any linear programming problem with a nonempty bounded feasible region
has an optimal solution; moreover, an optimal solution can always be found
at an extreme point of the problem‗s feasible region. Extreme point theorem
states that if S is convex and compact in a locally convex space, then S is
the closed convex hull of its extreme points: In particular, such a set has
extreme points. Convex set has its extreme points at the boundary.
Extreme points should be the end points of the line connecting any two
points of convex set.
16.What is The Euclidean minimum spanning tree problem?(May/June 2016)

The Euclidean minimum spanning tree or EMST is a minimum spanning
tree of a set of n points in the plane where the weight of the edge between
each pair of points is the Euclidean distance between those two points. In
simpler terms, an EMST connects a set of dots using lines such that the total
length of all the lines is minimized and any dot can be reached from any other
by following the lines
17. State how Binomial Coefficient is computed? (Nov/Dec 2015)

C(n,k)=c(n-1,k-
1)+C(n-1,k) And

Page 69 of 120
C(n,0)=1
C(n,n)=1
Where n>k>0
PART – B
1. Discuss in detail about stable marriage problem. (Nov/Dec 2016) Explain in
detail about Gale-Shapley Algorithm.
STABLE MARRIAGE PROBLEM
Consider set Y = {m1,…,mn} of n men and a set X = {w1,…,wn} of n women. Each

man has a ranking list of the women, and each woman has a ranking list of the
men (with no ties in these lists) as given below. The same information can also be
presented by an n-by-n ranking matrix The rows and columns of the matrix
represent the men and women of the two sets, respectively. A cell in row m and
column w contains two rankings: the first is the position (ranking) of w in the
m's preference list; the second is the position (ranking) of m in the w's preference
list.
Marriage Matching:
A marriage matching M is a set of n (m, w) pairs whose members are selected
from disjoint n- element sets Y and X in a one-one fashion, i.e., each man m from
Y is paired with exactly one woman w from X and vice versa.
Blocking Pair:
A pair (m, w), where m ϵ Y, w ϵ X, is said to be a blocking pair for a marriage
matching M if man m and woman w are not matched in M but they prefer each
other to their mates in M. For example, (Bob, Lea) is a blocking pair for the
marriage matching M = (Bob,Ann), (Jim,Lea), (Tom,Sue)} because they are not
matched in M while Bob prefers Lea to Ann and Lea prefers Bob to Jim.
Stable and unstable marriage

matching:
A marriage matching M is called stable if there is no blocking pair for it;
otherwise, M is called unstable.
The stable marriage problem is to find a stable marriage matching for

men's and women's given preferences.

Page 70 of 120
Stable Marriage Algorithm:

Step 0 Start with all the men and women being free
Step 1 While there are free men, arbitrarily select one of them and do the
following: Proposal: The selected free man m proposes to w, the next woman on
his preference list Response: If w is free, she accepts the proposal to be matched
with m. If she is not free, she compares m with her current mate. If she prefers m
to him, she accepts m‗s proposal, making her former mate free; otherwise, she
simply rejects m‗s proposal, leaving m free
Step 2 Return the set of n matched pairs

Page 71 of 120
Analysis of the Gale-Shapley Algorithm

* The algorithm terminates after no more than n with a stable
marriage output iterations
* The stable matching produced by the algorithm is always man-optimal: each
man gets the highest rank woman on his list under any stable marriage. One
can obtain the woman- optimal matching by making women propose to men
* A man (woman) optimal matching is unique for a given set of participant
preferences
* The stable marriage problem has practical applications such as matching
medical- school graduates with hospitals for residency training
2. How do you compute the maximum flow for the following graph
using Ford – Fulkerson method? Explain. (May/June 2016)
MAXIMUM – FLOW PROBLEM (Nov/Dec 2015)

It is the problem of maximizing the flow of a material through a
transportation network (e.g., pipeline system, communications or transportation
networks)
The transportation network in question can be represented by a connected
weighted

Page 72 of 120
digraph with n vertices numbered from 1 to n and a set of edges E, with the
following properties:
 contains exactly one vertex with no entering edges, called the source
(numbered 1)
 contains exactly one vertex with no leaving edges, called the sink
(numbered n)
 has positive integer weight uij on each directed edge (i.j),
called the edge capacity, indicating the upper bound on the
amount of the material that can be sent from i to j through this edge
Flow: A flow is an assignment of real numbers xij to edges (i,j) of a given
network that satisfy the following:
Flow-conservation requirements: The total amount of material entering an
intermediate vertex must be equal to the total amount
of the material
leaving the vertex
Capacity constraints:
j: (1,j) є E j: (j,n) є E
The total outflow from the source or the total inflow into the sink is called the
value of the flow (v). Thus, a (feasible) flow is an assignment of real numbers xij
to edges (i, j) of a given network that satisfy flow-conservation constraints and the
capacity constraints:
0 ≤ xij ≤ uij for every edge (i,j) E
The maximum flow problem can be stated as: Given a network N,
find a flow f of maximum value.
More formally,
Maximize v = ∑ x1j
subject to
j: (1,j) € E
∑ xji - ∑ xij = 0 for i = 2, 3,…,n-1

j: (j,i) € E j: (i,j) € E

Page 73 of 120
Ford Fulkerson Method / Augmentation Path Method:

 Start with the zero flow (xij = 0 for every edge)
 On each iteration, try to find a flow-augmenting path from source
to sink, which a path along which some additional flow can be sent
 If a flow-augmenting path is found, adjust the flow along the edges of
this path to get a flow of increased value and try again
 If no flow-augmenting path is found, the current flow is maximum
Augment Path : 1->2->3->6
Augment Path : 1 →4 →3←2 →5 →6 max flow value = 3
Finding a flow-augmenting path

To find a flow-augmenting path for a flow x, consider paths from
source to sink in the underlying undirected graph in which any two
consecutive vertices i,j are either:
• connected by a directed edge (i to j) with some positive unused
capacity rij =
uij – xij
– known as forward edge ( → )
OR
• connected by a directed edge (j to i) with positive flow xji
– known as backward

Page 74 of 120
edge ( ← )
If a flow-augmenting path is found, the current flow can be increased by r units by

increasing
xij by r on each forward edge and decreasing xji by r on each backward
edge, where
r = min {rij on all forward edges, xji on all backward
edges} Assuming the edge capacities are integers, r is
a positive integer On each iteration, the flow value
increases by at least 1
Maximum value is bounded by the sum of the capacities of the edges
leaving the source;
hence the augmenting-path method has to stop after a finite number of
iterations
The final flow is always maximum; its value doesn‗t depend on a
sequence of augmenting paths used
Shortest-Augmenting-Path Algorithm
Generate augmenting path with the least number of edges by BFS as follows.
Starting at the source, perform BFS traversal by marking new (unlabeled) vertices
with two labels:
• first label – indicates the amount of additional flow that can be
brought from the source to the vertex being labeled
• second label – indicates the vertex from which the vertex
being labeled was reached, with ―+‖ or ―–‖ added to the
second label to indicate whether the vertex was reached via a
forward or backward edge
Labeling of vertex:
 The source is always labeled with ∞,-
 All other vertices are labeled as follows:
 If unlabeled vertex j is connected to the front vertex i of the traversal
queue by a directed edge
 +
 from i to j with positive unused capacity rij = uij –xij (forward edge),
vertex j is labeled with lj,i ,
 where lj = min{li, rij}
 If unlabeled vertex j is connected to the front vertex i of the traversal
queue by a directed edge
 -
 from j to i with positive flow xji (backward edge), vertex j is labeled
lj,i , where lj = min{li, xji}
 If the sink ends up being labeled, the current flow can be augmented
by the amount
 indicated by the
sink‗s first label
 The augmentation of the current flow is performed along the
augmenting path traced by following the vertex second labels from

Page 75 of 120
sink to source; the current flow quantities are increased on the

forward edges and decreased on the backward edges of this path
 If the sink remains unlabeled after the traversal queue becomes
empty, the algorithm returns the current flow as maximum and
stops.

Page 76 of 120
Augment the flow by 2 (the sink‗s first label)

along the path 1→2→3→6
Definition of
a Cut
Let X be a set of vertices in a network that includes its source but does not
include its sink, and let X, the complement of X, be the rest of the vertices
including the sink. The cut induced by this partition of the vertices is the set of
all the edges with a tail in X and a head in X.
Capacity of a cut is defined as the sum of capacities of the edges that
compose the cut.
A cut and its capacity are denoted by C(X,X)
and c(X,X)
Note that if all the edges of a cut were deleted from the network, there
would be no directed path from source to sink

Page 77 of 120
Efficiency:
• The number of augmenting paths needed by the shortest-augmenting-
path algorithm never exceeds nm/2, where n and m are the number of
vertices and edges, respectively
• Since the time required to find shortest
) augmenting path by breadth-first
search is in O(n+m)=O(m) for networks represented by their adjacency lists,
the time efficiency of the shortest-augmenting-path algorithm is in O(nm2 for this
representation
• More efficient algorithms have been found that can run in close to
O(nm) time, but these algorithms don‗t fall into the iterative-
improvement paradigm
3. Write down the optimality condition and algorithmic

implication for finding M- augmenting paths in Bipartite Graph.
BIPARTITE GRAPH
A graph whose vertices can be partitioned into two disjoint sets V and U, not
necessarily of the same size, so that every edge connects a vertex in V to a
vertex in U. A graph is bipartite if and only if it does not have a cycle of an odd
length
A matching in a graph is a subset of its edges with the property that no two
edges share a vertex A maximum (or maximum cardinality) matching is a
matching with the largest number of edges For a given matching M, a vertex is
called free (or unmatched) if it is not an endpoint of any edge inM; otherwise, a
vertex is said to be matched
• If every vertex is matched, then M is a maximum matching
• If there are unmatched or free vertices, then M may be able to be improved
• We can immediately increase a matching by adding an edge
connecting two free vertices (e.g., (1,6) above)
Augmentation path and Augmentation:

An augmenting path for a matching M is a path from a free vertex in V to a
free vertex in U whose edges alternate between edges not in M and edges in M
• The length of an augmenting path is always odd
• Adding to M the odd numbered path edges and deleting from it the

Page 78 of 120
even numbered path edges increases the matching size by 1

(augmentation)
• One-edge path between two free vertices is special case of augmenting path
Matching on the right is maximum (perfect matching)
Augmentation Path Method:
Start with some
initial
matching o
e.g., the
empty set
Find an augmenting path and augment the current matching along that path
o e.g., using breadth-first search like method
When no augmenting path can be found, terminate and return
the last matching, which is maximum
BFS-based Augmenting Path Algorithm:
Search for an augmenting path for a matching M by a BFS-like

traversal of the graph that starts simultaneously at all the free vertices
in one of the sets V and U, say V
Initialize queue Q with all free vertices in one of the sets (say V)
While Q is not empty, delete front vertex w and label every unlabeled
vertex u
adjacent to w as follows:
o Case 1 (w is in V): If u is free, augment the matching along the

path ending at u by moving backwards until a free vertex in V is
reached. After that, erase all labels and reinitialize Q with all
the vertices in V that are still free. If u is matched (not with w),
label u with w and enqueue u
o Case 2 (w is in U) Label its matching mate v with w and enqueue v
After Q becomes empty, return the last matching, which is maximum

Page 79 of 120

Page 80 of 120
4. Solve the given linear equations by simplex method.
Maximize P = 3x + 4y
subject to x+3y≤30 ; 2x+y≤20
Step 1: insert slack variable S1 and S2

x+3y+S1=30
2x+y+S2=20
Step 1: Rewrite the objective function

x+3y+S1=30
2x+y+S2=20
-3x-4y-P=0
Step 3: Form the initial simplex tableau

x Y S1 S2 P
1 3 1 0 0 30
2 1 0 1 0 20
-3 -4 0 0 -1 0
Step 4: Find the pivot element

X Y S1 S2 P
1/3 1 1/3 0 0 10
5/3 0 -1/3 1 0 10
-5/3 0 4/3 0 1 40
Repeat the above the step till there is no negative value in the last row
X Y S1 S2 P
0 1 2/5 -1/5 0 8
1 0 -1/5 3/5 0 6
0 0 1 3/5 1 50
P reaches the maximum value of 50 at x=6 and y=8.

Page 81 of 120
5. Write a note on simplex method (May/June 2016) (Nov/Dec 2016)

(Nov/Dec 15)
SIMPLEX METHOD
o The classic method for solving LP problems; one of the most
important algorithms ever invented
o Simplex method was invented by George Dantzig in 1947
o Based on the iterative improvement idea:
o Generates a sequence of adjacent points of the problem‗s feasible
region with improving values of the objective function until no further
improvement is possible
o Standard Linear Programming
Problem:
o must be a maximization problem
o all constraints (except the non negativity constraints) must be
in the form of linear equations
o all the variables must be required to be nonnegative
 Thus, the general linear programming problem in
standard form with m
constraints and n unknowns (n ≥ m) is
maximize c1 x1 +
...+ cn xn
subject to ai 1x1+ ...+ ain xn = bi , i = 1,...,m,
x1 ≥ 0, ... ,
xn ≥ 0
Every LP problem can be represented in such for
maximize 3x + 5y maximize 3x + 5y + 0u + 0v
subject to x + y ≤ 4 subject to x
+ y+ u=4
x + 3y ≤ 6 x + 3y + v = 6
x≥0, y≥0 x≥0, y≥0, u≥0, v≥0
Variables u and v, transforming inequality constraints into equality

constrains, are called slack variables
A basic solution to a system of m linear equations in n unknowns (n ≥
m) is obtained by setting n – m variables to 0 and solving the resulting
system to get the values of the other m variables. The variables set to 0 are
called non basic; the variables obtained by solving the system are called basic.
A basic solution is called feasible if all its (basic) variables are nonnegative.
Example x + y + u =4
x + 3y +
v =6
(0, 0, 4, 6) is basic feasible solution
(x, y are nonbasic; u, v

Page 82 of 120
There is a 1-1 correspondence between extreme points of LP‗s feasible

region and its basic feasible solutions.
Outline of Simplex Method:

Step 0 [Initialization] Present a given LP problem in standard
form and set up initial tableau.
Step 1 [Optimality test] If all entries in the objective row are nonnegative -
stop: the tableau
represents an optimal solution.
Step 2 [Find entering variable] Select (the most) negative
entry in the objective row. Mark its column to indicate the entering
variable and the pivot column.
Step 3 [Find departing variable] For each positive entry in the

pivot column, calculate the θ-ratio by dividing that row's entry in the
rightmost column by its entry in the pivot column. (If there are no positive
entries in the pivot column — stop: the problem is unbounded.) Find the
row with the smallest θ-ratio, mark this row to indicate the departing
variable and the pivot row.
Step 4 [Form the next tableau] Divide all the entries in the pivot row by its
entry in the pivot column. Subtract from each of the other rows, including
the objective row, the new pivot row multiplied by the entry in the pivot
column of the row in question. Replace the label of the pivot row by the
variable's name of the pivot column and go back to Step 1.

Page 83 of 120
PART-C
1. State and Prove Maximum Flow Min cut Theorem. (May/June
2016) (Nov/Dec 16) Maximum Flow Problem

Problem of maximizing the flow of a material through a
transportation network (e.g., pipeline system, communications or transportation
networks)
Formally represented by a connected weighted digraph with n vertices
numbered from 1 to n with the following properties:
• Contains exactly one vertex with no entering edges, called the source
(numbered 1)
• Contains exactly one vertex with no leaving edges, called the sink
(numbered n)
• Has positive integer weight uij on each directed edge (i.j), called
the edge capacity, indicating the upper bound on the amount of the
material that can be sent from i to j through this edge.
A digraph satisfying these properties is called a flow network or simply a network
Flow value and Maximum Flow Problem
Since no material can be lost or added to by going through intermediate

vertices of the network, the total amount of the material leaving the source must
end up at the sink:
∑ x1j =
∑ xjn j: (1,j) є
E j: (j,n) є E
The value of the flow is defined as the total outflow from the source (= the total
inflow into the sink). The maximum flow problem is to find a flow of the largest
value (maximum flow) for a given network.
Max-Flow Min-Cut Theorem
1. The value of maximum flow in a network is equal to the capacity of its

minimum cut
2. The shortest augmenting path algorithm yields both a maximum flow and a
minimum cut:
• Maximum flow is the final flow produced by

the algorithm
• Minimum cut is formed by all the edges from the labeled

vertices to unlabeled vertices on the last iteration of the algorithm.

Page 84 of 120
• All the edges from the labeled to unlabeled vertices are full, i.e.,
their flow amounts are equal to the edge capacities, while all the
edges from the unlabeled to labeled vertices, if any, have zero flow
amounts on them.

Page 85 of 120
UNIT V - COPING WITH THE LIMITATIONS OF

ALGORITHM POWER
Limitations of Algorithm Power-Lower-Bound Arguments-Decision Trees-P, NP

and NP- Complete Problems--Coping with the Limitations - Backtracking – n-
Queens problem – Hamiltonian Circuit Problem – Subset Sum Problem-Branch
and Bound – Assignment problem – Knapsack Problem – Traveling Salesman
Problem- Approximation Algorithms for NP – Hard Problems – Traveling
Salesman problem – Knapsack problem.
PART – A
1. Differentiate explicit and implicit constraint. Nov/Dec 2012, April/May

2012
Explicit constraints are "boundary conditions", that is they are set up as part of
the problem.
Implicit constraints are those constraints determined by the solution path.
2. What is live node and dead node? April / May 2012

Live Node: A node which has been generated and all of whose children are not
yet been generated. Dead Node: A node that is either not to be expanded further,
or for which all of its children have been generated.
3. Give the idea behind backtracking. Nov / Dec 2011

State the principle of backtracking. May / June 2013
The principal idea is to construct solutions one component at a time and
evaluate such partially constructed candidates as follows. If a partially constructed
solution can be developed further without violating the problem's constraints, it is
done by taking the first remaining legitimate option for the next component. If there
is no legitimate option for the next component, no alternatives for any remaining
component need to be considered. In this case, the algorithm backtracks to
replace the last component of the partially constructed solution with its next option.
This process is continued until the complete solution is obtained.
4. Define NP Hard and NP Completeness. Nov / Dec 2010, 2011

Class NP is the class of decision problems that can be solved by nondeterministic
polynomial algorithms. This class of problems is called non deterministic
polynomial. NP – Hard: If a problem is NP-Hard, this means that any problem in
NP can be reduced to the given problem. NP – Complete: a decision problem is NP
– complete when it is both in NP and P –hard.
5. What is promising and non-promising node?

Promising Node: A node in a state-space tree is said to be promising if it
corresponds to a partially constructed solution that may still lead to a complete

Page 86 of 120
solution.
Non Promising Node: A node in a state-space tree is said to be non-
promising if it backtracks to the node‗s parent to consider the nest possible
solution for its last component.
6. Depict the proof which says that a problem 'A' is no harder or no

easier than problem 'B' (Nov/Dec 2015)
Thus, motivation for <=p notation. A is no harder than B. Given B, we can
implement A. But, maybe we can also implement A without using B.
7. Mention the property of NP Complete problem. Nov / Dec 2012, 2013

A decision problem D is said to be NP complete if
 it belongs to class NP;
 every problem in NP is polynomially reducible to D
8. What is Hamiltonian cycle? Nov / Dec 2013

A Hamiltonian circuit or Hamiltonian cycle is defined as a cycle that passes
through all the vertices of the graph exactly once. It is named after the Irish
mathematician Sir William Rowan Hamilton (1805-1865), who became interested
in such cycles as an application of his algebraic discoveries. A Hamiltonian circuit
can be also defined as a sequence of n + 1 adjacent vertices vi0,vi1…….vin,vi0
where the first vertex of the sequence is the same as the last one while all the
other n - 1 vertices are distinct
9. State sum of subset problem. May / June 2013

Subset-sum problem: The subset sum problem is to find a subset of a given set
S= {s1, ... , sn} of n positive integers whose sum is equal to a given positive integer
d. For example, for S = {1, 2, 5, 6, 8} and d = 9, there are two solutions: {1, 2, 6 and
{1, 8}.
10. Define decision tree. (Nov/Dec 2016)

A decision tree is a tree data structure in which each vertex represents a question
and each descending edge from that vertex (child nodes) represents a possible
answer to that question. The performance of the algorithm whose basic operation is
comparison could be studied using decision tree.
11. Compare backtracking and branch and bound technique. April / May
2015
Backtracking Technique Branch and Bound technique
Backtracking constructs its state- Branch-and-bound is an algorithm
space tree in the depth-first search design technique that enhances
fashion in the majority of its the idea of generating a state-
applications. space tree with the idea of estimating
the best value obtainable from a
current node of the decision tree.

Page 87 of 120
If the sequence of choices If the estimate is not superior to the

represented by best solution seen up to that
a current node of the state-space tree point in the processing, the node
can be developed further without is eliminated from further
violating the problem's constraints, it consideration.
is done by considering the first
remaining legitimate option for the
next component. Otherwise, the
method backtracks by undoing the
last component of the partially built
solution and replaces it by the next
12. Define state space tree.
alternative. April / May 2015,May/June 2016
The processing of backtracking is implemented by constructing a tree of
choices being made. This is called the state-space tree. choices made for the first
component of the solution; the nodes in the second level represent the choices
for the second component and so on.
13. How NP – hard problem is different from NP complete? April / May

2015
NP – hard NP complete
If a problem is NP-Hard, this means A decision problem is NP –
that any problem in NP can be complete when it is both in NP and
reduced to the given problem. NP – hard.
14. State the reason for terminating search path at the current node in
branch bound algorithm (Nov/Dec 2016)
The value of the node's bound is not better than the value of the best solution seen
so far. The node represents no feasible solutions because the constraints of the
problem are already violated.
PART – B
1. Explain in detail about how the n – queen’s problem is

solved using backtracking. (Nov/Dec 2016)
N – QUEEN’S PROBLEM
The problem is to place n queens on an n-by-n chessboard so that no
two queens attack each other by being in the same row or in the same
column or on the same diagonal. For n = 1, the problem has a trivial solution,
and it is easy to see that there is no solution for n = 2 and n = 3.
Algorithm
place(k,I)
{

Page 88 of 120
for j := 1 to k-1 do
if(x[j]=I) or(abs(x[j]-I)=abs(j-k))) then return false;
return true;
}
Algorithm Nqueens(k,n)
{
for I:= 1 to n do
{
if( place(k,I) then
{
x[k]:= I;
if(k=n) then write(x[1:n]);
else
Nqueens(k
+1,n)
}
}
}
Example
N=4
2. Discuss in detail about Hamiltonian circuit problem and sum of subset

problem. (May/June
2016) (Nov/Dec 15)

Page 89 of 120
HAMILTONIAN CIRCUIT PROBLEM AND SUM OF SUBSET PROBLEM

A Hamiltonian circuit or Hamiltonian cycle is defined as a cycle that
passes through all the vertices of the graph exactly once. It is named after
the Irish mathematician Sir William Rowan Hamilton (1805-1865), who
became interested in such cycles as an application of his algebraic
discoveries. A Hamiltonian circuit can be also defined as a sequence of n
+ 1 adjacent vertices vi0,vi1…….vin,vi0 where the first vertex of the
sequence is the same as the last one while all the other n - 1 vertices are
distinct
Algorithm:(Finding all Hamiltonian cycle)
void Nextvalue(int k)
{
do
{
x[k]=(x[k]+1)%(n+1);
if(!x[k]) return; if(G[x[k-
1]][x[k]])
{
for(int j=1;j<=k-1;j++)
if(x[j]==x[k])
break;
}
}while(1);
}
if(j==k)
if(k<n)
return;void Hamiltonian(int k)
{
do
{
NextValue(k);
if(!x[k]) return;
if(k==n)
{
for(int i=1;i<=n;i++)
{
Print x[i];
}
}
else Hamiltonian(k+1);
}while(1);
}

Page 90 of 120
Example:
State Space
Tree:
Subset sum problem:

Problem Statement: To find a subset of a given set S= {s1, ... ,
sn} of n positive integers whose sum is equal to a given positive
integer d. For example, for S = {1, 2,
5, 6, 8} and d = 9, there are two solutions: {1, 2, 6} and {1, 8}.
Of course, some instances of this problem may have no solutions. It is
convenient to sort the set's elements in increasing order.
Algorithm sumofsubset(s,k,r)
{S1≤S2………≤Sn

Page 91 of 120
//generate the left child. note s+w(k)<=M since

Bk-1 is true. X{k]=1;
if (S+W[k]=m) then write(X[1:k]); // there is no recursive call
here as
W[j]>0,1<=j<=n.
else if (S+W[k]+W[k+1]<=m) then sum of sub (S+W[k], k+1,r- W[k]);
//generate right child and evaluate Bk.
if ((S+ r- W[k]>=m)and(S+ W[k+1]<=m)) then
{
X{k]=0;
sum of sub (S, k+1, r- W[k]);
}
}
Construction of state space tree for subset sum:
 The state-space tree can be constructed
as a binary tree.
 The root of the tree represents the starting point, with no
decisions about the given elements made as yet.
 Its left and right children represent, respectively, inclusion and
exclusion of s1 in a set being sought.
 Similarly, going to the left from a node of the first level corresponds
to inclusion of s2, while going to the right corresponds to its
exclusion, and so on. Thus, a path from the root to a node on the ith
level of the tree indicates which of the first I numbers have been
included in the subsets represented by that node.
 Record the value of s', the sum of these numbers, in the node. If s'
is equal to d, then there is a solution for this problem.
 The result can be both reported and stopped or, if all the
solutions need to be found, continue by backtracking to the node's
parent. If s' is not equal to d, then terminate the node as non
promising if either of the following two inequalities holds:
s' + si+1 > d (the sums' is too large)
< (the sum is too small)

Page 92 of 120
3. Explain how the travelling salesman problem is solved using branch and
bound technique.
TRAVELING SALESMAN PROBLEM

Given n cities with known distances between each pair, find the shortest
tour that passes through all the cities exactly once before returning to the starting
city
The branch-and-bound technique can be applied to instances of the
traveling salesman problem if the result comes up with a reasonable lower
bound on tour lengths.
A lower bound on the length l of any tour can be computed as follows.
Calculation of lower bound:
For each city i, 1 ≤ i ≤ n,
 find the sum si; of the distances from city i to the two nearest cities;
 compute the sum s of these n numbers;
 divide the result by 2; and,
 if all the distances are integers, round up the result to the nearest
integer:
lb=
s/2
Moreover, for any subset of tours that must include particular edges of a
given graph, the lower bound can be modified accordingly.

Page 93 of 120
graph.
For example, for the instance above the lower bound is:
lb = [(1+ 3) + (3 + 6) + (1 + 2) + (3 + 4) + (2 + 3)]/2 = 14.
The bounding function can be used, to find the shortest Hamiltonian circuit for
the given
Construction of state space tree:
Root:
First, without loss of generality, consider only tours that start at a.
First level
Second because the graph is undirected, tours can be generated in which b
is visited before c. In addition, after visiting n - 1 = 4 cities, a tour has no choice
but to visit the remaining unvisited city and return to the starting one.
Lower bound if edge (a,b) is chosen: lb =
ceil([(3+1)+(3+6)+(1+2)+(4+3)+(2+3)]/2)=14 Edge (a,c) is not include since b is
visited before c. Lower bound if edge (a,d) is chosen: lb =
ceil([5+1)+(3+6)+(1+2)+(5+3)+(2+3)]/2)=16. Lower bound if edge (a,e) is chosen: lb
= ceil([(8+1)+(3+6)+(1+2)+(4+3)+(2+8)]/2)=19 Since the lower bound of edge
(a,b) is smaller among all the edges, it is included in the solution. The state
space tree is expanded from this node.
Second level
The choice of edges should be made between three vertices: c, d and e.
Lower bound if edge (b,c) is chosen. The path taken will be (a ->b->c):
lb = ceil([(3+1)+(3+6)+(1+6)+(4+3)+(2+3)]/2)=16. Lower bound if edge (b,d) is
chosen. The path taken will be (a ->b->d):
lb = ceil([(3+1)+(3+7)+(7+3)+(1+2)+(2+3)]/2)=16

Page 94 of 120
Lower bound if edge (b,e) is chosen. The path taken will be (a ->b->e):
lb = ceil([(3+1)+(3+9)+(2+9)+(1+2)+(4+3)]/2)=19. (Since this lb is larger than other
values, so further expansion is stopped)
The path a->b->c and a->b->d are more promising. Hence the state space tree is
expanded from those nodes.
Next level
There are four possible routes:
a ->b->c->d->e->a a
->b->c->e->d->a a-
>b->d->c->e->a a-
>b->d->e->c->a
Lower bound for the route a ->b->c->d->e->a: (a,b,c,d)(e,a) lb =

ceil([(3+8)+(3+6)+(6+4)+(4+3)+(3+8)])
Lower bound for the route a ->b->c->e->d->a: (a,b,c,e)(d,a) lb =

ceil([(3+5)+(3+6)+(6+2)+(2+3)+(3+5)]/2)=19
Lower bound for the route a->b->d->c->e->a: (a,b,d,c)(e,a)

lb =
ceil([(3+8)+(3+7)+(7+4)+(4+2)+(2+8)]/2)
=24
Lower bound for the route a->b->d->e->c->a: (a,b,d,e)(c,a)

lb =
ceil([(3+1)+(3+7)+(7+3)+(3+2)+(2+1)]/2)
=16
Therefore from the above lower bound the solution is
The optimal tour is a ->b->c->e->d->a
The better tour is a ->b->c->e->d->a
The inferior tour is a->b->d->c->e->a
The first tour is a ->b->c->d->e->a

Page 95 of 120
State Space Tree for the Traveling Salesman Problem
4. Explain in detail about solving knapsack problem using branch and

bound technique. (Nov/Dec 2016)
KNAPSACK
PROBLEM
Given n items of known weights wi and values vi, i = 1, 2, ..., n, and a knapsack
of capacity W, find the most valuable subset of the items that fit in the knapsack. It
is convenient to order the items of a given instance in descending order by their
value-to-weight ratios. Then the first item gives the best payoff per weight unit
and the last one gives the worst payoff per weight unit, with ties resolved
arbitr
arily:
v1/w1≥ v2/w2≥…….
≥vn/wn
The state-space tree for this problem is constructed as a binary tree as

mentioned below:
 Each node on the ith level of this tree, 0≤i≤n, represents all the
subsets of n items that include a particular selection made from the first
i ordered items.
 This particular selection is uniquely determined by the path from the root
to the node:
 A branch going to the left indicates the inclusion of the next item,
 While a branch going to the right indicates its exclusion.
 Record the total weight w and the total value v of this selection in the
node, along with some upper bound ub on the value of any subset
that can be obtained by adding zero or more items to this selection.

Page 96 of 120
Lower bound calculation:

A simple way to compute the upper bound ub is to add to v, the total value of
the items already selected, the product of the remaining capacity of the knapsack
W - w and the best per unit payoff among the remaining items, which is vi+1/ w
i+1:
ub = v + (W-w)( vi+1/ w i+1)
Example:
W = 10
State space tree construction:

Node 0 - At the root of the state-space tree, no items have been selected as
yet. Hence, both the total weight of the items already selected w and their
total value v are equal to 0. The value of the upper bound computed by
formula is $100.
o w=0, v=0
o ub = 0 + (10-0) * (
10) =
10
0
Node 1: the left child of the root represents the subsets that include item 1.
The total weight and value of the items already included are 4 and $40,
respectively; the value of the upper
bound is
ub = 40 + (10- 4)
*6=
$76
.
Node 2 (right of node 1) represents the subsets that do not include item 1.
ub =
0 + (10-0)*6 =
60
Since node 1 has a larger upper bound than the upper bound
of node 2, it is more promising for this maximization problem,
and branched from node 1 first.

Page 97 of 120
Node 3 (left of node 1) with item 1 and with item 2

w=4+7=11, v=40;
vi+1/
w
i+1=5
Here w= 4+7=11>10. This is not a feasible solution since the
constraints are not satisfied.
Node 4 (right of node 1) with item 1 and without item 2 - w=4; v=40; vi+1/ w
i+1 =5
ub =
40+(10-
4)*5=7
0
Node 5 (left of node 4) with item 1 and item 3 – w=4+5=9; v=40 + 25 = 65;
vi+1/ w
o
i+1=4
ub = 65 +
(10-
9)*4=6
9
Node 6 (right of node 4) with item 1 and without item 3 – w=4;v=40; vi+1/
w i+1=4 ub =
40 + (10-4)*4=64
The right node yields inferior upper bound. So the left node is
selected for further expansion.
Node 7 (left of node 5) with item 1, 3 and with item 4 – w=3; v=12
Here w= 9+3=12>10. This is not a feasible solution since the
constraints are not satisfied.
Node 8 (right of node 5) with item 1, 3 and without item
4 w=9; v=65; vi+1/ w i+1=0
ub = 65 + (10- 9)*0=65

Page 98 of 120
Hence the items in the knapsack are {item 1, item 3} with the profit $65.
4. Explain in detail about job assignment problem.
JOB ASSIGNMENT PROBLEM

The job assignment problem is the problem of assigning n people to n jobs so
that the total cost of the assignment is as small as possible. An instance of the
assignment problem is specified by an n-by-n cost matrix C so that state the
problem can be stated as follows:
Select one element in each row of the matrix so that no two selected elements are
in the same column and their sum is the smallest possible. This is done by
considering the same small instance of the problem:
To find a lower bound on the cost of an optimal selection without actually

solving the problem, several methods can be used. For example, it is clear
that the cost of any solution, including an optimal one, cannot be smaller
than the sum of the smallest elements in each of the matrix‗s rows. For the
instance given, the lower bound is
lb= 2 +3 + 1 + 4 = 10.

Page 99 of 120
It is important to stress that this is not the cost of any legitimate

selection (3 and 1 came from the same column of the matrix); it is just a
lower bound on the cost of any legitimate selection.
Apply the same thinking to partially constructed solutions. For
example, for any legitimate selection that selects 9 from the first row, the
lower bound will be
lb = 9 + 3 + 1 + 4 = 17.
This problem deals with the order in which the tree‗s nodes will he
generated. Rather than generating a single child of the last promising node
as in backtracking, all the children of the most promising node among non-
terminated leaves in the current tree are generated.
To find which of the nodes is most promising, compare the lower bounds
of the live node. It is sensible to consider a node with the best
bound as most promising, although this does not, of course, preclude the
possibility that an optimal solution will ultimately belong to a different branch
of the state-space tree.
This variation of the strategy is called the best-first branch-and-bound.
Returning to the instance of the assignment problem given earlier, start

with the root that corresponds to no elements selected from the cost
matrix. As the lower bound value for the root, denoted lb is 10.
The nodes on the first level of the free correspond to four elements (jobs)
in the first row of the matrix since they are each a potential selection for the
first component of the solution. So there are four live leaves (nodes 1
through 4) that may contain an optimal solution. The most promising of them
is node 2 because it has the smallest lower bound value.
By following the best-first search strategy, branch out from that node first
by considering the three different ways of selecting an element from the
second row and not in the second column—the three different jobs that
can be assigned to person b.
Of the six live leaves (nodes 1, 3, 4, 5, 6, and 7) that may contain an
optimal solution, we again choose the one with the smallest lower bound,

Page 100 of 120
node 5.
First, consider selecting the third column‗s element from c‗s row (i.e.,
assigning person c to job 3); this leaves with no choice but to select
the element from the fourth column of d‗s row (assigning person d to job 4).
This yield leafs that corresponds to the feasible solution (a →2, b→1, c→3,
d →4) with (The total cost of 13. Its sibling, node 9, corresponds to
the feasible
Solution:
solution {a → 2, b →1, c → 4, d → 3) with the total cost of 25, Since its cost is
larger than the cost of the solution represented by leafs, node 9 is simply
terminated.
o Note that if its cost were smaller than 13 then it would have to be replaced
with the information about the best solution seen so far with the data provided by
this node.
o Now, as inspect each of the live leaves of the last state-space tree (nodes 1, 3,
4, 6, and 7 in the following figure), it is discovered that their lower bound
values are not smaller than 13 the value of the best selection seen so far (leaf
8).
o Hence all of them are terminated and the solution represented by leaf 8 is
recognized as the optimal solution to the problem.

Page 101 of 120
6. Explain in detail about approximation algorithm for

traveling salesman problem.
APPROXIMATION OF TRAVELING SALESMAN

PROBLEM Nearest- neighbour algorithm
The following simple greedy algorithm is based on the nearest-neighbour heuristic:
the idea of always going to the nearest unvisited city next.
Step 1: Choose an arbitrary city as the start.

Step 2: Repeat the following operation until all the cities have been
visited: go to the unvisited city nearest the one visited last (ties can be
broken arbitrarily).
Step 3: Return to the starting city.

Page 102 of 120
sa : A – B – C – D – A of
length 10
*
s : A – B – D – C – A of
length 8
Multifragment-heuristic algorithm
Step 1 Sort the edges in increasing order of their weights. (Ties can be broken
arbitrarily.) Initialize the set of tour edges to be constructed to the empty set.
Step 2 Repeat this step until a tour of length n is obtained, where n is the number of
cities in the
instance being solved: add the next edge on the sorted edge list to the set of tour
edges, provided this addition does not create a vertex of degree 3 or a cycle of
length less than n; otherwise, skip the edge.
Step 3 Return the set of tour edges.
This algorithm yields the set of edges for the graph shown above:
{(a, b), (c, d), (b, c), (a, d)}.
Minimum-spanning-tree-based algorithms
There are approximation algorithms for the traveling salesman problem that exploit
a connection between Hamiltonian circuits and spanning trees of the same graph.
Since removing an edge from a Hamiltonian circuit yields a spanning tree, we
can expect that the structure of a minimum spanning tree provides a good basis
for constructing a shortest tour approximation. Here is an algorithm that
implements this idea in a rather straightforward fashion.
Twice-around-the-tree algorithm:
Step 1 Construct a minimum spanning tree of the graph corresponding to a

given instance of the traveling salesman problem.
Step 2 Starting at an arbitrary vertex, perform a walk around the minimum
spanning tree recording all the vertices passed by. (This can be done by a DFS
traversal.)
Step 3 Scan the vertex list obtained in Step 2 and eliminate from it all repeated
occurrences of the same

Page 103 of 120
vertex except the starting one at the end of the list. (This step is equivalent to
making shortcuts in the walk.) The vertices remaining on the list will form a
Hamiltonian circuit, which is the output of the algorithm.
Christofides algorithm:
It also uses a minimum spanning tree but does this in a more sophisticated
way than the twice- around-the-tree algorithm.
Stage 1: Construct a minimum spanning tree of the graph
Stage 2: Add edges of a minimum-weight matching of all the odd vertices in the
minimum spanning tree.
Stage 3: Find an Eulerian circuit of the multigraph obtained in stage 2
Stage 3: Create a tour form the path constructed in Sateg 2 by making
shortcuts to avoid visiting intermediate vertices more than once.

Page 104 of 120
Local Search Heuristics for TSP:

Start with some initial tour (e.g., nearest neighbor).
On each iteration, explore the current tour‗s neighborhood by
exchanging a few edges in it.
If the new tour is shorter, make it the current tour; otherwise
consider another edge change.
If no change yields a shorter tour, the current tour is returned as the output.
Example of a 2-
change
7. Explain in detail about the approximation algorithm for knapsack

problem.(Nov/Dec 15) APPROXIMATION ALGORITHM FOR
KNAPSACK PROBLEM Knapsack
Problem:
Given n items of known weights wi and values vi, i = 1, 2, ..., n,
and a knapsack of capacity W, find the most valuable subset of the
items that fit in the knapsack.
Greedy algorithms for the knapsack problem:
Step 1: Order the items in decreasing order of relative
values:
v1/w1 >= vn/wn.

Page 105 of 120
Step 2: Sort the items in non increasing order of the ratios computed in Step
1.
Step 3 Repeat the following operation until no item is left in the sorted list:
if the current item on the list fits into the knapsack, place it in the knapsack;
otherwise, proceed to the next item.
Item Weight Value

1 7 $42
2 3 $12
3 4 $40
4 5 $25
Computing the value-to-weight ratios and sorting the items in non increasing
order of these efficiency ratios yields
Value
Item Weight Value
/
1 4 $40 Weig10
2 7 $42 ht 6
3 5 $25 5
4 3 $12 4
The greedy algorithm will select the first item of weight 4, skip the next
item of weight 7, select the next item of weight 5, and skip the last item of
weight 3. The solution obtained happens to be optimal for this instance
Greedy algorithm for the continuous knapsack
problem:
Step 1 Compute the value-to-weight ratios vi!wi, i = 1,..........,n for the items
given.
Step 2 Sort the items in non increasing order of the ratios computed in
Step 1.
Step 3 Repeat the following operation until the knapsack is filled to its full
capacity or no item is left in the sorted list: if the current item on the list fits into
the knapsack in its entirety, take it and proceed to the next item; otherwise,
take its largest fraction to fill the knapsack to its full capacity and stop.
Item Weight Value Value

/
1 4 $40 10
Weig
2 7 $42 ht 6
3 5 $25 5
4 3 $12 4
The algorithm will take the first item of weight 4 and then 6/7 of the
next item on the sorted list to fill the knapsack to its full capacity.
Approximation schemes:
For this problem, unlike the traveling salesman problem, there exist
polynomial-time approximation schemes, which are parametric families of
algorithms that allow us to get(k) approximations

Page 106 of 120
Approximation algorithm by S.
This algorithm generates all subsets of k items or less, and for each one that
fits into the knapsack, it adds the remaining items as the greedy algorithm
would (i.e., in non increasing order of their value-to-weight ratios). The subset
of the highest value obtained in this fashion is returned as the algorithm's
output.
Example: A small example of an approximation scheme with k = 2
and instances given below:
Ite Weight Value Value / Weight
m
1 4 $40 10
2 7 $42 6
3 5 $25 5
4 1 $4 4
Subset Added items Valu

ϕ 1,3, e
$69
{1} 4
3,4 $69
{2} 4 $46
{3} 1,4 $69
{1,2 Not feasible
{1,3
} 4 $69
}
{1,4 3 $69
}
{2,3 Not feasible
}
{2,4 $46
}
{3,4 1 $69
}
Solution: The algorithm yields (1, 3, 4}, which is the optimal solution for this
instance.
PART-C
1.Explain in detail about P,NP,NP complete and NP hard
problems. (Nov/Dec 2015) P, NP, NP COMPLETE AND NP HARD
PROBLEMS

Page 107 of 120
P:
 P is the set of all decision problems which can be solved in polynomial

time.
 P problems are questions that have a yes/no answer and can be easily
solved by a computer.
 For example,checkingwhether a number is prime is a relatively easy
problem to solve.
NP:
 There are a lot of programs that don't run in polynomial timeon a
regular computer, but do run in polynomial time on a
nondeterministic Turing machine.
 These programs solve problems in NP, which stands for
nondeterministic polynomial time.
 NP problems are questions that have yes/no answers that are easy to
verify, but are hard to solve. That means it would take years or
centuries for your computer to come up with an answer.
 For example, Given the cities and distances, is there a route that
covers all the cities, returning to the starting point, in less than x
distance?
 Two Stages in NP class problems.
 Guessing stage: We can easily guess.
 Verifying stage: It is very hard to verify. i.e) High time complexity.
NP COMPLETE:
 NP complete problems are special kinds of NP problems. We can take

any kind of NP problem and twist and bend it until it looks like an NP
complete problem.
 A problem is NP complete if the problem is both NP hard, and in NP.
 For example, the knapsack problem is NP. It can ask what's the best
way to stuff knapsack if you had lots of different sized pieces of
different precious metals lying on the ground , and that you can't carry
all of them in the bag.
NP HARD:Figure:Notion of an NP-complete problem. Polynomial-time reductions
of NP problems to an NP-complete problem are shown by arrows.
 NP Hard problems are worst than NP problems.

 Even if someone suggested you solution to a NP Hard problem, it'd still
take forever to verify if they were right.
 For example, in travelling salesman, trying to figure out the absolute
shortest path through 500 cities in your state would take forever to
solve. Even if someone walked up to you and gave you an itinerary
and claimed it was the absolute shortest path, it'd still take you
forever to figure out whether he was a liar or not.

Page 108 of 120
Figure: A relationship between P, NP, NP Complete and NP Hard problems
2. Give any five undecidable problems and explain the famous

halting problem. (May/June 2016)
 Halting Problem.
 Post correspondence problem.
 Hilbert‗s tenth problem: the problem of deciding whether a
Diophantine equation (multivariable polynomial equation) has a
solution in integers.
 Determining if a context-free grammar generates all possible strings, or
if it is ambiguous.
 The word problem in algebra and computer science.
 The word problem for certain formal languages.
 Determining whether a λ-calculus formula has a normal form.
In computability theory and computational complexity theory, an undecidable

problem is a decision problem for which it is known to be impossible to construct
a single algorithm that always leads to a correct yes-or-no answer.
Some decision problems cannot be solved at all by any algorithm. Such

problems are called undecidable, as opposed to decidable problems that can
be solved by an algorithm. A famous example of an undecidable problem was
given by Alan Turing in 1936.1 The problem in question is called the halting
problem: given a computer program and an input to it, determine whether the
program will halt on that input or continue working indefinitely on it.
Here is a surprisingly short proof of this remarkable fact. By way of contradiction,
assume that A is an algorithm that solves the halting problem. That is, for any
program P and input I,

Page 109 of 120
This is a contradiction because neither of the two outcomes for

program Q is possible, which completes te proof.

Page 110 of 120
Industrial/Practical Connectivity of the subject
 Graph theoretic methods are widely used in linguistics

 Graphs are used in networks of communication, data organization
 Tree traversals are used for searching
 Trees are used to manipulated list of data

Page 111 of 120

Page 112 of 120

Page 113 of 120

Page 114 of 120
Pg no:13
pg no:14
Pg no:27
Pg no:29
Pg no:48
Pg no:47
Pg no:88
Pg no:69
Pg no:88
Pg no:69

Page 115 of 120
Pg no:19
Pg no:25
Pg no:25
Pg no:32
Pg no:43
Pg no:64

Page 116 of 120
Pg no:65
Pg no:82
Pg no:84
Pg no:72
Pg no:109
Pg no:89

Page 117 of 120

Page 118 of 120

Page 119 of 120

Page 120 of 120

CS8451-DAA - by WWW - LearnEngineering.in PDF

Uploaded by

Copyright:

Available Formats

CS8451-DAA - by WWW - LearnEngineering.in PDF

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

CS8451-DAA - by WWW - LearnEngineering.in PDF

Uploaded by

Copyright:

Available Formats

For More Visit : www.Learnengineering.

SUBJECT CODE: CS6402

SUBJECT NAME: DESIGN AND ANALYSIS OF ALGORITHMS

Regulation: 2013 Year and Semester: II Year/IV Sem

SUBJECT CODE: CS8451

SUBJECT NAME: DESIGN AND ANALYSIS OF ALGORITHMS

Verified by DLI, CLI and Approved by the Centralized Monitoring Team

For More Visit : www.Learnengineering.in

CS8451 DESIGN AND ANALYSIS OF ALGORITHMS

OBJECTIVES: The student should be made to:

UNIT II BRUTE FORCE AND DIVIDE-AND-CONQUER 9

UNIT III DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE 9

UNIT IV ITERATIVE IMPROVEMENT 9

UNIT V COPING WITH THE LIMITATIONS OF ALGORITHM POWER 9

For More Visit : www.Learnengineering.in

 Design algorithms for various computing problems.

For More Visit : www.Learnengineering.in

For More Visit : www.Learnengineering.in

26 Minimum spanning tree 59

47 Question Bank 112

For More Visit : www.Learnengineering.in

AIM AND OBJECTIVE OF THE SUBJECT

The student should be made to:

 Learn the algorithm analysis techniques.

Need and Importance for Study of the Subject:

 Design and analysis is the basis for all problems since it

For More Visit : www.Learnengineering.in

DETAILED LESSON PLAN

S. Unit Hrs Cumilative Books

1 I Introduction - Notion of an Algorithm 1 1 T1 , R1

4 I Important Problem Types 1 4 T1

Fundamentals of the Analysis

7 I Mathematical analysis for 1 T1

For More Visit : www.Learnengineering.in

Example : Formula and Algorithm

Divide and conquer

UNIT-III DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE

21 III Floyd‗s algorithm 1 23 T1, R1

22 III Optimal Binary Search Trees 2 25 T1, R1

Knapsack Problem and

26 III Kruskal's Algorithm 1 29 T1, R1

27 III Dijkstra's Algorithm 1 30 T1, R1

28 III Huffman Trees 1 31 T1, R1

For More Visit : www.Learnengineering.in

UNIT IV ITERATIVE IMPROVEMENT

Geometric Interpretation of Linear

31 IV Problem on Simplex Method 1 34 T1, R1

UNIT V COPING WITH THE LIMITATIONS OF ALGORITHM POWER

38 V P, NP and NP-Complete Problems 1 42 T1

39 V Backtracking – n-Queens problem 1 43 T1

40 V Hamiltonian Circuit Problem 1 44 T1

41 V Subset Sum Problem 1 45 T1

42 V Branch and Bound - Assignment 1 46 T1

Approximation Algorithms for NP –

For More Visit : www.Learnengineering.in

3. What is recurrence equation? April / May 2010, Nov/Dec

4. Write an algorithm to find the number of binary digits in the

For More Visit : www.Learnengineering.in

5. List out the properties of asymptotic notations. April / May 2015