Question Bank PDF

Q.1 Q.2 Q. 3 Q. 4 Q. 5 Q. 6 Q. 7 Q. 8 Q. 9 Q.10 Give an example graph for which Bellman Ford algorithm will fail to find shortest path. Q. 11 I an undirected graph with negative edge weights, will kruskal’s algorithm produces MST? Q. 12 Q. 13 Q.14 Q. 15 Q. 16 Q. 17 Q. 18 Q. 19 Q...

Q.1 Q.2 Q. 3 Q. 4 Q. 5 Q. 6 Q. 7 Q. 8 Q. 9 Q.10 Give an example graph for which Bellman Ford algorithm will fail to find shortest path. Q. 11 I an undirected graph with negative edge weights, will kruskal’s algorithm produces MST? Q. 12 Q. 13 Q.14 Q. 15 Q. 16 Q. 17 Q. 18 Q. 19 Q. 20 Q. 21 Discuss advantage of skip list over linked list. Q. 22 Q. 23 How can we solve all pairs shortest path problem with Dijkstra algorithm? Illustrate with a suitable example. Also compute its time complexity. Q. 24 Q. 25 Q. 26 Q. 27 Q. 28 Compare and contrast separate chaining and open addressing as collision resolution strategies. Under what conditions might one be preferred over the other? Write average-case and worst-case time complexities for insertion, deletion, and search operations in both methods. Q. 29 For the pattern P = "abacab", build the failure function step-by-step and explain how the failure function helps in avoiding unnecessary comparisons when searching for this pattern in a larger text. Q. 30 Given a B-tree of order 3 (each node can have a maximum of 3 children and 2 keys), perform a sequence of insertions for the following keys: [10, 20, 5, 6, 12, 30, 7, 17]. Show the tree after each insertion and any node splits that occur. Q.31 discuss the advantage of RANDOMIZED-QUICKSORT over Quicksort algorithm? During the running time of procedure RANDOMIZED-QUICKSORT how many calls are made to the random number generator RANDOM in the worst case? what about the best case? Also write recurrence relation for RANDOMIZED-PARTITION in worst and best cases. Q. 32  How does the Union-Find data structure ensure that it avoids cyclic connections in a graph? What are the time complexities of union and find operations in a naive implementation of Union-Find? 6. Describe a real-world problem where Union-Find can be applied effectively. 11. How does Union-Find solve the problem of detecting cycles in an undirected graph?  12. Implement a Union-Find data structure to determine whether two nodes in a graph belong to the same connected component. 13. How can you use Union-Find to efficiently implement dynamic connectivity in a graph? 14. Explain how Union-Find can be used in social network analysis to determine groups of connected users. Analyze the behavior of the KMP algorithm for the pattern "AAAAA" and text "AAAAAAAAAA". What do you observe? 11. Use the KMP algorithm to determine if a string contains repeated substrings. For example, the string "abab" should return True. Explain how the KMP algorithm can be extended to find all occurrences of a pattern in a text. What happens when there is a mismatch in the KMP algorithm, and how does the LPS array help handle mismatches? Explain how a trie can be used to perform auto-complete functionality. Compare the time complexity of searching in a trie versus searching in a hash table. Given a large dataset of strings, how a trie can efficiently find the most frequent prefix? Discuss the advantages and disadvantages of using an iterator over indexing for accessing elements in a collection. How can a skip list be viewed as an extension of the List ADT? What are its advantages?