QUESTION BANK

SUBJECT : CS3401- ALGORITHMS

SEM / YEAR : IV / II
UNIT I - INTRODUCTION
Algorithm analysis: Time and space complexity -Asymptotic Notations and its properties Best case, Worst
case and average case analysis –Recurrence relation: substitution method -Lower bounds –searching: linear
search, binary search and Interpolation Search, Pattern search:The naïve string-matching algorithm -Rabin-
Karp algorithm -Knuth- Morris-Pratt algorithm. Sorting: Insertion sort –heap sort
PART – A
Q. No Questions

1. 1. What is an algorithm?
An algorithm is a sequence of unambiguous instructions for solving
a problem. i.e., for obtaining a required output for any legitimate
input in a finite amount of time
2. What is Big ‘Oh’ notation?
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 some constant multiple of g(n) for all large n,
i.e., if there exist some positive constant c and some nonnegative
integers n0 such that t(n) ≤ cg(n) for all n≥ n0
3. What are the different criteria used to improve the effectiveness of
algorithm?
(i) The effectiveness of algorithm is improved, when the design,
satisfies the following constraints to be minimum.
Time efficiency - how fast an algorithm in question
runs. Space efficiency – an extra space the algorithm
requires
(ii) The algorithm has to provide result for all valid inputs.
4. Analyze the time complexity of the following segment:
for(i=0;i<N;i+
+)
for(j=N/2;j>0;j
--) sum++;
Time Complexity= N * N/2
= N2 /2
Є
O(N2)
5 What is space complexity and time complexity ?
The space complexity of an algorithm is the amount of memory it
needs to run to completion. The time complexity of an algorithm is the
amount of computer time it needs
to run to completion.
6 Define best-case step count.
The best-case step count is the minimum number of steps that can be
executed for the given parameters.
7 Define worst-case step count.
The worst-case step count is the maximum number of steps that can be
executed for the given parameters.
8 Write an algorithm using Recursive function to fine sum of n numbers,
Algorithm Rsum (a,n)
{
If(n≤0)
then
 Return
0.0;
Else Return Rsum(a, n- 1) + a(n);
9 What is the substitution method?
One of the methods for solving any such recurrence relation is called
the substitution method.
10 What is the binary search?
If ‘q’ is always chosen such that ‘aq’ is the middle element(that
is, q=[(n+1)/2), then the resulting search algorithm is known as
binary search.
11 Write the algorithm for Iterative binary search?
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;
}
12 Give the diagram representation of Notion of algorithm.

13 What are the basic asymptotic efficiency

classes? The various basic efficiency classes
are
 Constant : 1
 Logarithmic : log n
 Linear : n
 N-log-n : nlog n
 Quadratic : n2
 Cubic : n3
 Exponential : 2n
 Factorial : n!
14 What is average case efficiency?
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.
15 Mention the useful property, which can be applied to the asymptotic
notations and its use?
If t1(n) ε O(g1(n)) and t2(n) ε O(g2(n)) then t1(n)+t2(n) ε max
{g1(n),g2(n)} this property is also true for Ω and θ notations. This
property will be useful in analyzing algorithms that comprise of two
consecutive executable parts.
16 Define Ω-notation?
A function t(n) is said to be in Ω (g(n)), denoted by t(n) ε Ω (g(n)), if
t(n) is bounded below 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

17 Write the Brute force algorithm to string matching.[Apr/May

2019]Algorithm NAÏVE(Text, Pattern)
n=length[Text]
n=length[Pattern]
for s=1 to n-m
if pattern[1...m]==Text[s+1...s+m]
Print ”location of pattern is found with shift s”
Time Complexity= O(m)
18 Mention the searching problems.
The searching problem deals with finding a given
value. called a search key, in a given set.
19 Write down formula for Space Complexity Calculation? (Dec 13)
S (P) = c +Sp (instance characteristics). Where c is a constant
that denotes the fixed part of the space
requirements and Sp denotes the variable component.
20 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, which in
turn calls A.
21 What are the advantages of insertion sort?(Nov 2017)
The main advantage of the insertion sort is its simplicity.
 It also exhibits a good performance when dealing with a
small list.
The insertion sort is an in-place sorting algorithm so the space
requirement is minimal.
22 Define Heap sort.
A heap can be defined as a binary tree with keys assigned to its
nodes, one key per node, provided the following two conditions
are met:
 The shape propertyt— he binary tree is essentially
complete (or simply complete), i.e., all its levels are full
except possibly the last level, where only some rightmost
leaves may be missing.
 The parental dominance or heap property—t he key in
each node is greater than or equal to the
keys in its children.
23 Explain String matching problem.
String-matching problem: Given a string of n characters called
the text and a string of m characters (m ≤
n) called the pattern; find a substring of the text that matches
 the pattern. To put it more precisely, we want to find i—the
index of the leftmost character of the first matching substring
in the text—such that

24 Write the brute force algorithm of string matching.

ALGORITHM BruteForceStringMatch(T [0..n − 1], P[0..m − 1])
//Input: An array T [0..n − 1] representing a text and an array
P[0..m − 1] of representing a pattern
//Output: The index of the first character in the text or −1 if the
search is unsuccessful
for i ←0 to n − m do
j ←0
while j < m and P[j ]= T [i + j ] do
j ←j + 1
if j = m return i
return −1
PART – B
Discuss in detail about fundamentals of algorithmic
1.
problem solving?
Write the asymptotic notations used for best case,average
2.
case andworst case analysis of algorithms and Write an
algorithmfor finding maximum element of an array
performbest , worst and average case complexity with
appropriate order notations
Explain the method of solving recurrence equations with
3.
suitable example.
4. i)Describe the basic efficiency classes in detail.
Write an algorithmfor Fibonacci numbers generation and
compute the following
a) How many times is the basic operation executed
b) What is the efficiency class of this algorithm
Explain about linear search and binary search algorithms.
5.
Difference between binary search and interpolation search with
6.
algorithm and example.
Explain about pattern matching algorithms.
7.

