PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

CS6402-DESIGN AND ANALYSIS OF ALGORITHMS

UNIT- I
INTRODUCTION
PART – A

SYLLABUS: 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.

COURSE OBJECTIVE: Learn the algorithm analysis techniques.

1. What do you mean by algorithm? (Nov/Dec 2008) (May/June 2013)

An algorithm is a sequence of unambiguous for solving a problem i.e., for obtaining a required
output for any legitimate input in a finite amount of time. In addition, all algorithms must satisfy the
following criteria:
1) Input
2) Output
3) Definiteness
4) Finiteness
5) Effectiveness.

2. What is performance measurement?

Performance measurement is concerned with obtaining the space and the time requirements of a
particular algorithm.

3. Give the diagram representation of Notion of algorithm.

PROBLEM

ALGORITHM

INPUT COMPUTER OUTPUT

4. What are the types of algorithm efficiencies?

The two types of algorithm efficiencies are .Time efficiency: indicates how fast the algorithm runs
.Space efficiency: indicates how much extra memory the algorithm needs.

5. What is space complexity? (Nov/Dec 2012)

II Year / IV Sem 1
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

Space Complexity indicates how much extra memory the algorithm needs. Basicallyit has three
components. They are instruction space, data space and environmentspace.

6. What is time complexity? (Nov/Dec 2012)

Time Complexity indicates how fast an algorithm runs.T(P)=Compile Time+ Run Time .(Tp) ,Where
Tp is no of add, sub, mul...

7. What is an algorithm design technique?

An algorithm design technique is a general approach to solving problemsalgorithmically that is
applicable to a variety of problems from different areasof computing.

8. What is pseudo code?

A pseudo code is a mixture of a natural language and programming languageconstructs to specify an
algorithm. A pseudo code is more precise than anatural language and its usage often yields more
concise algorithmdescriptions.

10. What are the types of algorithm efficiencies?

The two types of algorithm efficiencies are
Time efficiency: indicates how fast the algorithm runs
Space efficiency: indicates how much extra memory the algorithm needs.

11. What are the steps involved in the analysis framework?

The various steps are as follows
 Measuring the input’s size
 Units for measuring running time
 Orders of growth
 Worst case, best case and average case efficiencies

12. The worst-case efficiency?

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 algorithmruns the longest among
all possible inputs of that size.

13. What is best-case efficiency?

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 thefastest among all possible inputs of that size.

14. What is average case efficiency?(May 2008)

The average case efficiency of an algorithm is its efficiency for an averagecase input of size n. It
provides information about an algorithm behavior on a“typical” or “random” input.

15. Define asymptotic notations.

II Year / IV Sem 2
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

To choose best algorithm, we need to check efficiency of each algorithm the efficiency can be
measured by computing time complexity of each algorithm. Asymptotic notation is shorthand way to
represent the time complexity
The various notations are Big “Oh”, Big Omega, and Theta.

16. Define the asymptotic notation “Big oh” (0) (May 2008)(April/May 2012&2013)
Let, f(n) and g(n) be two non-negative functions. Let, n0 and constant c are two integers such that no
denotes some value of in put similarly c is constant such that c > 0. We can write

F(n) <= c*g(n) For all n ≥ n0

A function t(n) is said to be in O(g(n)) denoted t(n) ε O (g(n)), if t(n) is bounded above by
someconstant multiple of g(n) for all large n, i.e., if there exist some positive constant c and some
non-negative integer n0 such that
T (n) < c g (n) for n > n0

17. Define the asymptotic notation “Omega” ( Ω).

A function f(n) is said to be in Ω (g(n)) if f(n) is bounded below by some
positive constant multiple of g(n) such that
f(n) ≥ c * g(n) For all n ≥ n0

18. Define the asymptotic notation “theta” (θ)

Let, f(n) and g(n) be two non negative functions. There are two positive constants namely c1 and c2
such that c1 ≤ g(n) ≤ c2 g(n)
Then we can say that, f(n) ε Θ (g(n))
II Year / IV Sem 3
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

19. What is recursive algorithm?

An algorithm is said to be recursive if the same algorithm is invoked in the body.
An algorithm that calls itself is direct recursive. Algorithm A is said to be indeed recursive if it calls
another algorithm

20. Define recurrence. (May2010)

A recurrence is an equation or inequality that describes a function in terms of its value on smaller
inputs. The complexity of many interesting algorithms is easily expressed as a recurrence, especially
divide and conquer algorithms. The complexity of recursive algorithms is readily expressed as a
recurrence.
Example :(i)Linear search of a list

1 for n  1
T (n)  
T(n - 1) + 1 otherwise
(ii) Binary search
1 for n  1
T (n)  
T(n/2) + 1 otherwise

21. Define Linear Search. (Nov/Dec 2011) (April/May 2010&2012)

In computer science, linear search or sequential search is a method for finding aparticular value in a
list, which consists in checking every one of its elements, one at atime and in sequence, until the
desired one is found.

22. What are the Best, Worst and Average Case complexity of Linear Search?
 Best Case – O(1)
 Average Case – O(N)
 Worst Case – O(N)
II Year / IV Sem 4
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

23. Difference between Best Case and Worst Case Complexities.

The best case complexity of an algorithm is its efficiency for the best case input ofsize N, which is an
input of size N for which the algorithm runs fastest among allpossible inputs of that size.
The worst case complexity of an algorithm is its efficiency for the worst case inputof size N, which is
an input of size N for which the algorithm runs longest among allpossible inputs of that size.

24. Give the general plan for analyzing non recursive algorithm.
 Decide a parameter indicating an Input’s Size.
 Identify the algorithms Basic Operation
 Check whether the number of times the basic operation is executed only on thesize of an
input. If it also depends on some additional property, the worst case,average case, and if
necessary, best case efficiencies have to be investigatedseparately.
 Using standard formulas and rules of sum manipulation either find a closedformula for the
count or, at the very least, establish its order of growth.

25. What is validation of algorithm? (Nov/Dec 2012)

The process of measuring the effectiveness of an algorithm before it is coded to know the algorithm
is correct for every possible input.This process is called validation.

26. What are all the methods available for solving recurrence relations?
 Forward Substitution
 Backward Substitution
 Smoothness Rule
 Master Theorem

27. Write down the problem types.(April/May 2008)

 Sorting
 Searching
 String Processing
 Graph Problem
 Combinational Problem
 Geometric Problem
 Numerical Problem

28. What are the types of recurrence relations?

 Homogeneous recurrence relation.
 Non homogeneous recurrence relation.
