Unit 4 - Previous Questions

Space and Time Tradeoffs

Sorting by Counting

1. Design an algorithm for Sorting by Counting. Trace the algorithm with an example.

2. Given the set {62, 31, 84, 96, 19, 47}, sort the list using the Counting Sort algorithm.

3. Explain the algorithm for Sorting by Distribution Counting.

4. Assuming the set of possible values is {a, b, c, d}, sort the list b, c, d, c, b, a, a, b alphabetically using Distribution Counting algorithm.

5. Develop the algorithm for sorting using Distribution Counting and sort the list 13, 11, 12, 13, 12, 12.

6. Write an algorithm for Distribution Counting and apply it to sort the list 7, 6, 7, 8, 8, 7. Also, find the time complexity.

Hashing – Open Hashing, Closed Hashing

1. Define Hashing. Explain the two mechanisms to resolve collisions in Closed Hashing.

2. What is hashing? Explain two collision resolution techniques with examples and give their mathematical analysis.

3. For the input {30, 20, 56, 75, 31, 19}, construct the Open Hash Table using the hash function h(k) = k mod 11. Find the largest number of key comparisons in a successful search.

4. For the inputs {apple, lemon, and, kiwi, are, grapes} and the hash function h(k) = k mod 13, construct: Open Hash Table and Closed Hash Table.

Dynamic Programming

1. Develop Warshall’s Algorithm to find the transitive closure of a matrix. Apply it to a given directed graph. (2024 Sep, Fig 2)

2. Explain Warshall’s Algorithm. Apply it to compute the transitive closure of the following directed graph. (2023 Sep, Fig 6)

3. Write Floyd’s Algorithm. Apply it to find the distance matrix of the given graph. (2021 Feb, Fig 18)

4. In a star topology with 5 nodes, packets must be transmitted between all pairs. Using a given graph, find the shortest routes using Floyd’s Algorithm. (2020 Sep, Fig 21)

Greedy Technique

Kruskal’s Algorithm

1. Define a Spanning Tree.

2. Write Kruskal’s Algorithm for constructing a Minimum Spanning Tree (MST).

3. Trace Kruskal’s Algorithm for the given graph and construct the MST. (2022 Sep, Fig 11)

4. Apply Kruskal’s Algorithm to a graph and find the MST. (2021 Feb, Fig 17)

5. Apply Kruskal’s Algorithm to a given graph and state its time complexity. (2020 Sep, Fig 22)

Dijkstra’s Algorithm

1. Apply Dijkstra’s Algorithm to find the shortest path from vertex B to all other vertices in the graph. List all shortest paths. (2024 Sep, Fig 1)

2. Write Dijkstra’s Algorithm and apply it to find the shortest paths from node A to all other nodes. (2022 Sep, Fig 10)

3. Apply Dijkstra’s Algorithm from vertex B to all other vertices and list all shortest paths. (2021 Sep, Fig 15)

Huffman Trees

1. Describe Huffman’s Algorithm. Construct a Huffman Tree and obtain the Huffman codes for the following data:

Character	A	B	C	D	E
Probability	0.25	0.15	0.20	0.10	0.30

2. Construct a Huffman Tree for the following data and encode the text DAB-AC:

Character	A	B	C	D	-
Probability	0.4	0.1	0.2	0.15	0.15