JNTU
JNTU B.Tech III DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (November/December - 2018 - R16)
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. Each question carries 10 marks and may have a, b, c as sub questions.
Part A
Write an algorithm to find the number of digits in the binary representation of a positive decimal integer.
Answer
To find the number of digits in the binary representation of a positive decimal integer n:
- Initialize count = 0.
- While n > 0:
- Set n = floor(n / 2).
- Increment count by 1.
- Return count.
How can we measure an algorithm’s running time?
Answer
An algorithm's running time is measured using two primary methods:
- Empirical Analysis: Running the algorithm on a computer for various input sizes and measuring the actual execution time using a clock or timer.
- Theoretical Analysis: Counting the number of primitive operations (like assignments, comparisons, or arithmetic) as a function of input size n, typically expressed using Asymptotic Notations like Big-O, Omega, and Theta.
What is a set? List the operations that can be performed on it.
Answer
Sign in to view the complete answer paper.
Give brief note on graph coloring.
Answer
Sign in to view the complete answer paper.
State the Job – Sequencing Deadline Problem.
Answer
Sign in to view the complete answer paper.
Find an optimal solution to the knapsack instance n=4 objects and the capacity of knapsack m=15, profits (10, 5, 7, 11) and weight are (3, 4, 3, 5).
Answer
Sign in to view the complete answer paper.
What is Travelling Sales Man Problem?
Answer
Sign in to view the complete answer paper.
Give the statement of Reliability design problem.
Answer
Sign in to view the complete answer paper.
State the methodology of Branch and Bound.
Answer
Sign in to view the complete answer paper.
Define Bounding Function? Give the statement of 0/1 Knapsack FIFO BB.
Answer
Sign in to view the complete answer paper.
Part B
Explain Recursive Binary search algorithm with suitable examples.
Answer
Sign in to view the complete answer paper.
Distinguish between Merge sort and quick sort.
Answer
Sign in to view the complete answer paper.
What is stable sorting method? Is Merge sort a stable sorting method? Justify your answer.
Answer
Sign in to view the complete answer paper.
Explain partition exchange sort algorithm and trace this algorithm for n =8 elements: 24, 12, 35, 23, 45, 34, 20, 48.
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.
Give the solution to the 8-queens problem using backtracking.
Answer
Sign in to view the complete answer paper.
What is Minimum cost spanning tree? Explain an algorithm for generating minimum cost Spanning tree and list some applications of it.
Answer
Sign in to view the complete answer paper.
Explain the greedy technique for solving the Job Sequencing problem.
Answer
Sign in to view the complete answer paper.
Write with an example of Prim’s algorithm.
Answer
Sign in to view the complete answer paper.
Discuss the time and space complexity of Dynamic Programming traveling sales person algorithm.
Answer
Sign in to view the complete answer paper.
Write an algorithm of matrix chain multiplication.
Answer
Sign in to view the complete answer paper.
With the help of suitable example explain the all pairs shortest path problem.
Answer
Sign in to view the complete answer paper.
Give the 0/1 Knapsack LCBB algorithm.
Answer
Sign in to view the complete answer paper.
Differentiate between deterministic and non deterministic algorithm.
Answer
Sign in to view the complete answer paper.
Draw the portion of state space tree generated by LCBB for the 0/1 Knapsack instance: n = 5, (p1, p2, ..., p5) = (10, 15, 6, 8, 4), (w1, w2, ..., w5) = (4, 6, 3, 4, 2) and m=12. And also find an optimal solution of the same.
Answer
Sign in to view the complete answer paper.