# see the attached due in 2 hours

see the attached due in 2 hours

see the attached due in 2 hours
CIS350/3501 Summer 2022 (10 points) Radix Sort Shows the sequences of values found in each bucket after each pass involved in sorting the list 359, 243, 439, 068, 436, 175, 831, 363. During pass 1, the ones place digits are ordered. During pass 2, the tens place digits are ordered, retaining the relative positions of values set by the earlier pass. On pass 3, the hundreds place digits are ordered, again retaining the previous relative ordering. (10 points) Disjoint Sets via Quick Union Ten elements 1, 2, …, 9, 10, initially in different sets. Show the result of the following sequence of operations: union (1, 2), union (1, 3), union (4, 5), union (6, 7), union (4, 6), union (1, 4), union (8, 9), union(8, 10), and union (4,8) when the unions are performed by size. If the sizes of two sets are equal, make the smaller ID as the root of the new set. For the tree created in part a, show the result of the find(7) with path compression. (10 points) Huffman coding: A string contains only six letters (a, b, c, d, e, f) in the following frequency: a b c d e f Show the Huffman tree and the Huffman code for each letter. (8 points) Quicksort Using the first element as the pivot, sort 5, 3, 8, 5, 1, 5, 9, 2, 6, 5, 3, 7 using quicksort, show the result after the first-round partition. Here is an array which has just been partitioned by the first step of quicksort (the pivot element has already been swapped with the element pointed to by i in the final part of the partitioning) : 3, 0, 2, 4, 5, 8, 7, 6, 9 List ALL possible pivots. (12 points) Answer parts (a) and (b) with tables or diagrams. Show how you would represent the above graph using adjacency lists. Show how you would represent the above graph using an adjacency matrix. Show the order that the nodes would be visited in a breadth first and depth first traversal starting from the vertex v6, respectively. Assume that whenever the traversal offers a choice of which node to visit first, you will choose the smallest numbered node available. (14 points) Graph Algorithms Use Dijkstra’s algorithm to find the shortest path from vertex A to all other vertices. Use the table below to show all iterations: Vertex Known dv pv From (a) list the minimum distance and the shortest path for the A-D. State the edges in the Minimum Spanning Tree which would be found by Prim’s Algorithm if it started with vertex A. List the edges in the order in which they would be added by the algorithm. (6 points) Given two sets A and B of n integers, design an algorithm to determine if A is equal to B in O(nlogn) time. Two sets are equal if and only if they have the same elements. (10 points) Consider the definition h(0) = 1 h(1) = 1 h(n) = h(n-1) + h(floor(n/2)) + 1 For example, h(2) = h(1) + h(1) + 1 = 3, h(3) = h(2) + h(1) + 1 = 5, etc. An obvious algorithm to compute h is a recursive one, based directly on the defining equations. Is that algorithm efficient? Why or why not? Justify your answer. If not, write one or more function(s) to implement a linear time O(n) algorithm. 7