Exam Details
| Subject | design and analysis of algorithms | |
| Paper | ||
| Exam / Course | b.tech | |
| Department | ||
| Organization | Institute Of Aeronautical Engineering | |
| Position | ||
| Exam Date | December, 2017 | |
| City, State | telangana, hyderabad |
Question Paper
Hall Ticket No Question Paper Code: AIT001
INSTITUTE OF AERONAUTICAL ENGINEERING
(Autonomous)
B.Tech III Semester End Examinations (Regular) December, 2017
Regulation: IARE R16
DESIGN AND ANALYSIS OF ALGORITHMS
(Common to CSE/IT)
Time: 3 Hours Max Marks: 70
Answer ONE Question from each Unit
All Questions Carry Equal Marks
All parts of the question must be answered in one place only
UNIT I
1. Briefly explain the time complexity and space complexity estimation.
Sort the following elements using Merge Sort. 45,22,88,23,78,46,84,44,21,34.
2. Write and trace the binary search algorithm for searching the element 70 from the list
3,14,27,31,39,42,55,70,74,81,85,93,98. Analyze its worst case time complexity.
ALGORITHM Sum(n)
Input: A nonnegative integer n
S←0
For i ← 1 to n do
S ← S i
Return S
1. What does this algorithm compute?
2. What is basic operation?
How many times the basic operation is executed?
UNIT II
3. Define articulation points and construct a depth first spanning tree for the graph shown in Figure
1 .
Figure 1
Write the algorithm to find the depth first search and breadth first search of a graph.
4. Explain about Weighted Union and Collapsing Find using an example.
Write the algorithm for finding the bicomponents of a graph G.
Page 1 of 3
UNIT III
5. Explain the Job sequencing with deadlines using following example.
N=5 ,profits (d1,d2,..d5) 3).
Write an algorithm for optimal binary search tree.
6. Explain Kruskal's Algorithm to find Minimum cost Spanning Tree using an example.
Write a pseudo code using bottom-up dynamic programming for the knapsack Problem.
UNIT IV
7. What is graph coloring problem? Discuss in detail the m-coloring graph problem.
Explain how backtracking can be used to solve n-queens problem and obtain one solution to
4-queens problem showing the state space tree.
8. Apply backtracking to find Hamiltonian cycle in the following graph shown in Figure 2 and write
the algorithm.
Figure 2
Find the optimal tour of travelling salesman problem for the graph shown in Figure 3 using
branch and bound.
Figure 3
Page 2 of 3
UNIT V
9. State Cook's theorem and explain.
Describe about clique decision problem.
10. Write a brief note on NP NP hard and NP complete
Prove that the circuit Satisfactory problem is NP complete
INSTITUTE OF AERONAUTICAL ENGINEERING
(Autonomous)
B.Tech III Semester End Examinations (Regular) December, 2017
Regulation: IARE R16
DESIGN AND ANALYSIS OF ALGORITHMS
(Common to CSE/IT)
Time: 3 Hours Max Marks: 70
Answer ONE Question from each Unit
All Questions Carry Equal Marks
All parts of the question must be answered in one place only
UNIT I
1. Briefly explain the time complexity and space complexity estimation.
Sort the following elements using Merge Sort. 45,22,88,23,78,46,84,44,21,34.
2. Write and trace the binary search algorithm for searching the element 70 from the list
3,14,27,31,39,42,55,70,74,81,85,93,98. Analyze its worst case time complexity.
ALGORITHM Sum(n)
Input: A nonnegative integer n
S←0
For i ← 1 to n do
S ← S i
Return S
1. What does this algorithm compute?
2. What is basic operation?
How many times the basic operation is executed?
UNIT II
3. Define articulation points and construct a depth first spanning tree for the graph shown in Figure
1 .
Figure 1
Write the algorithm to find the depth first search and breadth first search of a graph.
4. Explain about Weighted Union and Collapsing Find using an example.
Write the algorithm for finding the bicomponents of a graph G.
Page 1 of 3
UNIT III
5. Explain the Job sequencing with deadlines using following example.
N=5 ,profits (d1,d2,..d5) 3).
Write an algorithm for optimal binary search tree.
6. Explain Kruskal's Algorithm to find Minimum cost Spanning Tree using an example.
Write a pseudo code using bottom-up dynamic programming for the knapsack Problem.
UNIT IV
7. What is graph coloring problem? Discuss in detail the m-coloring graph problem.
Explain how backtracking can be used to solve n-queens problem and obtain one solution to
4-queens problem showing the state space tree.
8. Apply backtracking to find Hamiltonian cycle in the following graph shown in Figure 2 and write
the algorithm.
Figure 2
Find the optimal tour of travelling salesman problem for the graph shown in Figure 3 using
branch and bound.
Figure 3
Page 2 of 3
UNIT V
9. State Cook's theorem and explain.
Describe about clique decision problem.
10. Write a brief note on NP NP hard and NP complete
Prove that the circuit Satisfactory problem is NP complete
Other Question Papers
Subjects
- ac machines
- advanced databases
- aircraft materials and production
- aircraft performance
- aircraft propulsion
- aircraft systems and controls
- analog communications
- analysis of aircraft production
- antennas and propagation
- applied physics
- applied thermodynamics
- basic electrical and electronics engineering
- basic electrical engineering
- building materials construction and planning
- business economics and financial analysis
- compiler design
- complex analysis and probability distribution
- computational mathematics and integral calculus
- computer networks
- computer organization
- computer organization and architecture
- computer programming
- concrete technology
- control systems
- data structures
- database management systems
- dc machines and transformers
- design and analysis of algorithms
- design of machine members
- digital and pulse circuits
- digital communications
- digital ic applications using vhdl
- digital logic design
- digital system design
- disaster management
- disaster management and mitigation
- discrete mathematical structures
- dynamics of machinery
- electrical circuits
- electrical measurements and instrumentation
- electrical technology
- electromagnetic field theory
- electromagnetic theory and transmission lines
- electronic circuit analysis
- electronic devices and circuits
- elements of mechanical engineering
- engineering chemistry
- engineering drawing
- engineering geology
- engineering mechanics
- engineering physics
- english
- english for communication
- environmental studies
- finite element methods
- fluid mechanics
- fluid mechanics and hydraulics
- fundamental of electrical and electronics engineering
- fundamental of electrical engineering
- gender sensitivity
- geotechnical engineering
- heat transfer
- high speed aerodynamics
- hydraulics and hydraulic machinery
- image processing
- industrial automation and control
- instrumentation and control systems
- integrated circuits applications
- introduction to aerospace engineering
- kinematics of machinery
- linear algebra and calculus
- linear algebra and ordinary differential equations
- low speed aerodynamics
- machine tools and metrology
- mathematical transform techniques
- mathematical transforms techniques
- mechanics of fluids and hydraulic machines
- mechanics of solids
- mechanism and machine design
- metallurgy and material science
- microprocessor and interfacing
- modern physics
- network analysis
- object oriented analysis and design
- object oriented programming through java
- operating systems
- optimization techniques
- power electronics
- power generation systems
- probability and statistics
- probability theory and stochastic processes
- production technology
- programming for problem solving
- pulse and digital circuits
- reinforced concrete structures design and drawing
- software engineering
- strength of materials - i
- strength of materials - ii
- structural analysis
- surveying
- theory of computation
- theory of structures
- thermal engineering
- thermo dynamics
- thermodynamics
- tool design
- transmission and distribution systems
- unconventional machining processes
- waves and optics
- web technologies