My Profile
Active Members
TodayLast 7 Days
more...
Awards & Gifts
Online Exams
Fresher Jobs
Our fresher job section is exclusively for fresh graduates! Find jobs for freshers in major Indian
cities including Bangalore, Chennai, Hyderabad, Pune or Kochi
Resources
Find educational articles, blogs, discussion threads and other resources.
Colleges
Find details about any college in India or search for courses.
Advertisements
|
Download Model question papers & previous years question papers
|
Posted By: Sra1 Member Level: Diamond Posted Date: 27 May 2008
|
2007 Jawaharlal Nehru Technological University B.Tech Computer science and engineering DESIGN AND ANALYSIS OF ALGORITHMS (Supplimentary Examinations, Aug/Sep 2007) Question paper
|
|
|
Set No 1
----------------
Time: 3 hours Max Marks: 80
Answer any FIVE Questions
All Questions carry equal marks
1. (a) Explain the asymptotic notations used in algorithm analysis.
(b) Prove that f(n)=0(h(n)) where f(n)=0(g(n)) and g(n)=0(h(n)). [10+6]
2. (a) List some of the relative advantages and disadvantages of the partition algorithm
(b) Write the Quicksort algorithm? Analize the time complexity in worst case. [6+10]
3. (a) How many comparisons of edge weights will be done by the minimum spanning tree algorithm, in total, if the input is a complete undirected graph with n vertices and vi is the start vertex.
(b) Design a linear-time algorithm for solving the single source shortest path algo-
rithm for directed a cyclic graphs represented by their adjacency linked lists. [6+10]
4. (a) Solve the following 0/1 Knapsack problem using dynamic programming
m=6, n=3, (w1,w2,w3)=(2,3,3), (p1, p2, p3)=(1,2,4)
(b) Write an algorithm of all pairs shortest path problem. [8+8]
5. (a) Write a pseudocode for finding the strongly connected components of directed graph. Also analyze its time complexity.
(b) Explain the Inorder traversal of a tree with an example. [8+8]
6. (a) Describe graph coloring problem and its time complexity.
(b) Write an algorithm of 8-queens problem using backtracking. [8+8]
7. (a) What is Bounding? Explain how these bound are useful in Branch and Bound methods.
(b) Describe the TSP in Branch and Bound. [8+8]
8. (a) Explain about cook’s theorem.
(b) Explain the strategy to prove that a problem is NP hard. [8+8]
Return to question paper search
|
|
|
Submit Previous Years University Question Papers and make money from adsense revenue sharing program
Are you preparing for a university examination? Download model question papers
and practise before you write the exam.
|
|