JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B. Tech II Year DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (September/October - 2023 - R15)
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 is time complexity?
Answer
Time complexity is a measure of the amount of time an algorithm takes to run as a function of the length of the input. It is typically expressed using asymptotic notation, such as Big O notation, to describe the upper bound of the growth rate of the algorithm's execution time.
Differentiate between Pseudocode and an algorithm.
Answer
An algorithm is a step-by-step logical procedure or set of rules designed to solve a specific problem, independent of any programming language. Pseudocode is a high-level, informal description of an algorithm that uses structural conventions of programming languages but is intended for human reading rather than machine execution.
Write an algorithm of Union operation.
Answer
Sign in to view the complete answer paper.
What is the importance of Game tree?
Answer
Sign in to view the complete answer paper.
What is feasible solution?
Answer
Sign in to view the complete answer paper.
Write an algorithm of Greedy Knapsack.
Answer
Sign in to view the complete answer paper.
What is state space tree?
Answer
Sign in to view the complete answer paper.
What are the advantages of Backtracking?
Answer
Sign in to view the complete answer paper.
What is Non-Polynomial time algorithm?
Answer
Sign in to view the complete answer paper.
What is decision problem?
Answer
Sign in to view the complete answer paper.
Part B
Derive the time complexity of Strassen’s matrix multiplication.
Answer
Sign in to view the complete answer paper.
Explain about the Amortized complexity.
Answer
Sign in to view the complete answer paper.
Write and explain the algorithm of Merge Sort and also analyze the time complexity of the same.
Answer
Sign in to view the complete answer paper.
Write an algorithm to find the connected components using DFS and also analyze the time complexity of the same.
Answer
Sign in to view the complete answer paper.
Explain about the AND/OR graph with an example.
Answer
Sign in to view the complete answer paper.
Write an algorithm of BFS and also analyze the time complexity of the same.
Answer
Sign in to view the complete answer paper.
Design a three stage system with device types D1, D2, D3. The costs are $30, $15, $20 respectively. The cost of the system is to be no more than $105. The reliability of each device type is 0.9, 0.8 and 0.5 respectively.
Answer
Sign in to view the complete answer paper.
Find the shortest path of the following graph from source to destination by using single source shortest path.
Answer
Sign in to view the complete answer paper.
Write down the differences between prim’s and Krushkal’s algorithm.
Answer
Sign in to view the complete answer paper.
Draw the portion of the state space tree generated by LCBB for the following knapsack instances: n=5, (P1, P2, P3, P4, P5) = (10, 15, 6, 8, 4), (W1, W2, W3, W4, W5) = (4, 6, 3, 4, 2) and m = 12
Answer
Sign in to view the complete answer paper.
Write down the applications of n-Queens problem.
Answer
Sign in to view the complete answer paper.
Explain how to find the Hamiltonian cycle using Backtracking.
Answer
Sign in to view the complete answer paper.
Draw and explain the tree organization of the 4 – Queen Solution state space tree.
Answer
Sign in to view the complete answer paper.
Write a non-deterministic algorithm of Sorting of an elements in an array.
Answer
Sign in to view the complete answer paper.
Explain about the Cook’s theorem.
Answer
Sign in to view the complete answer paper.
Explain the relationship between P, NP, NP-Hard and NP-Complete.
Answer
Sign in to view the complete answer paper.
Write a Non – deterministic algorithm of 0/1Knapsack problem.
Answer
Sign in to view the complete answer paper.