8. Explain about heap sort.

Design a recursive algorithm to compute the factorial function F

9. (n) =n! and derive the recurrence relation.

Solve the following recurrence relations

a) x(n)=x(n -1) + 5 for n > 1 x(1)=0
1 b) x(n)=3x(n-1) for n > 1 x(1)=4
c) x(n)=x(n-1)+n for n > 0 x(0)=0
d) x(n)=x(n/2)+n for n > 1 x(1)=1 ( solve for n=2k)
e) x(n)=x(n/3)+1 for n >1x(1)=1 (solve for n=3k)
Consider the following recursion algorithm Min1(A[0
n-1])
If n=1 return A[0]
2 Else temp = Min1(A[0.. . .n-2])
 If temp <= A[n-1] return
temp ElseReturn A[n-1]
a) What does this algorithm compute?
b) Setup a recurrence relationfor the algorithms basic
operation count and solve it
3 Sort the following numbers using heap sort.
73,6,57,88,60,42,83,72,48,85
Apply the Knuth- Morris-Pratt algorithm for the following pattern
4 search: pattern=abcday and text=abcabxdaabbayabcday

UNIT II GRAPH ALGORITHMS

Graph algorithms: Representations of graphs -Graph traversal: DFS –BFS -applications -Connectivity,
strong connectivity, bi-connectivity -Minimum spanning tree: Kruskal’s and Prim’s algorithm-Shortest
path:Bellman- Ford algorithm -Dijkstra’s algorithm -Floyd-Warshall algorithm Network flow: Flow
networks -Ford-Fulkerson method –Matching:Maximum bipartite matching
PART –A
Q.No Questions
1. Define principle of optimality.
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.

2. What are the labels in Prim’s algorithm used for?

Prim‘s algorithm makes it necessary to provide each vertex not
in the current tree with the information about the shortest edge
connecting the vertex to a tree vertex. The information is
provided by attaching two labels to a vertex.
• The name of the nearest tree vertex.
• The length of the corresponding edge

3. How are the vertices not in the tree split into?

