November 25, 2011

DESIGN AND ANALYSIS OF ALGORITHMS JNTU previous years question papers

DESIGN AND ANALYSIS OF ALGORITHMS JNTU previous years question papers

Computer Science & Engineering

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

1. (a) Show that f(n)+g(n)=O (n2) where f(n) = 3n2 - n + 4 and g(n)=nlogn+5
(b) Explain how time complexity of an algorithm is computed. [8+8]

2. (a) Suppose a binary tree has leaves l1l2.......lm at depths d1, respectively prove that
2-di 1 and determine when the equality is true.
(b) Write and explain the control abstraction algorithm of divide and conquer.

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 algorithm for directed a cyclic graphs represented by their adjacency linked lists.

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) Explain game tree with an example.
(b) Prove or disprove an undirected graph G=(V,E) is biconnected if and only if for each pair of distinct vertices u and v there are two distinct paths from u to v that have no vertex in common except u and v. [8+8]

6. (a) Write an algorithm of finding all m-colorings of a graph.
(b) Describe the 4-queens problem using backtracking. [8+8]

7. (a) Explain the method of reduction to solve TSP problem using Branch and Bound.
(b) Explain the principles of FIFO Branch and Bound. [8+8]

8. (a) Explain about cook’s theorem.
(b) Explain the strategy to prove that a problem is NP hard.



Post a Comment

Get Syllabus in your Mail


Accenture Admission Notice - 2010 Admission Notification Anna University Anna University Chennai Anna University Question Papers Anna University Trichy Apparel Technology and Management Aptitude Questions Arts and Science Colleges Biomedical Engineering C and CPP Ebooks Calicut University CBSE Question papers Civil Engineering Civil Service Exams Colleges in India Colleges Result Computer Science Engineering Core Jobs CS R2008 CSE CSIR NET EBooks Download ECE EEE EIE Electives Electrical and Electronics Engineering Electronics and communication Electronics and Instrumentation Engineering Engineering Engineering Colleges in Maharashtra Engineering Colleges in TamilNadu Engineering Admissions Engineering Colleges Engineering Colleges in Karnataka Engineering Jobs Engineering Syllabus Entrance Exam Dates Entrance Exam Results Entrance Examination Exam Time Table Experiencer First Year Syllabus Freshers Full Time Jobs Government jobs in india Hardware and Networking Jobs Hotel Management and Catering Technology IGNOU Information Technology INTEVIEW QUESTIONS IT Jobs JNTU Question Papers Jobs in Bangalore Jobs in Chennai Jobs in Coimbatore Jobs in Delhi Jobs in Hyderabad Jobs in India Jobs in Kerala Jobs in Noida Jobs in Tamilnadu Jobs in TATA Karnataka Educations Lab Manuals Mechanical Engineering Medical Colleges Placement Papers Plus 2 Preparation for exams Private Jobs in India Question Papers Question Papers Download Results Announcement Semester 1 Semester 2 Semester 3 Semester 4 Semester 5 Semester 6 Semester 7 Semester 8 Syllabus Syllabus Download Tamil Movie TCS Placement Papers Teaching Jobs TECH MAHINDRA Textile Technology Top colleges University Results UPSC VICEVESVARAYA TECHNOLOGICAL UNIVERSITY waec Walk-in Interview Web Designers



Anna university Engineering Syllabus

Earn Money From Online

Government jobs in india

Admission Notification

Total Pageviews


Privacy Policy use third-party advertising companies to serve ads when you visit our website. These companies may use information (not including your name, address, email address, or telephone number) about your visits to this and other websites in order to provide advertisements about goods and services of interest to you. If you would like more information about this practice and to know your choices about not having this information used by these companies, click here.