CS8401 - Design and Analysis of Algorithms - April May 2014

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

PART-A (10 x 2 = 20 Marks)

1. Suppose the worst-case running time of an algorithm is O(f(n)) and its best-case 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 NP-class?

10. Show the class hierarchy of P, NP, and NP-Complete.

Part-B (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 0-1 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 m-coloring 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 odd-even merge sort and provide the corresponding network. (5)

ii. Using the odd-even 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 Boyer-Moore string matching algorithm for finding a pattern on a text, and analyze the algorithm. (8)

(OR)

(b) i. Sort the following numbers on a 2D-mesh, having shuffled row-major 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 NP-Complete. (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 NP-Complete. (10)

ii. What is wrong in the following proof? It is known that 3-SAT 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 DNF-SAT G P, a satisfying assignment for the new formula, and hence for the old formula, can be found in polynomial time. This shows that 3-SAT 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 NP-complete 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

Go back to Anna University B.E Computer Science and Engineering Questions page