Question 1) Give and describe each step with graph example for the trace of following graph traversal algorithms.
a) Breadth first search
b) Depth first search
Question 2)a) Show the insertion of the keys 5, 28, 19, 15, 20, 33, 12, 17, 10 into a hash table with collisions resolved by chaining. Let the table have 9 slots, and let the hash function be h(k) = k mod 9.
b) For the set of keys {1, 4, 5, 10, 16, 17, 21}, draw binary search trees of height 2, 3, 4, 5, and 6.
Question 3)a) Prove that fractional knapsack problem has the greedy-choice property.
b) What is the optimal Huffman code for the following set of frequencies, based on the first 8 Fibonacci numbers?
a : 1 b : 1 c : 2 d : 3 e : 5 f : 8 g : 13 h : 21
Question 4) Perform the following algorithms for the given graph. Analyze the difference between the order of nodes or edges visited for the two algorithms.
a) Prim’s algorithm
b) Kruskal’s algorithm
Question 5) Write detail notes on the following topics:
• Huffman Codes
• Breadth first search
• Binary Search Trees
• Optimal Polygon Triangulation