Data and Information Structures

CS 3304 – Data and Information Structures
Assignment 5
Due: 11/23/2021, 23:59
Submission: Submit your solutions as a single .pdf file through Blackboard. .pdf file will contain
your solutions for all questions. If you scan your handwritten solutions, be sure that your
handwriting is legible.
Q1 (15 pts). Quick sort. Given the array of numbers, show the elements of the array after each
split operation of quick sort. The algorithm will sort the array in increasing order. Select the first
element as pivot in each split. For instance, use 49 as pivot in the first iteration and show the
array elements after split. Then, in the second iteration, apply split operation to left sublist and
right sublist. You can continue splits until you have 0 or 1 element in sublists.
i
x[i]
1
49
2
27
3
33
4
56
5
87
6
91
7
24
8
69
9
42
10
21
11
19
12
82
13
29
14
77
15
50
Q2 (15 pts). Binary merge sort. Given the array of numbers, show the elements of the array
after each iteration of binary merge sort. Since there are 16 numbers, there will be log216 = 4
iterations. The algorithm will sort the array in increasing order.
i
x[i]
1
31
2
33
3
22
4
11
5
46
6
35
7
42
8
39
9
13
10
96
11
18
12
12
13
75
14
69
15
38
16
44
Q3 (15 pts). Natural merge sort. Given the array of numbers, show the elements of the array
after each iteration of natural merge sort. The algorithm will sort the array in increasing order.
i
x[i]
1
31
2
33
3
22
4
11
5
46
6
35
7
42
8
39
9
13
10
96
11
18
12
12
13
75
14
69
15
38
16
44
Q4 (10 pts). Radix sort. Given the array of numbers, show the elements of the array after each
iteration of radix sort. Since there are 4 digits, there will be 4 iterations. The algorithm will sort
the array in increasing order.
i
x[i]
1
5497
2
2273
3
6335
4
5329
5
1871
6
0914
7
9426
8
5248
9
0963
10
7194
11
3789
12
8117
Q5 (20 pts). Huffman coding. Construct the Huffman code for the characters and weights given
below:
Character
Weight
A
0.08
B
0.1
C
0.04
D
0.14
E
0.02
F
0.05
G
0.13
H
0.09
I
0.06
J
0.01
K
0.12
L
0.16
Q6 (25 pts). AVL Tree. Given an empty AVL Tree, insert the following numbers into AVL Tree in
the given order and show the tree after each insertion. Also, if rotation is needed after
insertion, mention which rotation you applied.
15, 22, 29, 26, 24, 25, 10, 6, 12, 11, 23