29. Define Substitution Method. (April /May 2010)
Substitution method is a method of solving a system of equations wherein one of theequations is
solved for one variable in terms of the other variables.

II Year / IV Sem 5
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

30. Give the general plan for analyzing recursive algorithm.

 Decide a parameter indicating an Input’s Size.
 Identify the algorithms Basic Operation
 Check whether the number of times the basic operation is executed only on thesize of an
input. If it also depends on some additional property, the worst case,average case, and if
necessary, best case efficiencies have to be investigatedseparately.
 Set up a recurrence relation, with an appropriate initial condition, for thenumber of times
basic operation is executed.

31. Define Recurrence Relation. (APRIL/MAY 2010)

The equation defines M (N) not explicitly, ie.., is a function of n, but implicitly as afunction of its
value at another point, namely N-1. Such equations are calledrecurrence relation.

32. Give the General Plan for the Empirical Analysis of Algorithm Time Efficiency?
1. Understand the experiment’s purpose.
2. Decide on the efficiency metric M to be measured and the measurement unit
(an operation count vs. a time unit).
3. Decide on characteristics of the input sample (its range, size, and so on).
4. Prepare a program implementing the algorithm (or algorithms) for the experimentation.
5. Generate a sample of inputs.
6. Run the algorithm (or algorithms) on the sample’s inputs and record the data
observed.
7. Analyze the data obtained.

33. Write an algorithm to check whether the given string is Palindrome or not. (NOV/DEC
2008)
1. Get the number from user.
2. Reverse it.
3. Compare it with the number entered by the user.
4. If both are same then print palindrome number
5. Else print not a palindrome number.

34. Write an algorithm to find the number of binary digits in the binary representation of a
positive decimal integer. (MAY 2015)
ALGORITHM 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
count<- count+1
n<- [n/2]
return count

II Year / IV Sem 6
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

35. Write down the properties of asymptotic notations? (MAY 2015)

If t1(n)Ɛ O(g1(n)) and t2(n)Ɛ O(g2(n)), then
t1(n)+t2(n)Ɛ O(max{g1(n),g2(n)})

36. Give the Euclid’s algorithm for computing gcd(m, n) (MAY-JUN 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.

37. Compare the order of growth n(n-1)/2 and n2. (MAY-JUN 2016)
2
n n(n-1)/2 n
Polynomial Quadratic Quadratic
1 0 1
2 1 4
4 6 16
8 28 64
2
10 45 10
2 4
10 4950 10
Complexity Low High
Growth Low high
2
n(n-1)/2 is lesser than the half of n

PART B
1. Define the asymptotic notations used for best case average case and worst case analysis?
(APRIL/MAY2009) (APRIL/MAY 2008) (U)
2. How do you evaluate the performance of the algorithms? (E)
3. Explain the general framework for analyzing the efficiency of algorithm. (R)
4. Explain properties of BIG (oh) Notation.(8) (MAY 2016) (U)
5. What is meant by recurrence? Give one example to solve recurrence equations.
(APRIL/MAY012) (U)
6.(i) Distinguish between Big Oh, Theta and Omega natation. (NOV/DEC 2012) (R)
(ii) Analyze the best, worst and average case analysis for linear search. (An)
7.Find complexity of algorithm C (n) of the algorithm for the best, worst, average case,(evaluate
average case complexity of n=3 n mean number of inputs.(Ap)
8. (i) Define Asymptotic notations. Distinguish between Asymptotic notation and conditional
II Year / IV Sem 7
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

asymptotic notation. (10)(APRIL/MAY 2010)(APRIL/MAY 2011) (U)

ii) Explain how the removing condition is done from the conditional Asymptotic notation
with an example. (6)(NOV/DEC 2011) (An)
9. (i) Explain how analysis of linear search is done with a suitable illustration. (10) (Ap)
(ii)Define recurrence equation and explain how solving recurrence equations are
done.(6)(NOV/DEC 2011) (An)
10. Explain how Time Complexity is calculated. Give an example. (APRIL/MAY 2010)(An)
11.Discuss all the Asymptotic notations in detail.(APRIL/MAY 2012) (U)
12. Write an algorithm for finding maximum element of an array, perform best, worst and
average case complexity with appropriate order notations. (APRIL/MAY 2008) (U)
13. Write an algorithm to find mean and variance of an array perform best, worst and average
case complexity, defining the notations used for each type of analysis.(APRIL/MAY 2008)(U)
14. (i)Briefly explain the time complexity, space complexity estimation.(6)(MAY/JUNE 2013)(R)
(ii) Write the linear search algorithm and analyze its time complexity. (10) (An)

15. (i) Find the time complexity and space complexity of the following problems. Factorial using
Recursion AND Compute nth Fibonacci Number using Iterative statements.(Ap)
(ii) Solve the following recurrence relations:(NOV/DEC 2012) (Ap)

1).

2) Where a and c are constants.

16. Solve the following inequalities are correct (MAY/JUNE 2013) (Ap)
(i)
(ii) n!=O( )
(iii)
(iv)
17. If you have to solve the searching problem for a list of n numbers, how can you take
advantage of the fact that the list is known to be sorted? Give separate answer for
(i) list represented as arrays
(ii) lists represented as linked lists
Compare the time complexities involved in the analysis of both the algorithms.(MAY 2015) (C)
18. (i) Derive the worst case analysis of merge sort using suitable illustrations.(8) (C )
(ii) Derive a loose bound on the following equation (8) (C )
F(x)=35x8 -22x7 +14x5 – 2x4-4x2+x-15
19. 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.(8) (MAY / JUNE 2016) (Ap)
20. Give the recursive algorithm which finds the number of binary digits in the binary of a
II Year / IV Sem 8
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

positive decimal integer. Find the recurrence relation and complexity. (MAY / JUNE 2016) Ap)

COURSE OUTCOMES:
Basic ability to analyze algorithms and to determine algorithm correctness and time efficiency
class.

UNIT II
BRUTEFORCE AND DIVIDE-AND-CONQUER
PART A
SYLLABUS: 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.

COURSE OBJECTIVE: Apply important algorithmic design paradigms and methods of analysis.
1. Give the general plan for divide-and-conquer algorithms. (APRIL/MAY 2008)(NOV/DEC
2008)(MAY/JUNE 2016)
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 ofthe original problem

2. Give the recurrence relation of divide-and-conquer?

The recurrence relation is
 g ( n)
