JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech III DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (August/September - 2024 - R16)
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
In what way a time complexity differs from space complexity.
Answer
Time complexity measures the amount of computational time an algorithm takes to run as a function of input size, whereas space complexity measures the amount of memory (RAM) space required by an algorithm as a function of the input size.
How can we measure an algorithm’s running time?
Answer
An algorithm's running time is measured by counting the number of primitive operations (such as additions, comparisons, or assignments) executed as a function of input size. This is typically expressed using Asymptotic Notation (Big-O, Omega, or Theta) to describe the growth rate of the execution time as the input size approaches infinity.
What is a set? List the operations that can be performed on it.
Answer
Sign in to view the complete answer paper.
Define spanning tree and minimum spanning tree.
Answer
Sign in to view the complete answer paper.
What is the importance of knapsack algorithm in our daily life?
Answer
Sign in to view the complete answer paper.
What is greedy strategy? Explain.
Answer
Sign in to view the complete answer paper.
What is reliability design?
Answer
Sign in to view the complete answer paper.
What are the applications of dynamic programming?
Answer
Sign in to view the complete answer paper.
What is NP-hard problem?
Answer
Sign in to view the complete answer paper.
What is meant by non-deterministic algorithm?
Answer
Sign in to view the complete answer paper.
Part B
What are the different mathematical notations used for algorithm analysis?
Answer
Sign in to view the complete answer paper.
Distinguish between Merge sort and quick sort. Give suitable examples.
Answer
Sign in to view the complete answer paper.
Explain about Recursive Binary search algorithm with suitable examples.
Answer
Sign in to view the complete answer paper.
Write Randomized algorithm of Quicksort.
Answer
Sign in to view the complete answer paper.
Write and explain the algorithm of Bi connected components with an example.
Answer
Sign in to view the complete answer paper.
Explain about union and find algorithms.
Answer
Sign in to view the complete answer paper.
Discuss about the graph traversal and coloring with an example.
Answer
Sign in to view the complete answer paper.
Write an algorithm to find the strongly connected components in a diagraph.
Answer
Sign in to view the complete answer paper.
State the Job – Sequencing with deadlines problem.
Answer
Sign in to view the complete answer paper.
Find an optimal sequence to the n = 5 Jobs where Profits (P1, P2, P3, P4, P5) = (20, 15, 10, 5, 1) and Deadlines (d1, d2, d3, d4, d5) = (2, 2, 1, 3, 3) are given.
Answer
Sign in to view the complete answer paper.
Write the pseudo code for Dijkstra’s algorithm for single source shortest path problem.
Answer
Sign in to view the complete answer paper.
Write an algorithm of Prim’s minimum cost spanning tree.
Answer
Sign in to view the complete answer paper.
How Matrix – chain Multiplication problem can be solved using dynamic programming? Explain with suitable example.
Answer
Sign in to view the complete answer paper.
Draw an Optimal Binary Search Tree for n=4 identifiers (a1,a2,a3,a4) = ( do, if, read, while) P(1:4)=(3,3,1,1) and Q(0:4)=(2,3,1,1,1).
Answer
Sign in to view the complete answer paper.
Describe the travelling sales person problem.
Answer
Sign in to view the complete answer paper.
Explain Cook’s theorem and its significance.
Answer
Sign in to view the complete answer paper.
Discuss in detail about FIFO Branch and Bound solutions.
Answer
Sign in to view the complete answer paper.
Explain the classes of NP Hard and NP-Complete.
Answer
Sign in to view the complete answer paper.
Show that the Hamiltonian cycle problem on directed graphs is NP-complete.
Answer
Sign in to view the complete answer paper.