Description

hi

Categories

Published

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Similar Documents

Share

Transcript

Code No: R09220505
R09 Set No. 2
II B.Tech II Semester Examinations,APRIL 2011DESIGN AND ANALYSIS OF ALGORITHMSCommon to Mechanical Engineering, Information Technology, ProductionEngineering, Computer Science And EngineeringTime: 3 hours Max Marks: 75Answer any FIVE QuestionsAll Questions carry equal marks
1. (a) Modify the Binary search of the text so that in the case of unsuccessful searchit 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 memoryfor storing elements of the algorithm’s intermediate matrices.(b) Give an example of a graph or a digraph with negative weights for whichFloyd’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 inparallel. The time required by job i is t
i
. Write an algorithm that determines which jobs are to be run on which processors and the order in which they should be runso 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 Decisionproblem 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 thesize, recursively solving each subproblem, and then combining the solutions inlinear time.(b) Algorithm B solves problems of size n by recursively solving two subproblemsof size (n-1) and then combining the solutions in constant time.(c) Algorithm C solves problems of size n by dividing them into nine subproblemsof 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(in big-O notation), and which would you choose? [5+5+5]1
Code No: R09220505
R09 Set No. 2
2
Code No: R09220505
R09 Set No. 4
II B.Tech II Semester Examinations,APRIL 2011DESIGN AND ANALYSIS OF ALGORITHMSCommon to Mechanical Engineering, Information Technology, ProductionEngineering, Computer Science And EngineeringTime: 3 hours Max Marks: 75Answer any FIVE QuestionsAll Questions carry equal marks
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,
W
1
,
W
2
,
W
3
,....,
W
n
and their correspondingprobabilities of occurrence
p
1
,
p
2
,
p
3
,....,
p
n
. The problem is to arrange thesewords in a binary search tree in a way that minimizes the expected total accesstime. Suggest a good algorithm to implement it. Also prove the complexityof the algorithm derived by you. [7+8]3. (a) Give an algorithm to ﬁnd the minimum number of edges that need to beremoved 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 edgeweights. [7+8]4. Suppose you implement the disjoint-sets data structure using union-by-rank but notpath compression. Give a sequence of m union and ﬁnd operations on n elementsthat take (m log n) time. [15]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 forthis problem.(b) Obtain a nondeterministic algorithm of complexity O(n) to determine whetherthere is a subset of n numbers a
i
, 1
≤
i
≤
n, that sums to n. [7+8]6. (a) Is Quick sort a stable sorting method? Justify your answer.(b) Derive the time complexity of Strassen’ Matrix multiplication. [7+8]7. Write a branch- and - bound algorithm for the job sequencing with deadlines prob-lem. [15]8. Write the algorithm BKnap for solving 0/1 Knapsack Problem using Back Trackingmethod. [15]
3
Code No: R09220505
R09 Set No. 1
II B.Tech II Semester Examinations,APRIL 2011DESIGN AND ANALYSIS OF ALGORITHMSCommon to Mechanical Engineering, Information Technology, ProductionEngineering, Computer Science And EngineeringTime: 3 hours Max Marks: 75Answer any FIVE QuestionsAll Questions carry equal marks
1. Write an algorithm in pseudocode to count the number of capital letters in a ﬁleof text. How many comparisions does it do? What is fewest number of incrementsit might do? What is the largest number? Assume that N is number of charactersin a ﬁle. [15]2. Explain the problem of All Pairs Shortest Path Problem and write its algorithmusing Dynamic Programming. Prove that it is working with a numerical example.[15]3. (a) What puts a problem into class NP.(b) Explain the diﬀerences between decision and optimization problems. [7+8]4. Write an algorithm schema FifoBB for a FIFO branch-and-bound search for aleast-cost answer node. [15]5. (a) Explain the merge sort with the example. Write the algorithm of merge sort,and the running time of the algorithm.(b) Compute the product of the following matrices of 4 x4 size, using Strassen’smatrix multiplication method. A =
1 2 3 45 6 7 89 1 2 34 5 6 7
B
=
8 9 1 23 4 5 67 8 9 12 3 4 5
[7 + 8]6. Deﬁne an articulation point in a graph. Write algorithm for ﬁnd articulation point.Write the time complexity of your algorithm. [15]7. Suppose you are given n men and n women and two of (n x n) arrays P and Qsuch that P(i,j) is the preference of man i for women j and Q(i,j) is the preferenceof woman i for man j. Design an algorithm that ﬁnds a pairing of men and womensuch that the sum of the product of the preferences is maximized. [15]8. (a) Compute the time complexity of deriving minimum spanning tree from theweighted connected graph using Kruskal’s algorithm(b) Prove that if p
1
/
w
1
≥
p
2
/
w
2
≥
....
≥
p
n
/
w
n
,
, then FractionalGreedyKnapsackalgorithm generates an optimal solution to the given instance of the fractionalKnapsack problem. [7+8]
4

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...Sign Now!

We are very appreciated for your Prompt Action!

x