The vertices that are not in the tree are split into two sets
• Fringe : It contains the vertices that are not in the tree but
are adjacent to atleast one tree vertex.
• Unseen : All other vertices of the graph are called unseen
because they are yet to be affected by the algorithm.

4. What are the operations to be done after identifying a vertex

u* to be added to the tree?
After identifying a vertex u* to be added to the tree, the
following two operations need to be performed
• Move u* from the set V-VT to the set of tree vertices VT.
For each remaining vertex u in V-VT that is connected to u* by a
shorter edge than the u‘s current distance label, update its labels
by u* and the weight of the edge between u* and u,
respectively.
5. What is the use of Dijksra’s algorithm?
Dijkstra‘s algorithm is used to solve the single-source
shortest- paths problem: for a given vertex called the source in a
weighted connected graph, find the shortest path to all its other
vertices. The single-source shortest-paths problem asks for a
family of paths, each leading from the source to a different vertex
in the graph, though some paths may have edges in common.
6. Define Spanning tree.
 Spanning tree of a connected graph G: a connected acyclic
subgraph of
G that includes all of G‘s vertices
7. What is minimum spanning tree.
Minimum spanning tree of a weighted, connected graph G: a
spanning tree of G of the minimum total weight

8. Disuss Warshall’s Algorithm with suitable

diagrams?
Main idea: Use a bottom-up method to construct the
transitive closure of a given digraph with n
vertices through a series of nxn boolean matrices:
R(0) ,…, R(k-1), R(k) , …, R(n)
R(k) : rij(k) = 1 in R(k) , iff
there is an edge from i to j; or
there is a path from i to j going
through vertex 1; or
there is a path from i to j going
through vertex 1 and/or 2; or
...
there is a path from i to j going through 1, 2, … and/or k
9. Floyd’s Algorithm
• All pairs shortest paths problem: In a weighted graph,
find shortest paths between every pair of vertices.
• Applicable to: undirected and directed weighted graphs; no
negative weight.
• Same idea as the Warshall‘s algorithm : construct
solution through series of matrices D(0) , D(1), …, D(n)

10. Knapsack problem

Find the most valuable subset of the given n items that fit
into a knapsack of capacity W.
11. The Knapsack Problem and Memory Functions
• The Recurrence
a. Two possibilities for the most valuable
subset for the subproblem 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
V[i-1, j] if j – wi < 0 V[0, j] = 0 for j  0 and V[i, 0] = 0 for i  0

12. Define linear programming.

Every LP problem can be represented in such form
maximize 3x + 5y
maximize 3x + 5y + 0u + 0v
subject to x+ y≤4
subject to x+ y
+ u = 4x + 3y ≤ 6x + 3y +v=
6
x≥0, y≥0 x≥0, y≥0,
 u≥0, v≥0

13. What is basic solution? 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 nonbasic; the variables obtained by solving
the system are called basic. A basic solution is called feasible
if all its (basic) variables are nonnegative.

14. State max – flow – min – cut theorem.

The value of maximum flow in a network is equal to the capacity
of its minimum cut
15. Define Bipartite Graphs.
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
16. What is augmentation and augmentation 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.

17. Define flow and flow conservation requirement.

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
PART - B
Construct a minimum spanning tree using Kruskal’s
1. algorithm with your own example
How will find the shortest path between two given
2. vertices using Dijikstra’s algorithm? Explain the pseudo
code with an example.
Explain Warshall’s algorithm to find the transitive closure
3. with an example. Prove that the time efficiency of warshall’s
algorithm is cubic
Apply Kruskal’s algorithm to find a minimum spanning tree of
4. the following graph.
 Solve the following instance of the single source shortest
5. path problem with vertex a as the source.

Explain the construction of huffman coding tree with an