T(n) =  g(n)
t (n1)  t (n 2)  .....  t (nk )  f (n)
3. What is 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].
A[0]………A[m-1] A[m] A[m+1]………A[n-1]

4. Give computing time for Binary search? (APRIL/MAY 2012)

In conclusion we are now able completely describe the computing time of binary search by giving
formulas that describe the best, average and worst cases.
Successful searches
Best-(1) average-(logn) worst -(Logn)
unsuccessful searches best, average, worst- (logn)

5. Write the algorithm for Iterative binary search?

II Year / IV Sem 9
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

Algorithm BinSearch(a,n,x)
//Given an array a[1:n] of elements in nondecreasing
// order, n>0, determine whether x is present
{
low : = 1;
high : = n;
while (low < high) do
{
mid : = [(low+high)/2];
if(x a[mid]) then high:= mid-1;
else if (x a[mid]) then low:=mid + 1;
else return mid;
}
return 0;}

6. Define merge sort.

Mergesort 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 twosmaller sorted arrays into a
single sorted one.
7. Describe the recurrence relation of merge sort?
If the time for the merging operation is proportional to n, then the computing time
of merge sort is described by the recurrence relation
T(n)= a
2T(n/2)+n n = 1, a constant

8. Define Selection Sort?

We start selection sort by scanning the entire given list to find its smallest element and exchange it
with the first element, putting the smallest element in its final position in the sorted list. Then we
scan the list, starting with the second element,to find the smallest among the last n − 1 elements and
exchange it with the second element, putting the second smallest element in its final position.

9. Define Bubble Sort?

Another brute-force application to the sorting problem is to compare adjacentelements of the list and
exchange them if they are out of order. By doing itrepeatedly, we end up “bubbling up” the largest
element to the last position onthe list. The next pass bubbles up the second largest element, and so
on, untilafter n − 1 passes the list is sorted.

10. Define Closest-Pair Problem? (MAY/JUNE 2016)

The closest-pair problem calls for finding the two closest points in a set of n points. It is the simplest
of a variety of problems in computational geometry thatdeals with proximity of points in the plane or
higher-dimensional spaces. Pointsin question can represent such physical objects as airplanes or post
offices as wellas database records, statistical samples, DNA sequences, and so on.
II Year / IV Sem 10
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

11. Write the Pseudocode for computes the distance between the two closest points?
//Finds distance between two closest points in the plane by brute force
//Input: A list P of n (n ≥ 2) points p1(x1, y1), . . . ,pn(xn, yn)
//Output: The distance between the closest pair of points
d←∞
fori ←1 to n − 1 do
forj ←i + 1 to ndo
d←min(d, sqrt((xi− xj )2 + (yi− yj )2)) //sqrtis square root
return d

12. Define Convex-Hull Problem?

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. Define Convex Set?

A set of points (finite or infinite) in the plane is called convex if for any two pointsp and q in the set,
the entire line segment with the endpoints at p and q belongs to the set.

14. Define Exhaustive search?

Exhaustive search is simply a brute-force approach to combinatorial problems.It suggests generating
each and every element of the problem domain, selectingthose of them that satisfy all the constraints,
and then finding a desiredelement (e.g., the one that optimizes some objective function). Note that
althoughthe idea of exhaustive search is quite straightforward, its implementation typicallyrequires
an algorithm for generating certain combinatorial objects.

15. Define Traveling Salesman Problem?

The traveling salesman problem (TSP) has been intriguing researchers for the last 150 years by its
seemingly simple formulation, important applications, and interesting connections to other
combinatorial problems. In layman’s terms, the problem asks to find the shortest tour through a given
set of n cities that visits each city exactly once before returning to the city where it started.

16. Design a brute-force algorithm for computing the value of a polynomial p(x)=anxn+an-1xn-1+-
----+a1x----a0 at a given point x0 and determine its worst case efficiency class.(MAY2015)
Number of multiplications needed in the worst case is
T(n) = n + n-1 + n-2 + … + 3 + 2 + 1
= n (n + 1)/2
=n2/2 + n/2
This is an exact formula for the maximum number of multiplications. In general though, analyses
yield upper bounds rather than exact formulae. We say that the number of multiplications is on the
order of n2 , or O(n2).

17. Derive the complexity of Binary search algorithm. (MAY 2015)

II Year / IV Sem 11
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

Cworst(n)=Cworst([n/2])+1 for n1, Cworst(1)=1

Cworst(2k)=k+1=log2n+1

Cworst(n)=[log2n]+1=[log2(n+1)]

Cworst(n)=[log2n]+1=[log22i]+1=[log22+log2i]+1

= (1+[log2i])+1=[log2i]+2

Cavg(n) ͌log n.
2

PART-B
1. Define divide and conquer to apply the technique in binary search algorithm and to analysis it.
(APR/MAY 2006) (Ap)
2. Explain in detail in merge sort give an example (APR/MAY 2008) (MAY 2016). (U)
3.What is divide and conquer strategy and explain the binary search with suitable example
problem.(NOV/DEC 2011)(R)
4. Distinguish between Quick sort and Merge sort, and arrange the following numbers in increasing
order using merge sort. (18, 29, 68, 32, 43, 37, 87, 24, 47, 50) (NOV/DEC 2011) (MAY/JUNE
2013). (U)

5. Trace the steps of Mergesort algorithm for the elements 122,25,70,175,89,90,95,102,123 and also
compute its time complexity.(NOV/DEC 2012) (Ap)

6. Explain brute-force approach. What are the advantages and disadvantages of this approach? (R)
7. Write an algorithm to perform binary search on a sorted list of elements. Analyze the algorithm for
the best case, average case and worst case.(APR/MAY 2011). (An)
8. Using the divide and conquer approach to find the maximum and minimum in a set of ‘n’ elements.
Also find the recurrence relation for the number of elements compared and solve. (APR2011).(C)
9. Explain Closest-pair and Convex-Hull problems by Brute Force? (R)
10. Explain Exhaustive Search? (R)
11. Write an efficient and exhaustive search algorithm for the travelling salesman problem?(U)
12. Trace maximum and minimum (using divide and conquer) algorithm for the following set of
numbers. 20, 35, 18, 8, 14, 41, 3, 39,-20. (Ap)
13. Write a pseudo code using divide and conquer technique for finding the position of the largest
element in an array of N numbers. (An)
14. Sort the following set of elements using merge sort: 12, 24, 8, 71, 4, 23, 6, 89, 56.(Ap)
15. Explain in detail quick sorting method. Provide a complete analysis of quick sort. (R)
(APR/MAY 2008)
16. Explain in detail the merge sort. Illustrate the algorithm with a numeric example. Provide
complete analysis of the same. (APR/MAY 2008) (R)
17. (i) Solve the following using Brute force algorithm: (MAY 2015) (Ap)
Find whether the given string follows the special pattern and return 0 or 1 accordingly.
II Year / IV Sem 12
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

