Algorithms and Advanced Data Structures — DU B.Sc. (Hons) Computer Science Previous Year Question Papers

2. This question paper has two sections A and B. 3. Section A carries 30 marks and each question in Section B carries 15 marks. 6. Parts of a question must be attempted together. Q.1 a) Differentiate between the crawling and indexing phases of a search engine's workflow. (3) b) In the VH-tree, what is the maximum number of horizontal pointers that can be traversed consecutively on a path from the root to a leaf? Justify your answer based on the tree's fundamental property. (3) c) Consider a binary counter of 4 bits that starts from 0 and supports only an INCREMENT operation. Using the accounting method of amortized analysis, determine the amortized cost per INCREMENT operation. Assign a credit to each bit flip and explain how these credits are used to pay for expensive operations. (4) (5) e) Give an example of a dataset consisting of 7 elements that results in the worst case for Quick Sort. Using this dataset, Sort the array using Quick Sort (with the last element as the pivot). Sort the same array using Randomized Quick Sort (selecting a random pivot in each partition). Compare the impact of pivot selection on the performance in both cases. (5) f) What is meant by a residual graph Gy for a flow network G with a flow f and what is significance of a backward edge in this residual graph? Explain with the help of an example g) on the following weighted undirected graph. Clearly show every step of addition Write Kruskal's algorithm for finding Minimum Spanning Tree. Apply the same of selected edge to generate MST. Q. 2 a) Explain Independent Set and Vertex-Cover problems. Prove that Independent Set ≤p Vertex-Cover. (7) b) Apply Bellman-Ford algorithm to find the shortest path from a to all other vertices on the following weighted directed graph G. Show the distance progressions of all vertices after each iteration. When does Bellman-Ford algorithm fail? Justify your answer with proper example. Q. 3 a) How the suffix trie of a string S of length n can be used to check if a pattern P of length m is a substring of S in O(m) time? Illustrate with the pattern "NAN" on the suffix trie for "BANANAS". Why is a suffix trie not the preferred data structure for (7) large genomic sequences despite its powerful substring operations? Using Knuth-Morris-Pratt (KMP) algorithm, construct the failure function for P = "ABAABAC" and find the first occurrence of the pattern P in the text string T= "ABABACABABABAABACABAC" clearly illustrating all shifts and comparisons. (8) Compare the Brute Force and KMP algorithms in terms of time complexity. Q.4 a) Considering the set of words: (programmer, programming, progress, project, python, slack, stack, stream, string, structure, algorithm, algebra, alpha} make a standard trie to store these words. By converting it into (7) a compressed trie, show how much space is saved.