JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech II Year DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (April/May - 2023 - R13)
Note: i) Question paper consists of Part A, Part B. ii) Part A is compulsory, which carries 25 marks. In Part A, Answer all questions. iii) In Part B, Answer any one question from each unit. Each question carries 10 marks and may have a, b as sub questions.
Part A
What are the properties of an algorithm?
Answer
An algorithm must satisfy the following five essential properties:
- Input: Zero or more quantities are externally supplied to the algorithm.
- Output: At least one quantity is produced as a result.
- Definiteness: Each instruction must be clear, unambiguous, and precise.
- Finiteness: The algorithm must terminate after a finite number of steps for all cases.
- Effectiveness: Every instruction must be basic enough to be carried out, in principle, by a person using only paper and pencil within a finite amount of time.
Write simple union algorithm.
Answer
The simple union algorithm, often used in Disjoint Set Union (DSU) data structures, merges two disjoint sets by making the root of one tree a child of the root of the other. Given two elements i and j, the algorithm first finds their respective roots using a find operation and then updates the parent pointer of one root to point to the other.
root_i = Find(i)
root_j = Find(j)
if root_i ≠ root_j:
parent[root_i] = root_j
This basic approach results in a tree structure where the depth can grow up to O(n) in the worst case, as it does not employ path compression or union-by-rank optimizations.
Explain greedy method.
Answer
Sign in to view the complete answer paper.
Define spanning tree.
Answer
Sign in to view the complete answer paper.
Write the applications of Dynamic programming.
Answer
Sign in to view the complete answer paper.
What is meant by reliability design?
Answer
Sign in to view the complete answer paper.
Give an example of m-coloring problem.
Answer
Sign in to view the complete answer paper.
Write the principles of FIFO branch and bound.
Answer
Sign in to view the complete answer paper.
State the Chromatic number decision problem.
Answer
Sign in to view the complete answer paper.
What is meant by Halting problem?
Answer
Sign in to view the complete answer paper.
Part B
Develop an algorithm for quick sort.
Answer
Sign in to view the complete answer paper.
Discuss about space complexity in detail with examples.
Answer
Sign in to view the complete answer paper.
Explain the binary search algorithm with an example.
Answer
Sign in to view the complete answer paper.
Explain about the bioconnected components with an example.
Answer
Sign in to view the complete answer paper.
Write a detailed note on greedy knapsack.
Answer
Sign in to view the complete answer paper.
Explain the Prim’s algorithm with an example.
Answer
Sign in to view the complete answer paper.
Develop Greedy algorithm to generate shortest path.
Answer
Sign in to view the complete answer paper.
Explain the Krushkal’s algorithm with an example.
Answer
Sign in to view the complete answer paper.
Explain about the optimal binary search tree.
Answer
Sign in to view the complete answer paper.
Write an algorithm for multistage graph corresponding to forward approach.
Answer
Sign in to view the complete answer paper.
Explain the Travelling salesman problem.
Answer
Sign in to view the complete answer paper.
Differentiate between Greedy method and Dynamic programming.
Answer
Sign in to view the complete answer paper.
Explain in detail about back tracking.
Answer
Sign in to view the complete answer paper.
Describe the sum of subsets problem.
Answer
Sign in to view the complete answer paper.
Explain Hamiltonian cycle using backtracking.
Answer
Sign in to view the complete answer paper.
Illustrate the properties of LC-search.
Answer
Sign in to view the complete answer paper.
Explain the classes of P and NP.
Answer
Sign in to view the complete answer paper.
Write a non deterministic sorting algorithm and also compute the time complexity of the same.
Answer
Sign in to view the complete answer paper.
Explain the strategy to prove that a problem is NP hard.
Answer
Sign in to view the complete answer paper.
Write a non-deterministic Knapsack algorithm.
Answer
Sign in to view the complete answer paper.