Examples:
1. Pattern: “abba”, input: “redblueredblue’ should return 1.
2. Pattern: “aaaa”, input: “asdasdasdasd” should return 1.
3. attern: “aabb”, input: “xyzabcxzyabc” should return 0.
(ii) Explain the convex hull problem and the solution involved behind it. (U)

18. A pair contains two numbers and its second number is on the right side of the first one in an array.
The difference of a pair is the minus result while subtracting the second number from the first one.
Implement a function which gets the maximal difference of all pairs in an array(using divide and
conquer method). (MAY 2015) (C)

19. Explain the method used for performing Multiplication of two large integers. Explain how
divide and conquer method can be used to solve the same. (MAY\JUNE 2016). (U)

COURSE OUTCOMES: Describe the divide-and-conquer paradigm and explain when an

algorithmic design situation calls for it. Recite algorithms that employ this paradigm. Synthesize
divide-and-conquer algorithms. Derive and solve recurrences describing the performance of divide-
and-conquer algorithms.
UNIT – III
DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE
PART –A
SYLLABUS: 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.

COURSE OBJECTIVE: Apply important algorithmic design paradigms and methods of analysis.

1. Define dynamic programming.

Dynamic programming is an algorithm design method that can be used when asolution to the
problem is viewed as the result of sequence of decisions.
2. What are the features of dynamic programming?
 Optimal solutions to sub problems are retained so as to avoid recomputing their values.
 Decision sequences containing subsequences that are sub optimal are not considered.
 It definitely gives the optimal solution always.

3. What are the drawbacks of dynamic programming?

 Time and space requirements are high, since storage is needed for all level.
 Optimality should be checked at all levels.

4.Write the general procedure of dynamic programming.

The development of dynamic programming algorithm can be broken into a
sequence of 4 steps.
1. Characterize the structure of an optimal solution.
2. Recursively defines the value of the optimal solution.
II Year / IV Sem 13
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

3. Compute the value of an optimal solution in the bottom-up fashion.

4. Construct an optimal solution from the computed information.

5. Write the difference between the Greedy method and Dynamic programming.(APRIL/MAY
2011)(NOV/DEC 2012)

1.Only one sequence of decision is 1.Many number of decisions are

generated. generated.
2.It does not guarantee to give an 2.It definitely gives an optimal
optimal solution always. solution always. 6.
Give
the Floyd’s algorithm
ALGORITHM Floyd(W[1..n,1..n])
//Implements Floyd’s algorithm for the all-pair shortest–path 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]

7.Give the time complexity and space complexity of traveling salesperson problem.
Time complexity is O (n2 2n).
Space complexity is O (n 2n).

8. Write some applications of traveling salesperson problem.

Routing a postal van to pick up mail from boxes located at n different sites. Using a robot arm to
tighten the nuts on some piece of machinery on an assembly line. Production environment in which
several commodities are manufactured on the sameset of machines.

9. Write about traveling salesperson problem. (NOV/DEC 2011)

Let g = (V, E) be a directed. The tour of G is a directed simple cycle that includes every vertex in
V. The cost of a tour is the sum of the cost of the edges on the tour. The traveling salesperson
problem to find a tour of minimum cost.

10. Define multistage graph. (NOV/DEC 2011)(NOV/DEC 2012)

A multistage graph G=(V,E) is a directed graph in which the vertices are partitioned into k≥2 disjoint
sets Vi,1≤i≤k.
 If <u,v> is an edge in E, then u€ V i andv € Vi+1 forsome i, 1≤i≤k.
 Let s and t, respectively be the vertices in v1 and vk. The vertex s is the source, and t the sink.
 Let c(i,j) be the cost of edge <i,j>.
II Year / IV Sem 14
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

 The cost of a path from s to t is the sum of the costs of the edges on the path.
 The multistage graph problem is to find a minimum-cost path from s to t.

12. Define optimal finish time.

Optimal finish time scheduling for a given set of tasks is a nonpreemptive schedule S forwhich F (S)
is minimum over all nonpreemptive schedules S.

13. Define preemptive optimal finish time.

 Preemptive optimal finish time scheduling for a given set of tasks is a preemptive scheduleS
for which F (S) is minimum over all preemptive schedules S.
 The finish time fi (S) of job i is the time at which all tasks of job i have been completed
inscheduleS.The finish time F(S) of schedule S is given by
o F(S)=max{ fi (S)} 1<i<n

14. Define the principle of optimality. (APR/MAY 2012)

It states that in an optimal sequence of decisions, each sub sequence must be optimal. Touse dynamic
programming the problem must observe the principle of optimality thatwhatever the initial state is,
remaining decisions must be optimal with regard the statefollowing from the first decision.

15. Define 0/1 knapsack problem. (NOV/DEC 2008) (NOV/DEC 2012)

The solution to the knapsack problem can be viewed as a result of sequence of decisions. We have to
decide the value of xi. xi is restricted to have the value 0 or 1 and by using the function knap(l, j, y)
we can represent the problem as maximum Σpi xi subject to Σwi xi < y where l -iteration, j - number
of objects, y – capacity.

16.What is the formula to calculate optimal solution in 0/1 knapsack problem?

The formula to calculate optimal solution isg0(m)=max{g1, g1(m-w1)+p1}.

17. What is the difference between dynamic programming and greed algorithm?(APRIL/MAY
2012)
S.No. GREEDY ALGORITHM DYNAMIC PROGRAMMING
1. 1. GA computes the solution in bottom up DA computes its solution by making
technique. It computes the solution from itschoices in a serial fashion (never
smaller sub-routines and tries many look backirrevocable).
possibilities and choices before it arrives at
the optimal set of choices.
2. It does not use the principle of optimality, i.e. It uses the principle of optimality.
there is no test by which one
can tell GA will lead to an optimal solution.

18. Define Optimal Binary Search Trees?

II Year / IV Sem 15
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

A binary search tree is one of the most important data structures in computer science. One of its
principal applications is to implement a dictionary, a set of elements with the operations of searching,
insertion, and deletion. If probabilities of searching for elements of a set are known—e.g., from
accumulated data about past searches—it is natural to pose a question about an optimal binary search
tree for which the average number of comparisons in a search is the smallest possible.