6. example.
Given the mobile numeric keypad. You can only press
7. buttons that are up,left,right or down to the first numbered
pressed to obtain the subsequent numbers.You are not
allowed to press bottom row corner buttons (i.e. * 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. (May 15)
PART-C
Write and explain Floyd’s algorithm for the all-pairs shortest
1 path problem. Using this find the length of the shortest path
between all pairs of vertices of the following graph. (Dec
06,07)

Explain the pseudo code for prim’s algorithm and apply the
same to minimum spanning tree for the following graph.
2 (Dec 07,May 18)

Explain the pseudo code for prim’s algorithm and apply the
3 same to minimum spanning tree for the following graph.
 Apply Kruskal’s algorithm to find a minimum spanning tree of
4 the following graph.

UNIT III ALGORITHM DESIGN TECHNIQUES

Divide and Conquer methodology: Finding maximum and minimum -Merge sort -Quick sort Dynamic
programming:Elements of dynamic programming —Matrix-chain multiplication -Multi stage graph —
Optimal Binary Search Trees. Greedy Technique: Elements of the greedy strategy -Activity-selection
problem –-Optimal Merge pattern —Huffman Trees.
PART - A
Q.No Questions

Define the divide an conquer method.

1.
Given a function to compute on ‘n’ inputs the divide-and-
comquer strategy suggests splitting the inputs in to’k’ distinct
susbsets, 1<k
<n, yielding ‘k’ subproblems. The subproblems must be solved,
and then a method must be found to combine subsolutions into a
solution of the whole. If the subproblems are still relatively
large,
then the divide-and conquer strategy can possibly be reapplied.
2 What is the Quick sort?
Quicksort is divide and conquer strategy that works by
partitioning it’s input elements according to their value relative
to some preselected element(pivot). it uses recursion and the
method is
also called partition –exchange sort.
3 Write the Analysis for the Quick sort.
O(nlogn) in average and best cases
O(n2) in worst case
4 what is Merge sort? and Is insertion sort better than the merge
sort?
Merge sort is divide and conquer strategy that works by dividing
an input array in to two halves, sorting them recursively and
then merging the two sorted halves to get the original array
sorted Insertion sort works exceedingly fast on arrays of less
then 16 elements, though for large
‘n’ its computing time is O(n2).
5 Write a algorithm for straightforward maximum and minimum?
Algorithm straight MaxMin(a,n,max,min)
//set max to the maximum and min to the minimum of a[1:n]
{
max := min: =
a[i]; for i = 2 to n
do
{
if(a[i] >max) then max: = a[i];
if(a[i] >min) then min: = a[i];
}
}
6 what is general divide and conquer recurrence?
Time efficiency T(n)of many divide and conquer algorithms
satisfies the equation T(n)=a.T(n/b)+f(n).This is the general
7 recurrence relation.
Describe the recurrence relation for 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 n = 1, a a constant
2T (n/2) + n n >1, c a constant
8 Explain the greedy method.
Greedy method is the most important design technique,
which makes a choice that
looks best at that moment. A given ‘n’ inputs are required
us to obtain a subset that
satisfies some constraints that is the feasible solution. A greedy
method suggests that
one can device an algorithm that works in stages considering
one input at a time.
9 What are the constraints of knapsack problem?
To maximize
Σpixi 1≤i≤n
The constraint is : Σwixi ≥ m and 0 ≤ xi ≤ 1 1≤ i
≤ n 1≤i≤n
where m is the bag capacity, n is the number of objects and
for each object i wi
and pi are the weight and profit of object respectively.
10 What is a minimum cost spanning tree?
A spanning tree of a connected graph is its connected acyclic
subgraph that contains all vertices of a graph. A minimum
spanning tree of a weighted connected graph is its spanning tree
of the smallest weight where bweight of the tree is the sum of
weights on all its edges. A minimum spanning subtree of a
weighted graph (G,w) is a spanning subtree of
G of minimum weight w(T )= Σ w(e ) e€ T
Minimum Spanning Subtree Problem: Given a weighted
connected undirected graph (G,w), find a minimum spanning
subtree
11 Specify the algorithms used for constructing Minimum cost
spanning tree.
a) Prim’s Algorithm
b) Kruskal’s Algorithm
12 State single source shortest path algorithm (Dijkstra’s
algorithm).
For a given vertex called the source in a weigted
connected graph,find shotrtest paths to all its other
 vertices.Dijikstra’s
