JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech IV ADVANCED ALGORITHMS Previous Question Paper (July - 2023 - 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
Explain the best case analysis of heap sort.
Answer
The best case for heap sort occurs when all elements in the input array are identical. In this scenario, building the heap takes O(n) time, and the subsequent extraction of elements involves heapifying, resulting in a total time complexity of O(n log n).
Define Principle of optimality.
Answer
The Principle of Optimality states that an optimal sequence of decisions has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision. This principle is the foundation of dynamic programming.
Write the general method of Greedy Approach.
Answer
Sign in to view the complete answer paper.
What is the need of Topological Sorting?
Answer
Sign in to view the complete answer paper.
Define Zero-one principle.
Answer
Sign in to view the complete answer paper.
How can you solve systems of linear equations by substitution?
Answer
Sign in to view the complete answer paper.
Define pattern in string.
Answer
Sign in to view the complete answer paper.
Write the steps of the Naive String Matching Algorithm.
Answer
Sign in to view the complete answer paper.
Define the word “Polynomial time”.
Answer
Sign in to view the complete answer paper.
Why the NP-complete problems are significant?
Answer
Sign in to view the complete answer paper.
Part B
Explain the worst case analysis of quick sort with example.
Answer
Sign in to view the complete answer paper.
Write the role of Algorithms in computing.
Answer
Sign in to view the complete answer paper.
What is min heap? Explain heap sort strategy with example.
Answer
Sign in to view the complete answer paper.
Explain the concept of chain matrix multiplication using dynamic programming.
Answer
Sign in to view the complete answer paper.
Apply a variable-length Huffman coding strategy on this frequency character count table.
Answer
Sign in to view the complete answer paper.
Write the minimum cost spanning tree prim’s algorithm.
Answer
Sign in to view the complete answer paper.
Find the Minimum cost spanning tree using Kruskal’s algorithm for the given graph.
Answer
Sign in to view the complete answer paper.
Write the advantages of Maximum Flow algorithm.
Answer
Sign in to view the complete answer paper.
Evaluate the time complexity of Strassen's Matrix Multiplication.
Answer
Sign in to view the complete answer paper.
Explain the concept of Bitonic Sorting Network.
Answer
Sign in to view the complete answer paper.
Write the application area of Sorting Network.
Answer
Sign in to view the complete answer paper.
How to find the Inverse of a 3 × 3 Matrix?
Answer
Sign in to view the complete answer paper.
Explain the major steps in Knuth-Morris-Pratt Algorithm.
Answer
Sign in to view the complete answer paper.
Compare and contrast deterministic and non deterministic finite automata.
Answer
Sign in to view the complete answer paper.
Write the brute force algorithm for string pattern matching.
Answer
Sign in to view the complete answer paper.
How many spurious hits does the Rabin-Karp matcher encounters in Text T = 31415926535......., for string matching, working module q = 11.
Answer
Sign in to view the complete answer paper.
What is Travelling Sales person problem? Explain with neat sketch.
Answer
Sign in to view the complete answer paper.
Explain P, NP and NP-Hard 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.
What are approximation algorithms? Explain.
Answer
Sign in to view the complete answer paper.