19. Define Memory Functions?

The memory function technique seeks to combine the strengths of the topdownand bottom-up
approaches to solving problems with overlappingsubproblems. It does this by solving, in the top-
down fashion but onlyonce, just the necessary subproblems of a given problem and recording
theirsolutions in a table.

20. Define Prims Algorithm.

Prim’s algorithm constructs a minimum spanning tree through a sequenceof expanding subtrees. The
initial subtree in such a sequence consists of a singlevertex selected arbitrarily from the set V of the
graph’s vertices. On each iteration,the algorithm expands the current tree in the greedy manner by
simply attaching toit the nearest vertex not in that tree.

21. Write down the optimization technique used for Warshalls algorithm. State the rules and
assumptions which are implied behind that. (MAY 2015)

Warshalls algorithm constructs the transitive closure of given digraph with n vertices through a series
of n-by-n Boolean matrices. The computations in warshalls algorithm are given by following
sequences,
R(0),…,R(k-1),…,R(k),…,R(n)
Rules:
1.Start with computation of R(0). In R(0) any path with intermediate veritices is not allowed. That
means only direct edges towards the vertices are considered. In other words the path length of one
edge is allowed in R(0). Thus R(0) is adjacency matrix for the digraph.
2. Construct R(1) in which first vertex is used as intermediate vertex and a path length of two edge is
allowed. Note that R(1)vis build using R(0)which is already computed.
3. Go on building R(k) by adding one intermediatr vertex each time and with more path length. Each
R(k) has to be built from R(k-1)
4. The last matrix in this series is R(1), in this R(n) all the n vertices are used as intermediate vertices.
And the R(n) which is obtained is nothing but the transitive closure of given digraph.

22. List out the memory functions used under Dynamic programming. (MAY 2015)
Memory functions solve in a top-down manner only sub problems that are necessary. Memory
functions are an improvement of dynamic programming because they only solve sub problems that
are necessary and do it only once. However they require more because it makes recursive calls which
require additional memory.
Greedy Algorithm
II Year / IV Sem 16
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

Branch and Bound

Genetic Algorithm
23. Define the single source shortest path problem. (MAY\JUNE 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. (i)Write an algorithm to construct the optimal binary search tree (or) Discuss the algorithm
for finding a minimum cost binary search trees.(8) (R)
(ii) Explain how dynamic programming is applied to solve travelling salesperson problem.
(APR/MAY 2010)(NOV/DEC 2012)(8) (U)
2. Describe traveling sales man problem and how to solve using dynamic programming
(APR/MAY2009) (APR/MAY 2012)(U)
3. Write an algorithm for all pairs shortest path algorithm and what are the time and space
complexity of the algorithm. (APIRL/MAY2009) (APRIL/MAY 2012)(U)
4. To consider the following instance of the knapsack problem n=6 ,(p1,p2,p3,p4 ,p5
,p6)=(w1,w2,w3,w4,w5,w6)=(100,50,20,10,10,7,3) m=165 To use dynamic programming
technique to solve the problem.(Ap)
5. Explain Floyd algorithm with example 8.Write down and explain the algorithm to solve all
pairs shortest paths problem.(APRIL/MAY 2010)(MAY/JUNE 2013).(U)
6. Using Dynamic approach programming, solve the following graph using the Backward
approach. (APRIL/MAY 2011)(An)

7. Write dynamic programming solution for the travelling salesperson problem for the
network with the cost adjacency matrix.(Ap)
0 10 15 30
4 0 9 11
5 13 0 10
7 7 8 0
8. Describe binary search tree with three traversal patterns? Give suitable example with neat
diagram for all three traversal of binary search?(An)
9. With a suitable example, explain all-pair shortest paths problem.(U)

II Year / IV Sem 17
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

10. How is dynamic programming applied to solve the travelling salesperson problem? Explain in
detail with an example?(An)
11. (i) Given the mobile numeric key pad. You can only press buttons that are up,left,right or
down to the first number pressed to obtain the subsequent numbers. You are not allowed to
press bottom row corner buttons (ie * and #). Given a number N, how many key strokes will
be involved to press the given number. What is the length of it? Which dynamic
programming technique could be used to find solution for this? Explain each step with the
help of a pseudo code and derive its time complexity. (12) (MAY 2015)(E)
(ii) How do you construct a minimum spanning tree using Kruskals algorithm?
Explain?(4) (MAY 2015) (U)
12. (i) Let A ={l/119,m/96,c/247,g/283,h/72,f/77,k/92,j/19} be the letters and its frequency of
distribution in a text file. Compute a suitable Huffman coding to compress the data
effectively. (8)(MAY 2015)(C)
(ii) Write an algorithm to construct the optimal binary search tree given the roots r(i,j)
,0≤i≤j≤n. Also prove that this could be performed in time O(n). (8)(MAY 2015) (Ev)
13. Discuss about the algorithm and pseudocode to find the Minimum Spanning Tree using
Prim’s Algorithm. Find the Minimum Spanning Tree for the graph. Discuss about the
efficiency of the algorithm.(MAY\JUNE 2016) (An)

COURSE OUTCOMES:
Describe the greedy paradigm and explain when an algorithmic design situation calls for it.
Recite algorithms that employ this paradigm. Synthesize greedy algorithms, and analyze them.

UNIT IV
ITERATIVE IMPROVEMENT
SYLLABUS: The Simplex Method-The Maximum-Flow Problem – Maximum Matching in
Bipartite Graphs- the Stable marriage Problem.

COURSE OBJECTIVE: Equip the students with mathematical concepts required to analyze and
design computer algorithms.

PART - A
1. Define Simplex Method.
The simplex method is a method for solving problems in linear programming. This method, invented
by George Dantzig in 1947, tests adjacent vertices of the feasible set (which is a polytope) in
sequence so that at each new vertex the objective function improves or is unchanged. The simplex
method is very efficient in practice, generally taking to iterations at most (where is the
number of equality constraints), and converging in expected polynomial time for certain distributions
of random inputs (Nocedal and Wright 1999, Forsgren 2002).

2. Define feasible region.

Feasible region is the set of allits feasible points. It is instructive to sketch the feasible region in the
Cartesianplane. Recall that any equation ax + by = c, where coefficients a andb are notboth equal to
II Year / IV Sem 18
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

zero, defines a straight line. Such a line divides the plane into twohalf-planes: for all the points in one
of them, ax + by < c, while for all the pointsin the other, ax + by > c.

3. Write short notes on the Maximum-Flow problem.

Maximum-flow algorithms require processing edges in both directions, it is convenient to modify the
adjacency matrix representation of a network as follows. If there is a directed edge from vertex i to
vertex j of capacity uij ,then the element in the ith row and the jth column is set to uij , and the
element in the jth row and the ith column is set to −uij; if there is no edge between vertices i and j ,
both these elements are set to zero. Outline a simple algorithm for identifying a source and a sink in a
network presented by sucha matrix and indicate its time efficiency.

4. Define maximum matching.

In many situations we are faced with a problem of pairing elements of two sets.The traditional
example is boys and girls for a dance, but you can easily thinkof more serious applications. It is
convenient to represent elements of two givensets by vertices of a graph, with edges between vertices
that can be paired. Amatching in a graph is a subset of its edges with the property that no two
edgesshare a vertex. A maximum matching—more precisely, a maximum cardinalitymatching—is a
matching with the largest number of edges.

5. Define maximum cardinality.

Maximum cardinality matching—is a matching with the largest number of edges. The maximum-
matching problem is the problem offinding a maximum matching in a given graph. For an arbitrary
graph, this is arather difficult problem. It was solved in 1965 by Jack Edmonds.

6. Define Stable Marriage Problem.

Amarriage matchingMis a set of n (m, w) pairs whose members are selectedfrom disjoint n-element
sets Y and X in a one-one fashion, i.e., each man m fromY is paired with exactly one woman w from
X and vice versa.

7. Define maximum flow problem.

The maximum flow problem can be seen as a special case of more complex network flow problems,
such as the circulation problem. The maximum value of an s-t flow (i.e., flow from source s to sink t)
is equal to the minimum capacity of an s-t cut (i.e., cut severing s from t) in the network, as stated in
the max-flow min-cut theorem.

8. Define BipartiteGraphs?
A bipartite graph, also called a bigraph, is a set of graph vertices decomposed into two disjoint sets
such that no two graph vertices within the same set are adjacent. A bipartite graph is a special case of
a k-partite graphwith . The illustration above shows some bipartite graphs, with vertices in each
graph colored based on to which of the two disjoint sets they belong.

II Year / IV Sem 19
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

9. What do you meant by perfect matching in bipartite graph?

When there are an equal number of nodes on each side of a bipartite graph, a perfect matching is an
assignment of nodes on the left to nodes on the right, in such a way that
i)each node is connected by an edge to the node it is assigned to, and
ii)no two nodes on the left are assigned to the same node on the right