algorithm applies to graph with non-negative weights only.
13 . What is Knapsack problem?
A bag or sack is given capacity and n objects are given. Each
object has weight wi and profit pi .Fraction of object is
considered as xi (i.e) 0<=xi<=1 .If fraction is 1 then entire
object is put into sack. When we place this fraction into the
sack we get wixi
and pixi.
14 Write any two characteristics of Greedy Algorithm?
* To solve a problem in an optimal way construct the solution
from given set of candidates.
* As the algorithm proceeds, two other sets get accumulated
among this one set contains the candidates that have been
already considered and chosen while the other set contains
the candidates that have been considered but rejected.
15 Write the difference between the Greedy method and
Dynamic programming.
Greedy method
Only one sequence of decision
is generated.
It does not guarantee to give
an optimal solution always.
Dynamic programming
Many sequence are generated
It definitely gives an optimal
solution always.
16 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.
17 Define multistage graph
A multistage graph G =(V,E) is a directed graph in which
the vertices are partitioned in to K>=2 disjoint sets
Vi,1<=i<=k.The multi stage graph problem is to find a
minimum cost paths from
s(source ) to t(sink) Two approach(forward and backward)
18 Define Distance matrix
Recording the lengths of shortest path in n x n matrix is
called Distance matrix(D)
19 Define floyd’s algorithm
To find all pair shortest path
The algorithm computes the distance matrix of a weighted
graph with n vertices
through series of n by n matrices :D(0)…D(k-1),D(k)…..D(n)
20 State time and space efficiency of
OBST SPACE EFFICIENCY
:QUADRATIC
TIME EFFICIENCY : CUBIC.

PART – B
Explain Divide andConquerMethod
1.
 Explain Merge Sort with suitable
2
example
Discuss QuickSortAlgorithm and Explain it with
3 example. Derive Worst case and Average
Case Complexity.
4 Explain in detail about Travelling
Salesman Problem using
exhaustivesearch.
Explain in detail about Knapsack
5
Problem.
6 Write algorithm to find closest pair of points using
divide and conquer and explain it with example.
Derive the worst case and average
case time complexity.
Write Strassen’s matrix multiplication algorithm. Is there
7 any time efficiency improvement compared to
ordinary matrix multiplication?
Explain an algorithm to find optimal binary search tree
8 with example or write an algorithm to construct the OBST
tree for the given the roots r (i, j), 0≤i≤j≤n. Also prove that
this could be performed in time
O(n).
Find a minimum cost path from S to t for the following
9 multistage graph

Develop the optimal binary search tree for the following

10 instance and explain the algorithm in detail.
Key A B C
Probability 0. 0.2 0.4 0.3
1
 PART-C
Apply merge sort to sort the list E, X, A, M, P, L, E in
1 alphabetical order.

Write an algorithm for merge sorting. Show the

intermediate steps when the numbers
310, 285, 179, 652, 351, 423, 861, 254, 450, 520 are sorted
2 using Merge Sort

Sort the following set of elements using quick sort.

12,24,8,71,4,23,6
3

Find a minimum cost path from S to t for the following

multistage graph. Use Forward and Backward approach also
4 for solving this problem

UNIT IV STATE SPACE SEARCH ALGORITHMS

Backtracking: n-Queens problem -Hamiltonian Circuit Problem -Subset Sum Problem –Graph colouring
problem Branch and Bound: Solving 15-Puzzle problem -Assignment problem -Knapsack Problem -
Travelling Salesman Problem

PART – A
Q.No Questions

1. What are the requirements that are needed for performing

