Jawaharlal Nehru Technological University Hyderabad
Jawaharlal Nehru Technological University Hyderabad B.Tech IV ADVANCED ALGORITHMS Previous Question Paper (January/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
Write down the role of algorithms in computing.
Answer
Algorithms serve as the fundamental building blocks of computing by providing a precise, step-by-step sequence of instructions to solve computational problems. They enable the transformation of input data into desired output efficiently, ensuring reliability, scalability, and optimal resource utilization in software systems.
State and explain optimal binary search tree.
Answer
An Optimal Binary Search Tree (OBST) is a binary search tree where the keys are arranged such that the total expected cost of searching for all keys is minimized. Given a set of keys with associated search probabilities, the tree structure is built using dynamic programming to ensure that frequently accessed keys are placed closer to the root, thereby reducing the average search time.
Define greedy algorithm?
Answer
Sign in to view the complete answer paper.
Discuss maximum flow algorithm with an example.
Answer
Sign in to view the complete answer paper.
Define sorting network.
Answer
Sign in to view the complete answer paper.
Explain bio tonic sorting network.
Answer
Sign in to view the complete answer paper.
What is string matching?
Answer
Sign in to view the complete answer paper.
Mention the applications of string-matching algorithms.
Answer
Sign in to view the complete answer paper.
What is vertex cover problem?
Answer
Sign in to view the complete answer paper.
State and explain polynomial time verification.
Answer
Sign in to view the complete answer paper.
Part B
Consider the following recurrence
Answer
Sign in to view the complete answer paper.
Given two sequences of characters, P=<MLNOM> Q= <MNOM> Obtain the longest common subsequence.
Answer
Sign in to view the complete answer paper.
What is an optimal Huffman code for the following set of frequencies based on first 8 Fibonacci numbers: 1, 1, 2, 3, 5, 8, 13, 21
Answer
Sign in to view the complete answer paper.
Define: “topological sort” of a directed acyclic graph. What is the time complexity of topological sort?
Answer
Sign in to view the complete answer paper.
What is Kruskal’s algorithm? Explain the algorithm with a suitable example.
Answer
Sign in to view the complete answer paper.
Explain in detail about the concept of solving system of linear equations.
Answer
Sign in to view the complete answer paper.
Give an example to explain in detail about the comparison networks in detail.
Answer
Sign in to view the complete answer paper.
What is the basic idea behind Rabin-Karp algorithm? What is expected running time of this algorithm?
Answer
Sign in to view the complete answer paper.
Explain in the algorithm for navie bayes string matching?
Answer
Sign in to view the complete answer paper.
Discuss Knuth Morries Pratt (KMP) algorithm. Compute whether the pattern P = 10100111 is present in the string T = 1001010100111 or not.
Answer
Sign in to view the complete answer paper.
If any NP-complete problem belongs to class P, then is P = NP? Explain.
Answer
Sign in to view the complete answer paper.
Write a brief note on NP-completeness and the classes-P, NP and NPC.
Answer
Sign in to view the complete answer paper.
Define NP complete and NP hard problems with example.
Answer
Sign in to view the complete answer paper.
How are P and NP problems related?
Answer
Sign in to view the complete answer paper.