Exam Details
| Subject | design and analysis of algorithms | |
| Paper | ||
| Exam / Course | b.tech | |
| Department | ||
| Organization | Institute Of Aeronautical Engineering | |
| Position | ||
| Exam Date | July, 2018 | |
| City, State | telangana, hyderabad |
Question Paper
Hall Ticket No Question Paper Code: AIT001
INSTITUTE OF AERONAUTICAL ENGINEERING
(Autonomous)
Four Year B.Tech III Semester End Examinations (Supplementary) July, 2018
Regulation: IARE R16
DESIGN AND ANALYSIS OF ALGORITHMS
Time: 3 Hours (Commo to CSE IT) 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 space and time complexity of an algorithm. State the asymptotic notations used in
computing the complexities.
Illustrate the merge sort algorithm by considering the following numbers and
analyze the time complexity of the algorithm.
2. Illustrate the multiplication of two matrices of order 2x2 using Strassen's approach.
Solve the following recurrence relations.
i. x x 5f or n x 0
ii. x 3x f or n x 4
UNIT II
3. Write the algorithm to find the depth first search and breadth first search of a graph.
Construct a depth first spanning tree for the below graph shown in Figure 1.
Figure 1
4. Discuss the tree representation of sets. Write and explain the algorithm for union and find
operation.
Define articulation points and write the biconnected graph for connected graph.
Page 1 of 2
UNIT III
5. With the help of suitable example, explain the Greedy Knapsack?
Find the shortest path between all pairs of nodes in the following graph shown in Figure 2.
Figure 2
6. Write a greedy algorithm for the shortest path problem.
What is the Knapsack problem? Find an optimal solution to Knapsack problem with
and .
UNIT IV
7. Define Hamiltonian cycle's problem. Explain with an example.
Explain FIFO Branch and Bound solution. Illustrate with suitable example.
8. Explain LC Branch and Bound solution with an example.
Define sum of subsets. Solve sum of subsets for W 10, 12, 13, 15, 18}.
UNIT V
9. State Cook's theorem and describe with real time applications.
Describe about clique decision problem. Give suitable example.
10. What is Non-deterministic algorithm for sorting? Give an example.
State and prove that the 3-SAT problem is NP-Complete.
Page 2 of 2
INSTITUTE OF AERONAUTICAL ENGINEERING
(Autonomous)
Four Year B.Tech III Semester End Examinations (Supplementary) July, 2018
Regulation: IARE R16
DESIGN AND ANALYSIS OF ALGORITHMS
Time: 3 Hours (Commo to CSE IT) 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 space and time complexity of an algorithm. State the asymptotic notations used in
computing the complexities.
Illustrate the merge sort algorithm by considering the following numbers and
analyze the time complexity of the algorithm.
2. Illustrate the multiplication of two matrices of order 2x2 using Strassen's approach.
Solve the following recurrence relations.
i. x x 5f or n x 0
ii. x 3x f or n x 4
UNIT II
3. Write the algorithm to find the depth first search and breadth first search of a graph.
Construct a depth first spanning tree for the below graph shown in Figure 1.
Figure 1
4. Discuss the tree representation of sets. Write and explain the algorithm for union and find
operation.
Define articulation points and write the biconnected graph for connected graph.
Page 1 of 2
UNIT III
5. With the help of suitable example, explain the Greedy Knapsack?
Find the shortest path between all pairs of nodes in the following graph shown in Figure 2.
Figure 2
6. Write a greedy algorithm for the shortest path problem.
What is the Knapsack problem? Find an optimal solution to Knapsack problem with
and .
UNIT IV
7. Define Hamiltonian cycle's problem. Explain with an example.
Explain FIFO Branch and Bound solution. Illustrate with suitable example.
8. Explain LC Branch and Bound solution with an example.
Define sum of subsets. Solve sum of subsets for W 10, 12, 13, 15, 18}.
UNIT V
9. State Cook's theorem and describe with real time applications.
Describe about clique decision problem. Give suitable example.
10. What is Non-deterministic algorithm for sorting? Give an example.
State and prove that the 3-SAT problem is NP-Complete.
Page 2 of 2
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