Backtracking?
To solve any problem using backtracking, it requires that all
the solutions satisfy a
complex set of constraints. They are:
i. Explicit constraints.
ii. Implicit constraints.
2 Define explicit constraint.
They are rules that restrict each x to take on values only from
a give set. They i
depend on the particular instance I of the problem being solved.
All tuples that satisfy the
explicit constraints define a possible solution space.
3 Define implicit constraint.
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 x must relate
to each other
4 Define state space tree.
The tree organization of the solution space is referred to as state
space tree.
5 Define a live node.
A node which has been generated and all of whose children
have not yet been generated is called as a live node.
6 Define a dead node.
Dead node is defined as a generated node, which is to
be expanded further all of
whose children have been generated.
7 Define Branch-and-Bound method.
The term Branch-and-Bound refers to all the state space
methods in which all children of the E-node are
generated before any other live node can become the E-
node.
8 What are the searching techniques that are commonly used
in Branch-and-Bound
method.
The searching techniques that are commonly used in Branch-
and-
Bound
method are:
i. FIFO
ii. LIFO
iii. LC
iv. Heuristic search
9 State 8 – Queens problem.
The problem is to place eight queens on a 8 x 8 chessboard so
that no two queen “attack” that is, so that no two of them are on
the same row, column or on the diagonal.
10 State Sum of Subsets problem.
Given n distinct positive numbers usually called as weights ,
the problem calls for finding all the combinations of these
numbers whose sums are m.
11 State m – colorability decision problem.
Let G be a graph and m be a given positive integer. We want to
discover whether the nodes of G can be colored in such a way
that no two adjacent nodes have the same color yet only
m colors are used.
12 Define chromatic number of the graph.
The m – colorability optimization problem asks for the
smallest integer m for which the graph G can be colored.
This integer is referred to as the chromatic number of the
graph.
13 Define a planar graph.
A graph is said to be planar iff it can be drawn in such a way
that no two edges cross each
other.
Define n-queens problem.
14 The problem is to place n queens on an n × 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.
Define state space tree. (Dec 06,May 16)
15 It is convenient to implement this kind of processing by
 constructing a tree of choices being made, called the
state-space tree. Its root represents an initial state before
the search for a solution begins. The nodes of the first level
in the tree represent the choices made for the first
component of a solution; the nodes of the
second level represent the choices for the second
component, and so on.
Define Hamiltonian circuit problem.(June 06, Dec14, May 15)
16 Let G= (V, E) the € connected graph, with n vertices. A
Hamiltonian cycle is a round trip path along n
edges of G that visits every vertex once and returns to its
starting position.
Mention the relation between P and NP.
17

Mention the relation between P, NP, NP-Hard and NP Complete

18 Problem.

What is an articulation point in a graph? (May 17)

19 A vertex of a connected graph is said to be its articulation
point if its removal with all edges incident to it
breaks the graph into disjoint pieces.
Give the purpose of lower bound. (May 16)
20 Given a class of algorithms for solving a particular problem,
a lower bound indicates the best possible
efficiency any algorithm from this class can have.
PART - B
Give solution to Subset sum problem using Backtracking
1. technique

Give solution to Hamiltonian circuit using Backtracking

2
technique
Explain the backtracking algorithm for the n-
3 queens problem.
Find the optimal solution for the
4
assignment operator given below
Job1 Job2 Job3 Job4
Person 1 4 3 8 6
Person 2 5 7 2 4
Person 3 16 9 3 1
Person 4 2 5 3 7
 Apply Branch and Bound algorithm to solve the Travelling
5 salesman problem for (May 17)

Solve the following instance of the travelling salesman

6 problem by branch and bound method and explain in detail.
(Dec 07)

Apply the branch and bound algorithm to solve the

7 following knapsack problem and explain in detail.

State the subset-sum problem and Complete state-space

8 tree of the backtracking algorithm applied to the
instance A= {3, 5, 6, 7} and d= 15 of the subset-sum
problem. (May 16)
Find a Hamiltonian circuit or disprove its existence in the
9 graph given below

PART-C
Explain Hamiltonian circuit in a graph. Use backtracking to
1 get a Hamiltonian circuit of following the graph.

Explain Hamiltonian circuit in a graph. Use backtracking to

2 get a Hamiltonian circuit of following the graph.(Dec 07)
 Solve the following assignment problem using branch and
bound technique. Explain in detail how branch and bound
3 technique is useful for solving assignment problems.

