See the attached file
Data Structures and Algorithm Analysis
Homework #2
Submission instruction:
Submit your homework as a single WORD or PDF file to the Canvas under the “HW2” folder.
Problem 1 (10 points): Disjoint Sets via Quick Union
Nine elements 1, 2, …, 9, initially in different sets. Show the result of the following sequence of operations: union (1, 2), union (3, 4), union (3, 5), union (1, 3), union (6, 7), union (8, 9), union (6, 8) and (3, 6) 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(9) with path compression.
Problem 2 (10 points): Huffman coding:
A string contains only five letters (a, b, c, d, e) in the following frequency:
| a | b | c | d | e |
| 10 |
Show the Huffman tree and the Huffman code for each letter.
Problem 3 (10 points): sort the sequence 3, 1, 4, 1, 5, 7, 2, 8, 5 using insertion sort. Show the resulting sequences for each pass p, referring to Lecture 13-Slide 13.
Problem 4 (10 points): Mergesort
Sort 4, 1, 3, 1, 9, 5, 7, 2 using mergesort. Showing the result of each step.
Determine the running time of mergesort for (i) sorted input, (ii) reverse-ordered input, and (iii) random input
Problem 5 (10 points): Sort 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 using quicksort, showing the result of each step. Always pick the first element as the pivot.
Problem 6 (10 points): Suppose we exchange elements a[i] and a[i+k], which were originally out of order. Prove that at least 1 and at most 2k-1 inversions are removed.
Problem 7 (10 points): quicksort
For the quicksort implementation in Lecture 13 – Slide 58-60, what is the running time when all keys are equal
Suppose we change the partitioning strategy so that neither i nor j stops when an element with the same key as the pivot is found. What fixes need to be made in the code to guarantee that quicksort works, and what is the running time, when all keys are equal.
Problem 8 (10 points): Suppose you have an array of N elements, containing three distinct keys, A, B, and C (A<B<C). Give an O(N) algorithm to rearrange the list so that all A elements precede B elements, which in turn precede C elements. You may use only constant extra space.
Problem 9 (10 points): Radix Sort
Shows the sequences of values found in each bucket after each pass involved in sorting the list 275, 087, 426, 061, 509, 170, 677, 503. 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.
