Anna University Questions  CS8401  Design and Analysis of Algorithms  April May 2014, Computer Science and Engineering (CSE), Fourth Semester, Regulation 2012
Exam

B.E/B.Tech. (Full
Time) DEGREE END SEMESTER EXAMINATIONS

Academic
Year

April May 2014

Subject
Code

CS8401 
Subject
Name

Design and Analysis of Algorithms 
Branch

Computer Science and Engineering

Semester

Fourth Semester

Regulation

2012

B.E
/ B.Tech. (Full Time) DEGREE END SEMESTER EXAMINATIONS, APRIL / MAY 2014
Computer Science
and Engineering
Fourth Semester
CS8401
DESIGN AND ANALYSIS OF
ALGORITHMS
(Regulations 2012)
Time : 3 Hours Answer A L L Questions Max. Marks 100
PARTA
(10 x 2 = 20 Marks)
1. Suppose the worstcase running time
of an algorithm is O(f(n)) and its
bestcase running time is Ω(f(n)).
Then, can you say the running time of the algorithm is Θ(f(n))? Justify your answer.
2. Find two functions f(n) and g(n) such that f(n) ≠ O(g(n))
and g(n) ≠ O(f(n)). Justify your
answer.
3. What do you mean by Principle of
Optimality?
4. How does dynamic programming differ
from divide and conquer?
5. Compare and contrast backtracking
and branch & bound?
6. The LC branch and bound is used
with least cost. Suppose you wish to use this technique for a maximization
problem, what kind of changes you need to do?
7. State the hierarchy of various PRAM
models, and also state the reason.
8. When do you say a sequence of
numbers as bitonic?
9. Formally define NPclass?
10. Show the class hierarchy of P, NP,
and NPComplete.
PartB
(5* 16 = 80 Marks)
11. (a) Using iterative method, find
the asymptotic value of T(n) for (5)
(b) Prove that log
n Є O(√n) but √n ∉
O(logn).
(3)
(c) Can selection be done in O(n) worst case, i f the size of the
input is n. If so, how does it be done? Analyze your algorithm to guarantee the
linear worst case time. (8)
12. (a) i. Explain the greedy based
algorithm for the fractional knapsack problem, and prove that this algorithm
always yields the optimal solution. (8)
ii. Can you use this algorithm for
solving 01 knapsack problem? If your answer is 'yes', provide appropriate
proof. If not, justify your answer with an example. (3)
iii. Construct a minimum spanning tree
of the following graph using Prim's algorithm. (5)
(OR)
(b) i. Using dynamic programming
method, determine the optimal tour and its length for the Traveling
Salesperson, using the distance matrix shown below. Assume that the tour starts
from city A. (8)
ii. Using dynamic programming method
find all pair shortest distances of the following instance. (8)
13. (a) i. Device a backtracking
algorithm that solves mcoloring problem on a graph, and analyze the algorithm.
(8)
ii. A bank has 15 million Euro, which
can be invested into stocks of four companies (1, 2, 3, and 4) to get more
profits. The table reports, for each company, the net revenue and the amount of
money (in million) that must be invested into i t . Solve the problem with a
branch and bound algorithm. Note that partial investment is not possible. (8)
Company

1

2

3

4

Revenue
Money

10
2

10
4

12
6

18
9

(OR)
(b) i. Design a backtracking algorithm
that inputs a natural number C, and outputs all the ways that a group of
ascending positive numbers can be summed to give C. For example, i f C = 6, the
output should be 1 + 2 + 3, 1 + 5, 2 + 4, and 6. (8)
ii. Apply branch and bound algorithm
to solve Traveling Salesperson problem for the following instance. Assume, the
tour starts from city A. (8)
14. (a) i. Describe the concept of
oddeven merge sort and provide the corresponding network. (5)
ii. Using the oddeven merge sort
network, provided by you for the question 14(a)i, merge the following
sequences: (3)
A = [27, 49, 84,
91] and B = [17, 32, 53, 63]
iii. Explain BoyerMoore string
matching algorithm for finding a pattern on a text, and analyze the algorithm.
(8)
(OR)
(b) i. Sort the following numbers on a
2Dmesh, having shuffled rowmajor order representation. (8)
50, 9, 42, 15, 14,
20, 11, 12, 6, 21, 8, 33, 5, 13, 7, 30
ii. Explain KMP string matching
algorithm for finding a pattern on a text, and analyze the algorithm. (8)
15. (a) i. Prove that the vertex cover
problem is in NPComplete. (8)
ii. Write and explain the
approximation algorithm for the vertex cover problem. Prove that the ratio
bound of the algorithm is 2. Also, prove that this bound is tight. (8)
(OR)
(b) i. Prove that the Hamiltonian
cycle problem is in NPComplete. (10)
ii. What is wrong in the following
proof? It is known that 3SAT is NP Complete. Given a Boolean
formula in conjunctive normal form with at most three literals per clause, use
the distributive law to construct an equivalent formula in disjunctive normal
form. For example,
Since DNFSAT G P, a
satisfying assignment for the new formula, and hence for the old formula, can
be found in polynomial time. This shows that 3SAT G P , and
hence that P = NP. (3)
iii. Consider a reduction of problem A
to problem B. What is the most precise claim you can make
about problem B for each of the following situations? (3)
• A is
NPcomplete and the reduction is in polynomial time.
• A is
in P and the reduction is also in polynomial time.
************************
Go
back to Anna University B.EComputer Science and Engineering Regulation 2012 Fourth Semester Questions page
Go back to Anna University B.E Computer Science and Engineering Questions April May 2014 page