Exam Details
| Subject | design and analysis of algorithms | |
| Paper | ||
| Exam / Course | b.tech | |
| Department | ||
| Organization | Institute Of Aeronautical Engineering | |
| Position | ||
| Exam Date | February, 2018 | |
| City, State | telangana, hyderabad |
Question Paper
Hall Ticket No Question Paper Code: AIT001
INSTITUTE OF AERONAUTICAL ENGINEERING
(Autonomous)
B.Tech III Semester End Examinations (Supplementary) January/February, 2018
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. Define and O asymptotic notations and discuss their significance.
Write the Quick sort algorithm Apply the algorithm to sort the list
2. Explain about the Probabilistic analysis with an example.
Describe Strassen's matrix multiplication and derive the time complexity of it.
UNIT II
3. Explain about FIND operation Using Collapsing Rule.
Write the algorithm to find the depth first search and breadth first search of a graph.
4. Explain UNION and FIND Operations of Disjoint sets with suitable examples and write the
algorithms.
Define biconnected component? Explain how to identify a biconnected component in a given
graph.
UNIT III
5. Write Kruskal's algorithm and determine the minimum cost spanning tree for the graph as shown
in figure 1.
Figure 1
Discuss the difference between greedy approach and dynamic programming with suitable examples.
Page 1 of 2
6. Write Dijkstra's algorithm to find single source shortest path. Apply the same to find the shortest
path from vertex in the following graph as shown in figure 2.
Figure 2
Apply Floyd's algorithm to solve all pair shortest path problem .
Figure 3
UNIT IV
7. Illustrate graph coloring problem and draw the state space tree for n=3 and m=3.
What is backtracking? Illustrate the n queen problem with state space tree.
8. Draw and explain the portion of the state space tree for n-queens problem that is generating
backtracking.
Solve the problem for travelling sale0sperson instance defined by cost adjacency matrix.
BBBBBBBBB@
1 7 3 12 8
3 1 6 14 9
5 8 1 6 18
9 3 5 1 11
18 14 9 8 1
1
CCCCCCCCCA
UNIT V
9. Explain nondeterministic algorithm for sorting.
Define and explain briefly
i. P Problem
ii. NP hard problem
iii. NP complete problem
10. Discuss in detail the different problems in NP-Hard and NP-Complete.
Explain about chromatic number decision problem.
INSTITUTE OF AERONAUTICAL ENGINEERING
(Autonomous)
B.Tech III Semester End Examinations (Supplementary) January/February, 2018
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. Define and O asymptotic notations and discuss their significance.
Write the Quick sort algorithm Apply the algorithm to sort the list
2. Explain about the Probabilistic analysis with an example.
Describe Strassen's matrix multiplication and derive the time complexity of it.
UNIT II
3. Explain about FIND operation Using Collapsing Rule.
Write the algorithm to find the depth first search and breadth first search of a graph.
4. Explain UNION and FIND Operations of Disjoint sets with suitable examples and write the
algorithms.
Define biconnected component? Explain how to identify a biconnected component in a given
graph.
UNIT III
5. Write Kruskal's algorithm and determine the minimum cost spanning tree for the graph as shown
in figure 1.
Figure 1
Discuss the difference between greedy approach and dynamic programming with suitable examples.
Page 1 of 2
6. Write Dijkstra's algorithm to find single source shortest path. Apply the same to find the shortest
path from vertex in the following graph as shown in figure 2.
Figure 2
Apply Floyd's algorithm to solve all pair shortest path problem .
Figure 3
UNIT IV
7. Illustrate graph coloring problem and draw the state space tree for n=3 and m=3.
What is backtracking? Illustrate the n queen problem with state space tree.
8. Draw and explain the portion of the state space tree for n-queens problem that is generating
backtracking.
Solve the problem for travelling sale0sperson instance defined by cost adjacency matrix.
BBBBBBBBB@
1 7 3 12 8
3 1 6 14 9
5 8 1 6 18
9 3 5 1 11
18 14 9 8 1
1
CCCCCCCCCA
UNIT V
9. Explain nondeterministic algorithm for sorting.
Define and explain briefly
i. P Problem
ii. NP hard problem
iii. NP complete problem
10. Discuss in detail the different problems in NP-Hard and NP-Complete.
Explain about chromatic number decision problem.
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