| ||||
| ||||
|
|
|
|||
|
Part-A
|
|
|
||
|
Answer
all the Questions
|
|
|
||
|
1 a)Define algorithm.
|
|
(2M)
|
||
|
b)Write algorithm for binary search ?
|
|
(3M)
|
||
|
c)Define game tree?
|
|
(2M)
|
||
|
d)Write non recursive post order
traversal algorithm ?
|
|
(3M)
|
||
|
e) Define minimum spanning tree ?
|
|
(2M)
|
||
|
f)Briefly Explain Multistage Graphs ?
|
|
(3M)
|
||
|
g)Define graph coloring ?
|
|
(2M)
|
||
|
h)Explain general method for Branch and
Bound ?
|
|
(3M)
|
||
|
i)Define deterministic algorithm ?
|
|
(2M)
|
||
|
j)Briefly Explain the classes of P and
NP ?
|
|
(3M)
|
||
|
Part-B
|
|
|
||
|
2) Write an algorithm for quicksort and
derive worst case time complexity ?
|
|
(10M)
|
||
|
(Or)
|
|
|
||
|
3)Explain strassen ‘s matrix
multiplication algorithm with an example ?
|
|
|
||
|
4)Write algorithms for BFS and DFS ?
|
|
(10M)
|
||
|
(Or)
|
|
|
||
|
5) What is an Articulation Point? Write
the Algorithm to find Articulation points ?
|
|
|||
|
6) Write an algorithm of prim’s minimum
spanning tree.
|
|
(10M)
|
||
|
(Or)
|
|
|
||
|
7) Find the optimal solution of the
Knapsack instance n= 7, M=15, (p1,p2,....p7) =
|
|
|||
|
(10,5,15,7,6,18,3) and
(w1,w2,.....w7)=(2,3,5,7,1,4,1).
|
|
|
||
|
8) What is Graph coloring? Write an
algorithm for it and explain with an example.
|
(10M)
|
|||
|
(Or)
|
|
|
||
|
9) What is bounding? Explain the following with an example.
|
|
(10M)
|
||
|
(a) Job Sequencing with Deadlines
|
|
|
||
|
(b) FIFO Branch and Bound
|
|
|
||
|
(c) LC Branch and Bound
|
|
|
||
|
10) Prove that Chromatic Number decision problem is NP-Complete.
|
|
(10M)
|
||
|
(Or)
|
|
|
||
|
11) State Cook’s theorem and explain
its importance.
|
|
|
||
DESIGN AND ANALYSIS OF ALGORITHMS
| MODEL PAPER-2 | |
|
Part-A
|
|
|
Answer
all the Questions
|
|
|
1 a)Define order of growth.
|
(2M)
|
|
b) Explain about Amortized analysis ?
|
(3M)
|
|
c)Define spanning tree.
|
(2M)
|
|
d) Write a non-recursive algorithm of in-order traversal of a binary
tree ?
|
(3M)
|
|
e)Define principle of optimality.
|
(2M)
|
|
f)Write general method for greedy
method ?
|
(3M)
|
|
g)Define state space.
|
(2M)
|
|
h)Write general method for backtracing
?
|
(3M)
|
|
i) Define non-deterministic algorithm ?
|
(2M)
|
|
j)Write about tractable and intractable
problems ?
|
(3M)
|
|
Part-B
|
|
|
2 )Show how the Quick sort sorts the
following sequences of keys in ascending order 22, 55, 33, 11, 99,
|
(10M)
|
|
|
77, 55,
|
66, 54, 21, 32.
|
|
|
|
(Or)
|
|
|
3)Explain probabilistic analysis and
amortized analysis.
|
|
|
|
4)Describe the strongly connected
components with an example.
|
(10M)
|
|
|
|
(Or)
|
|
|
5)write algorithms for union and find
operations.
|
|
|
|
6) (a)Explain prims algorithm for
minimal spanning tree with an example.
|
(10M)
|
|
|
(b) Differentiate between Divide and
Conquer algorithm & greedy Algorithm.
|
|
|
|
|
(Or)
|
|
7) (a) If objects
are selected in order of increasing vi/wi then prove that the algorithm
knapsack finds an optimal
|
solution.
|
|
|
|
(b) Write an algorithm for Single
source shortest path. Explain with an example
|
.
|
|
|
8) Write a Program schema for a LIFO branch and bound search for
Least-cost answernode.
|
(10M)
|
|
|
(Or)
|
|
|
9) Write an
algorithm for how Eight Queen’s problem can be solved using back tracking and
explain with an example.
|
10)
|
(a) How to deal with a NP-Complete
problem? Discuss with example.
|
(10M)
|
|
|
(b) Write the properties of NP-Complete
and NP-Hard Problems.
|
|
|
|
(Or)
|
|
|
11)
|
Discuss about the complexity of NP-Hard
problems.
|
|
MODEL PAPER -3
|
DESIGN AND ANALYSIS OF
ALGORITHMS
|
|
|
Part-A
|
|
|
Answer all the
Questions
|
|
|
1.a)What
do you mean by linear search?
|
(2M)
|
|
b)what
are the properties of big oh notation
|
(3M)
|
|
c)whatis
greedy algorithm?
|
(2M)
|
|
d)what
is knapsack problem
|
(3M)
|
|
e)what
is travelling sales man problem
|
(2M)
|
|
f)what
do you mean by multi stage graph?
|
(3M)
|
|
g)state
general method of backtracking
|
(2M)
|
|
h)what
is spanning tree? explain with an example
|
(3M)
|
|
i)what
is graph coloring
|
(2M)
|
|
j)what
is NP completeness?
|
(3M)
|
Part-B
2.(a)
Define time and space complexity. Describe different notations used to
represent these
|
complexities.
|
(10M)
|
(b) Describe about Order
of Growth with time function. (Or)
|
4)Explain
BFS &DFS using algorithms
|
(10M)
|
|
Or
|
|
|
5)Explain
AND/OR graphs and BI connected components
|
|
|
6a)Distinguish
the following:
|
(10M)
|
|
(i) Dynamic
Programming vs. Divide and Conquer
|
|
|
(ii) Dynamic
Programming vs. Greedy method
|
|
|
(b)
Write an algorithm for Single source shortest path. Explain with an example
|
(10M)
|
(Or)
7 (a)
Find the shortest tour of TSP for the graph using dynamic programming
(b)
What is the best method between greedy method and dynamic programming to solve
single source shortest path problem? Justify your answer with example
8)
(a) Consider a set S= {5, 10, 12, 13, 15, 18} and d= 30. Solve it for obtaining
sum of
|
subset.
|
|
|
(b)
What is Hamiltonian Cycle? Describe with an example
|
(10M)
|
|
(Or)
|
|
9)
(a) Describe Travelling Salesperson Problem(TSP) using branch and bound with an
example.
(b) Explain 0/1
knapsack problem using branch and bound
|
10)a)
Write the properties of NP-Complete and NP-Hard Problems
|
(10M)
|
(b) How to deal with a NP-Complete
problem? Discuss with example (Or)
11) a)
State and prove Cook’s Theorem
b) Prove
that Chromatic Number decision problem is NP-Complete.
MODEL PAPER-4
DESIGN AND
ANALYSIS OF ALGORITHMS
Part-A
Answer all the
Questions
1.
A)
Differentiate Time complexity from Space complexity. [2 M]
B)
What is a Recurrence Equation? [3
M]
C)
What is called Substitution method? [2
M]
D)
What is an Optimal solution? [3
M]
E)
Define Multistage Graphs. [2
M]
F)
Define Optimal Binary Search Tree. [3
M]
G)
Differentiate Explicit and Implicit Constraints. [2 M]
H)
What is the difference between a Live Node and a Dead Node? [3 M]
I)What
is a Biconnected Graph? [2
M]
J)
What is a FIFO branch - and - bound algorithm? [3
M]
PART B-
2 Explain how Time Complexity is
calculated. Give an example. (10 Marks) (Or)
3
Elaborate on Asymptotic Notations with examples.
4. With a suitable algorithm, explain
the problem of finding the maximum and minimum items in a set of n elements.
(10 Marks)
(Or)
5
Explain Merge Sort Problem using divide and conquer technique. Give an example.
6 Write down and explain the algorithm
to solve all pairs shortest paths problem. (10 Marks) (Or)
7
Explain how dynamic programming is applied to solve traveling sales person
problem
8 Describe the backtracking solution to
solve 8- Queens problem. (10 Marks) (Or)
9
With an example explain Graph coloring
Algorithm.
10 Explain in detail the graph
traversals. (10 Marks) (Or)
11
With an example, explain how the branch - and - bound technique is used to
solve O/I knapsack
MODEL PAPER-5 R09 MODEL
1.
(a) Modify the
Binary search of the text so that in the case of unsuccessful search it returns
the index i such that k(i) < key<k(i+1).
|
(b)
|
Is
Quick sort a stable sorting method? Justify your answer.
|
[7+8]
|
|
2. (a)
|
Explain
the Prim's algorithm with the appropriate example.
|
|
|
(b)
|
Write
the Prim's algorithm to nd the minimum
spanning tree.
|
[7+8]
|
3.
De ne the following terms:
state space, explicit
constraints, implicit constraints, problem state, solution states,
|
answer states, live node, E-node, dead node, bounding functions.
|
[15]
|
4.
(a) Explain how
to implement Warshall's algorithm without using extra memory for storing
elements of the algorithm's intermediate matrices.
|
|
(b)
Give an example of a graph or a digraph with negative weights for which
|
|
|
|
Floyd's
algorithm does not yield the correct result.
|
[7+8]
|
|
5.
|
Suppose
there are n jobs to be executed but only k processors that can work in
|
|
|
|
parallel. The time required by job i is ti. Write an algorithm that
determines which
|
|
|
|
jobs are to be run on which processors and the order in which
they should be run
|
|
|
|
so that
the nish time of the last job is
minimized.
|
[15]
|
|
6.
|
Prove
that every connected graph G on n vertices is the union of at most [(n+1)/2]
|
|
|
|
edge-disjoint
paths.
|
[15]
|
|
7.
|
Show
that the reduction of the CNF satis ability problem to the Clique Decision
|
|
|
|
problem
can be done in polynomial time.
|
[15]
|
8.
Suppose you are choosing between
the following three algorithms:
(a)
Algorithm A
solves problems by dividing them into ve subproblems of half the size,
recursively solving each subproblem, and then combining the solutions in linear
time.
(b)
Algorithm B
solves problems of size n by recursively solving two subproblems of size (n-1)
and then combining the solutions in constant time.
(c)
Algorithm C
solves problems of size n by dividing them into nine subproblems of size n=3,
recursively solving each subproblem, and then combining the so-
lutions
in O(n2) time. What are the running times of each of these algorithms
II B.Tech
II Semester Examinations,APRIL 2011
DESIGN
AND ANALYSIS OF ALGORITHMS
Common to Mechanical Engineering,
Information Technology, Production Engineering, Computer Science And
Engineering
Time: 3 hours Max Marks: 75 Answer any FIVE Questions
All
Questions carry equal marks
?
? ? ? ?
1.
Write a Backtracking algorithm
for the sum of subsets problem using the state
2. Explain 0/1 Knapsack problem and explain the approach to solve
it using Dynamic
3.
(a) Explain the
divide and conquer strategy. How it can be useful in the problem solving.
(b)
Assuming that quick sort uses
the rst item in the list as the pivot
item:
7.
Suppose we want
to nd the minimum spanning tree of the following graph in gure 1.
Figure 1:
(a)
Run Prim's
algorithm; whenever there is a choice of nodes, always use alpha-betic ordering
(e.g., start from node A). Draw a table showing the intermediate values of the
cost array.
(b)
Run Kruskal's
algorithm on the same graph. Show how the disjoint-sets data structure looks at
every intermediate stage (including the structure of the
8.
Let a,b,c be
numbers such that 0 a,b<1, and c> 0. Let T(n) be de ned by
T(n)=T(an)+T(bn)+ cn.
? ? ? ? ?
6
II B.Tech
II Semester Examinations,APRIL2011
DESIGN
AND ANALYSIS OF ALGORITHMS
1.
Given an array of
n elements, (possibly with some of the elements are duplicates), write an
algorithm to remove all duplicates from the array in time O(n log n).[15]
2.
(a) What is Dynamic Programming?
Explain with suitable illustration.
(b)
You are given a list of words, W1,W2,W3,...., Wn and their
corresponding probabilities of occurrence p1,p2,p3,....,pn. The problem
is to arrange these words in a binary search tree in a way that minimizes the
expected total access time. Suggest a good algorithm to implement it. Also
prove the complexity
3.
(a) Give an
algorithm to nd the minimum number of edges that need to be removed from an
undirected graph so that the resulting graph is acyclic.
(b) Does
either Prim's or Kruskal's algorithm work if there are negative edge
4.
Suppose you implement the disjoint-sets data structure using
union-by-rank but not path compression. Give a sequence of m union and nd
operations on n elements
5.
(a) Given a
sequence of n numbers, the distinct elements problem is to check if there are
equal numbers. Give an O(1) time non-deterministic algorithm for this problem.
? ? ? ? ?
1)
a) Define the terms alphabet, string, prefix,
suffix, language give examples to each.
b) Give DFA & NFA which accept the language {
(10)n : n 0 }
c) Define a linear grammar
d) Define a ambiguous CFG
e) Construct a CFG for the set of all strings over
the alphabet {a,b} with exactly twice 10 as many a’s and b’s.
f) Distinguish between DPDA and NPDA
g) Explain the operations of a NPDA with diagram?
h) Define unrestricted grammar.
i) What is the modified version of PCP
2) Construct a Mealy machine which is
equivalent to the Moore machine given in table.
3) Construct the
corresponding Mealy machine to the Moore machine described by the transition
table given.
4)
a) Construct an equivalent unambiguous grammar on the below production
rules.
b) Construct an unambiguous grammar for all
arithmetic expressions with no redundant parenthesis.
A set of
parenthesis is redundant if its removal does not change the expressions.
EàE
+ E / E * E / E / id
(OR)
5)
Explain left & right derivations and left
& right derivation trees with examples?
6)
State and prove pumping lemma for CFG?
(OR)
(OR)
9)
Explain LBA with example?
10) a) Design Turing Machine over
(OR)
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
No comments:
Post a Comment