10. Define flow cut.

Cut is a collection of arcs such that if they are removed there is no path from s to t. A cut is said to be
minimum in a network whose capacity is minimum over all cuts of the network.

11. 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.

PART –B
1. Explain the following: (R)
a. Blocking pair
b. Stable Marriage Problem
2. Write a pseudocode for the stable marriage algorithm. (R)
3. Determine the time-efficiency class of the stable marriage algorithm(An)
a. In the worst case
b. In the best case
4. Explain the algorithm for Maximum Bipartite Matching. (R)
5. Explain the simplex method. (U)
6. Example Geometric Interpretation of Linear Programming.(R)
7. Explain Extreme Point Theorem? (R)
8. Write a report on the following: (U)
a. Two-phase simplex method.
b. Ellipsoid method.
c. Bland’s rule
d. Teasible and optimal solutions
9. (i)Maximize p=2x+3y+z (MAY 2015) (C)
Subject to x+y+z≤40
2x+y-z≥10
-y+z≥10
x≥0,y≥0,z≥0

(ii) Write down the optimally condition and algorithmic implementation for finding M-
augmenting paths in bipartite graphs. (MAY 2015) (An)

II Year / IV Sem 20
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

10. (i)Briefly describe on the Stable marriage problem. (MAY 2015)(U)

(ii)How do you compute maximum flow for the following graph using Ford-Fulkerson
method? (MAY 2015)(An)

1
u v
10
2 3 9 4 6

s
7
5
x y
2

11. Summarize the Simplex method. (MAY\JUNE 2016)(U)

12. State and Prove Maximum Flow Min cut Theorem. (MAY\JUNE 2016)(U)
13. Apply the shortest Augmenting Path algorithm to the network shown below.
(MAY\JUNE 2016)(Ap)

COURSE OUTCOMES: Apply mathematical concepts to the analyses and design stages of
different types of algorithms.
UNIT-V
COPING WITH THELIMITATIONS OFALGORITHMPOWER
PART - A

1. Differentiate backtracking and Exhaustive search.

S.No Backtracking Exhaustive search

1. Backtracking is to build up the Exhaustive search is simply a “brute

solution vector one component at a – force” approach to combinatorial
II Year / IV Sem 21
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

time and to use modified criterionproblems. It suggests generating

function Pi(x1,..,xi) (sometimes eachand every element of the
calledbounding function) to test problem’s domain, selecting those of
whether thevector being formed hasthem that satisfy the problem’s
any chance of success. constraints, and
then finding a desired element.
2. Backtracking makes it possible to Exhaustive search is impractical for
solve many large instances of NP- large instances, however applicable
hard problems in an acceptable for small instances of problems.
amount of time.

2.What are the factors that influence the efficiency of the backtracking
algorithm?(APRIL/MAY 2008)
The efficiency of the backtracking algorithm depends on the following four
factors. They are:
i. The time needed to generate the next xk
ii. The number of xk satisfying the explicit constraints.
iii. The time for the bounding functions Bk
iv. The number of xk satisfying the Bk.

3. What is backtracking?(Nov/Dec 2011)

Backtracking constructs solutions one component at a time and suchpartially constructed solutions
are evaluated 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 the
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.
4. What is n-queens problem?
The problem is to place ‘n’ queens on an n-by-n chessboard so thatno two queens attack each other
by being in the same row or in the column orin the same

5. Draw the solution for the 4-queen problem.

Q
Q
Q
Q

6. Define the Hamiltonian cycle.(NOV/DEC 2012)

The Hamiltonian is defined as a cycle that passes through all thevertices of the graph exactly
once. It is named after the Irish mathematicianSir William Rowan Hamilton (1805-1865).It is a

II Year / IV Sem 22
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

sequence of n+1 adjacentverticesvi0, vi1… vin-1, vi0 where the first vertex of the sequence is same
as the last one while all the other n-1 vertices are distinct.

7. What is the subset-sum problem?( Nov/Dec 2012)

Find a subset of a given set S={s1,………,sn} of ‘n’ positive integerswhose sum is equal to a
given positive integer ‘d’.