UNIT V NP-COMPLETE AND APPROXIMATION ALGORITHM

Tractable and intractableproblems: Polynomial time algorithms –Venn diagram representation -NP-
algorithms -NP- hardness and NP-completeness –Bin Packing problem -Problem reduction: TSP 79CNF
problem. Approximation Algorithms: TSP -Randomized Algorithms: concept and application -primality
testing -randomized quick sort
-Finding kthsmallest number
PART – A
Q.No Questions
1. What are NP- hard and Np-complete problems?
The problems whose solutions have computing times are
bounded by polynomials of
small degree.
2 What is a decision problem?
Any problem for which the answer is either zero or one is
called decision problem.
3 what is approximate solution?
A feasible solution with value close to the value of an
optimal solution is called approximate solution.
4 what is promising and non-promising nodes?
a node in a state space tree is said to be promising if it
corresponds to a partially constructed solution from
which a complete solution can be obtained.
The nodes which are not promising for solution in a state space
tree are called non-promising nodes.
5 Write formula for bounding function in Knapsack problem
In knapsack problem upper bound value is computed by
the formula
UB = v + (W-w) * (vi+1/wi+1)
6 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 is to find a tour of
minimum cost.
 In branch and bound technique of TSP problem Lower bound
lb=
s/2
7 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 same set of machines.
8 Give the time complexity and space complexity of
traveling salesperson problem.
Time complexity is O (n2 2n). Space complexity is O (n 2n).
9 Differentiate decision problem and optimization problem
Any problem for which the answer is either zero or one is
called decision problem
Any problem that involves the identification of an
optimal (maximum or minimum) value of a given cost
function is
called optimization problem
10 what is class P and NP?
P is set of all decision problems solvable by
deterministic algorithms in polynomial time.
NP is set of all decision problems solvable by non deterministic
algorithms in polynomial time.
11 Define NP-Hard and NP-Complete problems
Problem L is NP-Hard if and only if satisfiability reduces
to L. A Problem L is NP-Complete if and only if L is NP-
Hard and L belongs to NP.
n))
12 Define optimization Problem.
Any problem that involves the identification of an optimal
(maximum or minimum) value of a given cost
function is known as an optimization problem. An
Optimization algorithm is used to solve an optimization
problem
13 Mention the relation between P and NP.

14 Mention the relation between P, NP, NP-Hard and NP Complete

Problem.
15 How NP-hard problems are different from NP-Complete? (May 15)
NP-hard : If an NP-hard problem can be solved in
polynomial time, then all NP-complete problems can be
solved in polynomial time.
NP-Complete: A problem that is NP-complete has the
property that it can be solved in polynomial time iff if all
other NP-complete problems can also be solved in
polynomial time.

PART - B
1.
Explain in detail about approximation algorithm for the
Knapsack problem

2
Explain the approximation algorithm for the travelling salesman
problem (TSP)
3 Explain the approximation Algorithm for NP-hard Problem:

4 Explain P, NP and NP complete problems.

5 Explain in detail about approximation algorithms for NP

hard problems. How all you quantify the accuracy of an
approximation algorithm?
6 Write an algorithm to solve the Travelling salesman
problem and prove that it is a 2 time approximation
algorithm.

7 Elaborate on nearest neighbor algorithm, multifragment

heuristic algorithm for TSP problem.
8 Implement an algorithm for Knapsack problem using NP-
Hard approach.
9 Give any five undecidable problems and explain the
famous halting problem.

PART C
Apply the branch and bound algorithm to solve the
following knapsack problem and explain in detail.
1
Item Weight Value

1 4 $40
 2 7 $42

3 5 $25

4 3 $12

The knapsack capacity W is 10

2 Apply the branch and bound algorithm to solve the
following knapsack problem and explain in detail.
Item Weight value

1 2 1

2 3 2

3 4 5
The knapsack capacity W is 6.
The Knight is placed on the first block of an empty board
3 and, moving accordingly to the rules of chess, must visit
each square exactly once. Solve the above problem using
backtracking procedure.