Design and Analysis of Algorithms-Practice Questions

MCS-031

Question 1: Write a context free grammar to generate palindromes of even length Over alphabet Σ = {a, b}.

Question 2: Write the finite automata corresponding to the regular expression        (a + b)*ab

Question 3: Derive the principle of optimality for multiplication of matrix chain.

Question 4: Compute the optimal number of scalar multiplications required to multiply the following matrices

 A1 of order 30 X 35 ; A2 of order 35 X 15 ; A3 of order 15 X 5

Question 5: Explain the Chomsky’s Classification of grammars.

Question 6: What is an ambiguous grammar? How do you prove that a given grammar is ambiguous?     Explain with an example.

Question 7: If L1 and L2 are context free languages then, prove that L1 U L2 is a context free language.

Question 8: Define Pushdown Automata

.

Question 9: Explain Decidable and Undecidable Problems. Give example for each.

Question 10: Construct a Turing machine that copies a given string over {a, b}.Also find a computation of TM for the string ‘aab’.

Question 11: Explain the importance of asymptotic analysis for running time of an algorithm.

Question 12: Differentiate between NP-Complete and NP-Hand problems.

Question 13: Find the asymptotic tight bound for

T(n) = 2T (𝑛4) + √𝑛 , with T(1) = 1.

Question 14: Write Quick Sort Algorithm. Prove that worst case for Quick Sort is worst case for Bubble Sort. Analyze the average case running time of Quick Sort Algorithm. Sort the following sequence of numbers, Using Quick Sort: 15, 10, 13, 9, 12, 7 Find the number of Comparisons Copy/Assignment Operations required by the Algorithm in sorting the list.

Question 18: Give a Greedy solution for the change making problem, to the make payment of amount 15597 considering the denominations

{1000, 500, 100, 50, 20, 10, 5, 2, 1 }.

Question 15: Compare the Dynamic programming technique and Greedy technique for solving problems given below

Consider an array A = {3, 14, 27, 31, 39, 42, 55, 70, 74, 81, 85, 93, 98}.

(i) What is the largest number of comparisons made by binary search for any key in array A?

(ii) Find the average number of comparisons made by binary search for a successful search in array A.

(iii)Find the average number of comparisons made by binary search for an unsuccessful search in array A.

Question 16: Write Short Note on Divide and Conquer Techniques. Give suitable example for it. Discuss the Tournament sort algorithm and determine its Recursive and Iterative expression, is Divide and Conquer Technique applicable to Tournament Sort, if Yes Discuss how if No discuss why?