JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech II DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (December - 2017 - R13)
Note: This question paper contains two parts A and B. Part A is compulsory which carries 25 marks. Answer all questions in Part A. Part B consists of 5 Units. Answer any one full question from each unit.
PART A
Write about Divide and conquer general method.
Answer
Divide and conquer is an algorithmic paradigm that breaks a problem into smaller sub-problems of the same type, solves them recursively, and then combines their solutions to solve the original problem. It follows three steps: Divide the problem into sub-problems, Conquer the sub-problems by solving them recursively, and Combine the solutions to form the final result.
Define any three asymptotic notations.
Answer
The three common asymptotic notations are:
- Big-O Notation (O): Represents the upper bound of an algorithm's running time, providing the worst-case complexity.
- Omega Notation (Ω): Represents the lower bound of an algorithm's running time, providing the best-case complexity.
- Theta Notation (Θ): Represents the tight bound of an algorithm's running time, where the function is bounded both above and below by the same growth rate.
List the applications of Greed method.
Answer
Sign in to view the complete answer paper.
Give an example for single source shortest Path problem.
Answer
Sign in to view the complete answer paper.
Give the general method for Dynamic programming.
Answer
Sign in to view the complete answer paper.
Explain about line and dead node.
Answer
Sign in to view the complete answer paper.
Explain the variable method in sum of subsets.
Answer
Sign in to view the complete answer paper.
State the Graph coloring problem with an example.
Answer
Sign in to view the complete answer paper.
Give an example for NP-Hard Problem.
Answer
Sign in to view the complete answer paper.
Differentiate Deterministic algorithms and non-deterministic algorithms.
Answer
Sign in to view the complete answer paper.
PART B
Define Space Complexity. Compute space complexity for an algorithm to find factorial of a given number.
Answer
Sign in to view the complete answer paper.
Illustrate the methods to find the connected components in a graph.
Answer
Sign in to view the complete answer paper.
Explain how divide and conquer method is used to implement Merge sort technique with its Time complexity.
Answer
Sign in to view the complete answer paper.
Write an algorithm for Quick sort.
Answer
Sign in to view the complete answer paper.
Write Kruskal’s Algorithm.
Answer
Sign in to view the complete answer paper.
Generate the MCST for the graph given in Figure 1 by applying Kruskal’s algorithm.
Answer
Sign in to view the complete answer paper.
Discuss the Job sequencing with deadlines problem.
Answer
Sign in to view the complete answer paper.
Illustrate 0/1 Knapsack problem with Greed approach.
Answer
Sign in to view the complete answer paper.
Explain Multi stage graph problem.
Answer
Sign in to view the complete answer paper.
Explain the reliability design problem.
Answer
Sign in to view the complete answer paper.
Explain all pairs shortest path problem with the graph given in figure 2.
Answer
Sign in to view the complete answer paper.
Write an algorithm of Optimal Binary Search Trees.
Answer
Sign in to view the complete answer paper.
Explain 4-Queen’s problem.
Answer
Sign in to view the complete answer paper.
Discuss LC branch and bound solution for 0/1 Knapsack problem.
Answer
Sign in to view the complete answer paper.
Illustrate the Hamilton cycles problem with backtracking method.
Answer
Sign in to view the complete answer paper.
Explain travelling sales person problem applying Branch and bound method.
Answer
Sign in to view the complete answer paper.
What is NP-Complete class? Give any two examples.
Answer
Sign in to view the complete answer paper.
Briefly explain Cooks-theorem.
Answer
Sign in to view the complete answer paper.
Compare NP-Hard and NP-Complete classes.
Answer
Sign in to view the complete answer paper.
Give any two examples for non-deterministic algorithms.
Answer
Sign in to view the complete answer paper.