8. When can a node be terminated in the subset-sum problem?(NOV/DEC 2008)

The sum of the numbers included are added and given as the valuefor the root as s’. The node can
be terminated as a non-promising node ifeither of the two equalities holds:
s’+si+1>d (the sum s’ is too large)

n
j i _ 1
sj  d (the sum s’ is too small)
9. How can the output of a backtracking algorithm be thought of?
The output of a backtracking algorithm can be thought of as an n-tuple(x1, …xn) where each
coordinate xi is an element of some finite linearlyordered set Si. If such a tuple (x1, …xi) is not a
solution, the algorithm finds thenext element in Si+1 that is consistent with the values of (x1, …xi)
and theproblem’s constraints and adds it to the tuple as its (I+1)st coordinate. If suchan element does
not exist, the algorithm backtracks to consider the next valueof xi, and so on.

10. Give a template for a generic backtracking algorithm.(APRIL/MAY 2012)

ALGORITHM Backtrack(X [1..i])
//Gives a template of a generic backtracking algorithm
//Input X[1..i] specifies the first I promising components of a solution
//Output All the tuples representing the problem’s solution
if X[1..i] is a solution write X[1..i]
else
for each element xSi+1 consistent with X[1..i] and the constraints do
X[i+1] = x
Backtrack(X[1..i+1])

11. What is the method used to find the solution in n-queen problem by symmetry?
The board of the n-queens problem has several symmetries so thatsome solutions can be obtained by
other reflections. Placements in the lastn/2 columns need not be considered, because any solution
with the first queen in square can be obtained by reflection from a solutionwith the first queen in
square (1,n-i+1)

12. State m color-ability decision problem.(NOV/DEC 2012)

Let G be a graph and m be a given positive integer. We want to discover whether thenodes of G can
be colored in such a way that no two adjacent nodes have the same color yet only m colors are used.

13. What are the two types of constraints used in Backtracking?

II Year / IV Sem 23
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

 Explicit constraints
 Implicit constraints

14. Define implicit constraint.(APR/MAY 2010& 2012)

They are rules that determine which of the tuples in the solution space of I satisfy the criteria
function. It describes the way in which the xi must relate to each other.

15. Define explicit constraint. (APR/MAY 2010& 2012)

They are rules that restrict each xi to take on values only from a give set. They depend on the
particular instance I of the problem being solved. All tuples that satisfy the explicit constraints
define a possible solution space.

16. What is a promising node in the state-space tree?

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

17. What is a non-promising node in the state-space tree?

A node in a state-space tree is said to be promising if it corresponds toa partially constructed solution
that may still lead to a complete solution;
otherwise it is called non-promising.

18. What do leaves in the state space tree represent?

Leaves in the state-space tree represent either non-promising deadends or complete solutions
found by the algorithm.
19. Define state space tree.

The tree organization of the solution space is referred to as state space tree.

20. Define a live node.(APR/MAY 2010)

A node which has been generated and all of whose children have not yet been generated
is called as a live node.

21. Define a dead node. (APR/MAY 2010)

Dead node is defined as a generated node, which is to be expanded further all of whose
children have been generated.

22. Compared to backtracking and branch and bound?(APRIL/MAY 2008)

Backtracking Branch and bound
State-space tree is constructed using State-space tree is constructed using
depth-first search best-first search
Finds solutions for combinatorial non Finds solutions for combinatorial

II Year / IV Sem 24
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

optimizationproblems optimization problems

No bounds are associated with the Bounds are associated with the each
nodes in the state-space tree and every node in the state-space
tree

23. When can a search path be terminated in a branch-and-bound technique.

A search path at the current node in a state-space tree of a branch and-bound algorithm can be
terminated if 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 solution because the constraints of the problem are already violated.
The subset of feasible solutions represented by the node consists of asingle point in this case compare
the value of the objective function for this feasible solution with that of the best solution seen so far
andupdate the latter with the former if the new solution is better.
30.Give the formula used to find the upper bound for knapsack problem.
A simple way to find the upper bound ‘ub’ is to add ‘v’, the total valueof the items already selected,
the product of the remaining capacity of theknapsack W-w and the best per unit payoff among the
remaining items, whichis vi+1/wi+1, ub = v + (W-w)( vi+1/wi+1)

24. What are NP- hard and NP-complete problems?

The problems whose solutions have computing times are bounded by polynomials of small degree.

25. Define bounding.

 Branch-and-bound method searches a state space tree using any search mechanism in which
all children of the E-node are generated before another node becomes the E-node.
 Each answer node x has a cost c(x) and we have to find a minimum-cost answer node.
Common strategies include LC, FIFO, and LIFO.
 Use a cost function ˆc(·) such that ˆc(x)  c(x) provides lower bound on the solution
obtainable from any node x.

26.List example of NP hard problem.

NP hard graph problem

 clique decision problem(CDP)
 Node cover decision problem(NCDP).

27. What is meant by NP hard and NP complete problem?(NOV/DEC 2011&NOV/DEC 2012)

 NP-Hard Problem: A problem L is NP-hard if any only if satisfy ability reduces to L.

 NP- Complete: A problem L is NP-complete if and only if L is NP-hard and L є NP.
There are NP-hard problems that are not NP-complete.
Halting problem is NP-hard decision problem, but it is not NP-complete.

II Year / IV Sem 25
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

28.An NP-hard problem can be solved in deterministic polynomial time,how?(NOV/DEC 2012)

 If there is a polynomial algorithm for any NP-hard problem, then there are polynomial algorithms
for all problems in NP, and hence P = NP.
 If P ≠ NP, then NP-hard problems cannot be solved in polynomial time, while P = NP does not
resolve whether the NP-hard problems can be solved in polynomial time.

29. How NP-Hard problems are different from NP-Complete?

These are the problems that are even harder than the NP-complete problems. Note that NP-hard
problems do not have to be in NP, and they do not have to be decision problems.
The precise definition here is that a problem X is NP-hard, if there is an NP-complete problem Y,
such that Y is reducible to X in polynomial time.
But since any NP-complete problem can be reduced to any other NP-complete problem in
polynomial time, all NP-complete problems can be reduced to any NP-hard problem in polynomial
time. Then, if there is a solution to one NP-hard problem in polynomial time, there is a solution to all
NP problems in polynomial time.

30. Define hamiltonian circuit problem.

