nielit.gov.in : C Level Course Advanced Algorithms Paper 2017
Name of the Organisation : National Institute of Electronics & Information Technology
Examination : C Level Course
Document Type : Sample Question Paper
Year : 2017
Name of the Subject : Advanced Algorithms
Website : http://beta.nielit.gov.in/content/january-2017
Download Sample Question Paper : https://www.pdfquestion.in/uploads/13079-Algorithm.pdf
C Level Course Advanced Algorithms Paper 2017
Time: 3 Hours
Total Marks: 100
Note :
1. Answer question 1 and any FOUR from questions 2 to 7.
2. Parts of the same question should be answered together and in the same sequence.
Related : NIELIT C Level Course Data Warehousing And Data Mining Paper 2017 : www.pdfquestion.in/13077.html
1. a) Discuss the types of graph for which you can apply (i) Kruskal’s algorithm and (ii) Prim’s algorithm to compute the MST.
b) Derive the recurrence equation for Quick sort under (i) best case and (ii) worst case.
c) Explain topological sort with an example. How it is different than DFS (Depth first search)?
d) Prefix function computation is one of the involved steps in Knuth-Morris-Pratt algorithm for string matching. Apply this prefix function to compute the complete prefix function for the pattern “ababaca”.
e) Differentiate between Radix sort and Bucket sort.
f) What is Amortized analysis? Briefly discuss Aggregate method for performing Amortized analysis.
g) Briefly discuss Quadratic residues. Give the entire set of quadratic residues and nonresidues (mod 10). (7×4)
2. a) A sorted array is circularly shifted k times, where k is not known to you. As an example, consider a sorted array as {3, 4, 5, 6, 7, 8} and after circularly shifting it 2 times (here k is 2), the resulting array is {7, 8, 3, 4, 5, 6}. Use the concept of binary search, modify it (if needed) and propose an efficient algorithm to find the minimum element in circularly shifted (k times) sorted array, if k is not known.
b) You are given with two sorted arrays, arr1 and arr2, each with n elements, i.e. totally 2n elements. Propose an efficient algorithm to find the median of the array1 obtained after merging he above 2 arrays (i.e. arr1 and arr2 of total length 2n). (8+10)
3. a) Coin change is a well known problem where, unlimited coins of denominations D1, D2, D3 etc. are given and it is desired to use minimum number of coins to change the amount X. Propose Dynamic Programming based algorithm to identify minimum number of coins to change given amount and use this algorithm to identify minimum number of coins needed to change Rs. 14 where you are given unlimited coins of following denominations: 1, 4, and 6.
b) Briefly discuss Huffman Coding. Write the steps to build Huffman Tree. (10+8)
4. a) Discuss the Boyer–Moore string search algorithm.
b) Solve the following recurrence :
T (n) = 1 + T (n – 1), if n > 1
= 1 , if n = 1
c) Briefly discuss NP completeness. Give the list of some of the problems, which are NP complete. (8+5+5)
5. a) Discuss strongly connected components and briefly explain the steps of Kosaraju’s algorithm to find the strongly connected components of a directed graph.
b) A complete, undirected, and weighted graph is given in Fig. 1, which satisfies the rules of triangle inequality. Briefly discuss the steps of 2-Approximation algorithm for travelling salesman problem (TSP) and apply it for the graph given in Fig. 1 to identify the cost of the tour, if starting city of the tour is given as vertex “B”. Show that the obtained tour cost may not be the optimal tour, but it will never exceed than twice of the optimal tour cost.
6. a) What simple property of the undirected graph corresponds exactly to the existence of Eulerian circuits? Explain clearly how to compute an Eulerian circuit in such graphs. Is it possible to find out Eulerian circuit in the graph, G given in Fig. 1? If yes, then find the Eulerian circuit.
b) Briefly discuss the key idea involved in Shell sort and apply Shell sort to sort following sequence of elements: {35, 33, 42, 10, 14, 19, 27, 44}. While sorting using Shell sort, consider first the interval of 4, then 2, and finally 1. (8+10)
7. a) Apply Dijkstra’s algorithm to find out shortest distances from vertex “A” to all other vertices in the graph of Fig. 2.
b) Write Floyd Warshall algorithm for all pair shortest path in an undirected weighted graph. (9+9)