JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech III ALGORITHM DESIGN AND ANALYSIS Previous Question Paper (February - 2023 - R18)
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
Define Little oh notation.
Answer
The Little oh notation, denoted as o(g(n)), describes an asymptotic upper bound that is not tight. A function f(n) is said to be o(g(n)) if for any positive constant c > 0, there exists a constant n₀ > 0 such that 0 ≤ f(n) < c · g(n) for all n ≥ n₀.
Write the application area of divide and conquer strategy.
Answer
The divide and conquer strategy is a fundamental algorithmic paradigm used extensively in computer science for solving complex problems by breaking them into smaller, manageable sub-problems. Its primary application areas include:
- Sorting Algorithms: It is the core logic behind efficient sorting techniques such as Merge Sort and Quick Sort, which achieve O(n log n) average time complexity.
- Searching Algorithms: It is used in Binary Search to locate elements in a sorted array by repeatedly dividing the search interval in half, resulting in O(log n) complexity.
- Computational Geometry: It is applied to solve problems like finding the closest pair of points in a plane or constructing convex hulls.
- Matrix Multiplication: Strassen's algorithm utilizes divide and conquer to perform matrix multiplication faster than the standard O(n³) approach.
- Large Integer Multiplication: The Karatsuba algorithm employs this strategy to multiply large numbers more efficiently than the traditional long multiplication method.
What is collapsing find?
Answer
Sign in to view the complete answer paper.
Define Chromatic number. Give one example.
Answer
Sign in to view the complete answer paper.
What is the beauty of dynamic programming?
Answer
Sign in to view the complete answer paper.
How many possible binary trees with n nodes, where n=3, draw them.
Answer
Sign in to view the complete answer paper.
Define spanning tree.
Answer
Sign in to view the complete answer paper.
List the application area of Greedy approach.
Answer
Sign in to view the complete answer paper.
What is E-node? Give an example.
Answer
Sign in to view the complete answer paper.
Compare and contrast deterministic algorithms and non-deterministic algorithms.
Answer
Sign in to view the complete answer paper.
PART - B
Write an Iterative algorithm for binary search. What is its best case analysis?
Answer
Sign in to view the complete answer paper.
Write any five rules to define an algorithm.
Answer
Sign in to view the complete answer paper.
What is an algorithms? List the properties of an algorithm.
Answer
Sign in to view the complete answer paper.
Write the worst case analysis of quick sort with suitable example.
Answer
Sign in to view the complete answer paper.
Write the union and find algorithms.
Answer
Sign in to view the complete answer paper.
Explain the 4-Queens problem.
Answer
Sign in to view the complete answer paper.
Compare and contrast divide and conquer approach with dynamic programming.
Answer
Sign in to view the complete answer paper.
Explain the sum of subset problem.
Answer
Sign in to view the complete answer paper.
Consider n=4 & (q1,q2,q3,q4)=(do, if, int, while) the values for p’s & q’s are given as p(1:4)=(3,3,1,1) & q(0:4)=(2,3,1,1,1). Construct the Optimal Binary Search tree.
Answer
Sign in to view the complete answer paper.
Define backtracking. List the advantages of it.
Answer
Sign in to view the complete answer paper.
Write the general method for dynamic programming.
Answer
Sign in to view the complete answer paper.
Find an Optimal Solution to the knapsack instance n=7, m=15, (P1,P2…..P7)=(10,5,15,7, 6, 18,3) and (W1,W2…..W7)=(2,3,5,7,1,4,1).
Answer
Sign in to view the complete answer paper.
Find the minimum cost spanning tree for the following graph using kruskals algorithm.
Answer
Sign in to view the complete answer paper.
What is the need of Greedy approach?
Answer
Sign in to view the complete answer paper.
Consider the following jobs, deadlines and profits. Use the scheduling with deadline algorithm to maximize the total profit.
Answer
Sign in to view the complete answer paper.
Explain Single source shortest path problem with an illustrative example.
Answer
Sign in to view the complete answer paper.
Define Cook’s theorem and prove it.
Answer
Sign in to view the complete answer paper.
Define NP-Hard problem. Explain it’s time complexity.
Answer
Sign in to view the complete answer paper.
Explain P, NP and NP-Complete classes with suitable examples.
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.