14. Consider the five-symbol alphabet {A, B, C, D, _} with the following occurrence frequencies in a text made up of these symbols: Answer: Hence, DAD is encoded as 011101,…
11. Explain Dijkstra’s Algorithm with example Answer: Example:
8. Apply Prim’s algorithm and Kruskal’s algorithm to find the minimum cost-spanning tree in the graph below. Answer: Prim’s algorithm: Kruskal’s algorithm:
5. Design Horspools algorithm for string matching. Apply Horspools algorithm to find the pattern BARBER in the text: JIM_SAW_ME_IN_A_BARBERSHOP Answer: Horspool’s algorithm is an efficient string matching algorithm that improves…
4. Explain Heapsort with example Answer: Two Stages: Stage 1 (Build Heap): Construct a heap from the input array. Time: O(n) Stage 2 (Sort): Delete the maximum (root) n−1 times…
3. Explain Heap, Bottom-up Heap and Top-down heap with example. Answer: A heap is a binary tree that satisfies two main conditions: Properties of Heaps Heap Property in Array Form:…
2. Define 2-3 tree. Give the worst-case efficiency of operations on 2-3 tree, build 2-3 tree for the list of keys 9, 5, 8, 3, 2, 4, 7by indicating each…
1) Define AVL Trees. Explain its four rotation types. Explain AVL tree with an example. Give worst case efficiency of operations on aviary construct an avail tree of the list…
9) Explain Strassen’s matrix multiplication and derive its time complexity Answer:Strassen’s Matrix Multiplication Strassen’s Matrix Multiplication is a divide-and-conquer algorithm introduced by Volker Strassen in 1969, which improves the efficiency…
