Q1. a) Develop an efficient algorithm to find a list of all the prime numbers up to anumber n (say 100).
b) Explain the following types of problems in Computer Science with the help of an example problem for each:
i) Searching
ii) String Processing
iii) Geometric Problems
iv) Numerical Problems
Q2. a) Using induction prove that, for all positive integers n,
b) What is the purpose of asymptotic analysis? What are the drawbacks of asymptotic analysis? Explain the Big-O notation with the help of an example.
Q3. a) Evaluate the polynomial p(x)= 5x 5+4x 4 -3x 3 -2x2+9x+11 at x=3 using Horner’s rule. Analyse the computation using Horner’s rule against the Brute force method of polynomial evaluation.
b) Write the linear search algorithm and discuss its best case, worst case and average case time complexity. Show the best case, worst case and the average case of linear search in the following data: 13, 15, 2, 6, 14, 10, 8, 7, 3, 5, 19, 4, 17.
Q4. a) Find an optimal solution for the knapsack instance n=7 and maximum capacity (W) =15,
(p1,p2,…,p6)=(4,5,10,7,6,8, 9)
(w1,w2,…, w6)=(1,2,3,6,2,4, 5)
b) Make an optimal Huffman tree and design the Huffman code for the following set of frequencies:a:7, e:6, s:20, d:2, f:1, g:3, h:4, t:7.
Q5. a) Write and explain the recursive binary search algorithm. Use this algorithm for searching an element in a sorted array of 7 elements.
b) Analyse the Quick sort algorithm using Master Method. Also draw the relevant recursion tree.
c) Write the algorithm for the divide and conquer strategy for Matrix multiplication. Also, analyse this algorithm.
Q6. a) Write the adjacency list and draw ADJACENCY MATRIX for the graph given below.
b) Write and explain the algorithm of Topological sorting. How can you compute time complexity for topological sorting?
Q7. a) Explain the working of Prim’s algorithm for finding the minimum cost spanning tree with the help of an example. Also find the time complexity of Prim’s algorithm.
b) Explain the working of Bellman-Ford algorithm for finding the shortest path from a single source to all destinations with the help of an example. Also find the time complexity of this algorithm.
Q8. a) Explain the process of creating a optimal binary search with the help of an example.
b) Find an optimal parenthesizing of a matrix-chain product who sesequence of dimensions is as follows:
Q9. a) Using the Rabin Karp algorithm, find the pattern string in the given text. Pattern: “ten”, Text: “attainthtenbetan”. Write all the steps involved.
b) Differentiate between Knuth Morris Pratt and Naïve String matching Algorithm
Q10. Differentiate between the following with the help of an example of each:
(i) Optimization and Decision Problems
(ii) P and NP problems
Q11. What are NP Hard and NP complete problems? Explain any one problem of each type.
Q12 Explain backtracking; and Branch and Bound techniques with the help of an example each.
Q1. a) What are the desirable characteristics of an algorithm? Find the GCD of p = 144 and q = 55 using Euclid’s algorithm.
b) Differentiate between Greedy Technique and Dynamic Programming approach of problem solving. Name few problems which are solved using these techniques.
Q2. a) Prove that, for all positive integers n, 1 + 2 + 4 + ⋯ + 2n = 2n+1 − 1.
b) What are asymptotic notations? Explain the significance of Big- O, Omega and theta notations with suitable example.
Q3. a) Evaluate p(x)= 3x4 +2x3 -5x+7 at x=2 using Horne’s rule. Show step wise iterations.
b) Sort the given sequence of numbers using Bubble sort. Write all the steps involved. 13, 15, 2, 6, 14, 10, 8, 7, 3, 5, 19, 4.
Q4. a) Find an optimal solution for the knapsack instance n=6 and M=13,
(p1, p2,…, p6)=(8, 5, 13, 7, 6, 15)
(w1, w2,…, w6)=(3, 2, 4, 6, 2, 5)
b) Write the Huffman code for the following set of frequencies of given symbols. A:1, B:1, K:2, D:3, F:5, G:8 , H:13, E:21.
Q5. a) Write the steps involved in searching an element in a given array of sorted elements using Binary search algorithm. Assume the searched element if not present in the sequence.
b) Analyse the merge sort algorithm Master Method. Also draw the relevant recursion tree.
c) Explain divide and conquer strategy with an example of Matrix multiplication.
Q6. a) Write the adjacency list and draw adjacency graph for the graph given below.
b) Explain Topological sorting using a suitable example of a graph.
Q7. a) What is a minimum cost spanning tree? Explain the working of Kruskal’s Algorithm with example.
b) While dealing with the negative edge weights, the Dijkstra’s algorithm is not considered best. Explain the alternate suitable algorithm for single source shortest path with an example.
Q8. a) Explain the principle of optimality with respect to binary search.
b) Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is as follows:
Q9. a) Using the Rabin Karp algorithm, find the pattern string in the given text. Pattern: “fed”, Text: “acfeddadfdec”. Write all the steps involved.
b) Differentiate between Knuth Morris Pratt and Rabin Karp Algorithm.
Q10. Differentiate between NP, NP-Hard and NP-Complete problems with suitable example of each.
Q11. Discuss about the techniques to show the NP- Hardness in brief.
Q12 What is a vertex cover problem? Discuss Graham’s algorithm in detail.