Hamiltonian circuit problem Determine whether a given graph has a Hamiltonian circuit—a path that
starts and ends at the same vertex and passes through all the other vertices exactly once.
31. State Assignment problem. (MAY\JUNE 2016)
There are n people who need to be assigned to execute n jobs, one person per job. (That is, each
person is assigned to exactly one job and each job is assigned to exactly one person.) The cost that
would accrue if the ith person is assigned to the jth job is a known quantity [ , ] for each pair , = 1, 2,
. . . , . The problem is to find an assignment with the minimum total cost.

32. What is state space tree? (MAY\JUNE 2016)

Backtracking and branch bound are based on the construction of a state space tree, whose nodes
reflect specific choices made for a solution’s component .Its root represents an initial state before the
search for a solution begins. The nodes of the first level the tree represent the made for the first
component of solution, the nodes of the second evel represent the Choices for the second components
& so on.

33. Give the purpose of lower bound. (MAY\JUNE 2016)

 The elements are compared using operator < to make selection. 
  Branch and bound is an algorithm design technique that uses lower bound comparisons. 
 Main purpose is to select the best lower bound. 
 Example: Assignment problem and transportation problem. 

34. 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
II Year / IV Sem 26
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

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.

PART –B
1. Explain the n-Queen’s problem & discuss the possible solutions.(APRIL/MAY2008)
(APRIL/MAY2009)(NOV/DEC 2008)(An)
2. Apply backtracking technique to solve the following instance of subset sum problem :
S={1,3,4,5} and d=11(NOV/DEC 2006)(Ap)
3. Explain subset sum problem & discuss the possible solution strategies using backtracking.(An)
4. Write a recursive backtracking algorithm to find all the Hamiltonian cycles of a given graph.
(APRIL/MAY2009) (NOV/DEC 2008)(E)
5. What is backtracking explain detail (APR/MAY 2007)(R)
6. Explain graph coloring in detail. (APR/MAY2009)(U)
7. Give the backtracking algorithm for knapsack problem.(U)
8. Explain the algorithm for finding all m-colorings of a graph.(APRIL/MAY 2012)(U)
9. Describe the backtracking solution to solve 8-Queens problem.(APRIL/MAY 2010)(U)
(APRIL/MAY2012)
10.With an example, explain Graph Coloring Algorithm.(APRIL/MAY 2010)(U)
11. Explain the n-Queen’s problem and trace it for n=6.(APRIL/MAY 2011)(An)
12.(i)Explain Hamiltonian cycles.(NOV/DEC 2012)(8)(U)
(ii) With an example, explains Graph Coloring Algorithm.(8)(U)
13. (i)Explain the control abstraction for Backtracking method. Describe the backtracking solution to
solve 8-Queens problem. (8)(NOV/DEC 2012)(An)
(ii) Let w= {5, 7, 10, 12, 15, 18, 20} and m=35.Find all possible subset of w whose sum is equivalent
to m.Draw the portion of state space tree for this problem. (8)(An)
14. How backtracking works on 8-Queens problem with suitable example?(MAY/JUNE 2013)(U)
15.(i) Give the backtracking algorithm for knapsack problem. (MAY/JUNE 2013) (8)(U)
(ii) Explain elaborately recursive backtracking algorithm. (8)(R)
16. Using backtracking, find the optimal solution to a knapsack problem for the knapsack instance
n=8, m=110,(p1…p7)=(11,21,31,33,43,53,55,65) and (w1…w7)=(1,11,21,33,43,53,55,65).(C)
17. Write an algorithm to determine Hamiltonian cycle in a given graph using back tracking. For
the following graph determine the Hamiltonian cycle.(U)
A B

C F

D E

II Year / IV Sem 27
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

18. Write an algorithm to determine the Sum of Subsets for a given sum and a Set of numbers. Draw
the tree representation to solve the subset sum problem given the numbers set as {3, 5, 6, 7, 2}
with the sum=15. Derive all the subsets.(E)
19. Write an algorithm for N QUEENS problem and Trace it for n=6.(An)
20. What is Branch and bound? Explain in detail.(MAY/JUNE 07) (APIRL/MAY2009)(NOV/DEC
2008)(R)
21. (i)Suggest an approximation algorithm for travelling salesperson problem. Assume that the cost
function satisfies the triangle inequality. (MAY 2015)(E)
(ii)Explain how job assignment problem could be solved, given n tasks and n agents where where
each agent has a cost to complete each task, using branch and bound. (MAY 2015)(An)
22. (i)The knight is placed on the first block of an empty board and, moving according to the rules of
chess, must visit each square exactly once. Solve the above problem using backtracking
procedure. (MAY 2015)(An)
(ii)Implement an algorithm for Knapsack problem using NP-Hard approach. (MAY 2015)(An)
23. State the subset-sum problem and Complete state-space tree of the backtracking algorithm
applied to the instance A={3, 5, 6, 7} and d=15 of the subset-sum problem.(MAY\JUNE
2016)(Ap)

COURSE OUTCOMES: Ability to apply algorithm design techniques to solve certain NP-complete
problems.

II Year / IV Sem 28
PANIMALAR INSTITUTE OF TECHNOLOGY DEPARTMENT OF IT

Course Name : Design and Analysis of Algorithms (CS6402)

Year/Sem : II /IV
Year of Study : 2016 – 2017(Even)
On Completion of this course student will gain
Ability to understand algorithm analysis techniques and analyze asymptotic runtime
C212.1
complexity of algorithms including formulating recurrence relations.
Apply the algorithms and design techniques to solve problems using brute force and divide and
C212.2
conquer.
Ability to understand and design algorithms using dynamic programming and greedy
C212.3
strategy.
C212.4 Ability to understand and design algorithms using max flow – maximum matching.
C212.5 An ability to analyze the limitations of Algorithm power.

COURSE OUTCOMES AND PROGRAM OBJECTIVE, COURSE OUTCOMES AND

PROGRAM SPECIFIC OUTCOMES MAPPING:
CO – PO MATRIX:

CO PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12
C212.1 3 3 - 2 - - - - - - - 2
C212.2 3 2 - 2 - - - - - - - 1
C212.3 2 2 - 2 - - - - - - - 1
C212.4 3 2 - 2 - - - - - - - 1
C212.5 2 1 - 2 - - - - - - - 2

C212* 2.6 2 - 2 - - - - - - - 1.4

CO – PSO MATRIX:

CO PSO1 PSO2 PSO3

C212.1 1 2 2
C212.2 1 2 2
C212.3 1 2 2
C212.4 1 2 2
C212.5 1 2 2
C212* 1 2 2

II Year / IV Sem 29