Monday, March 7, 2016

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

Academic Year
April May 2014
Subject Code


Subject Name

Design and Analysis of Algorithms

Computer Science and Engineering
Fourth Semester

Computer Science and Engineering
Fourth Semester
(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)
(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)

(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)
(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)
(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.


Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents

data recovery