# CSCI-B 505 Applied Algorithms (3 cr.) № 4 solution

\$30.00

Category:

## Description

Problem 1: Algorithm Design 1
Suppose you are given two sequences D1 and D2 of n elements, possibly containing duplicates,
on which a total order relation is defined. Describe an efficient algorithm for determining if D1
and D2 contain the same set of elements. What is the running time of this method?
Problem 2: Algorithm Design 2
Given an array D of n integers in the range [0, n2 − 1], describe a simple method for sorting D
in O(n) time.
Problem 3: Algorithm Design 3
Given a sequence D of n elements, on which a total order relation is defined, describe an efficient
method for determining whether there are two equal elements in D. What is the running time of
Problem 4: Merge-sort
Implement a bottom-up merge-sort for a collection of items by placing each item in its own
queue, and then repeatedly merging pairs of queues until all items are sorted within a single
queue.
Assignment № 4 Page 2
Problem 5: Heap Sort
Implement the heap-sort algorithm given in algorithm 1. The max_heapify and build_max_heap
procedures are described in algorithm 2 and algorithm 3, respectively.
Algorithm 1 Heap-sort algorithm
Input: D, an unsorted sequence.
Output sorted D.
build_max_heap(D)
input_length = len(D)
for i = input_length downto 2 do
swap D[1] and D[i]
D.heap_size = D.heap_size −1
max_heapify(D, 1)
end
Algorithm 2 max_heapify algorithm
Input: D, a sequence, and an integer i
Output partially max_heapify applied D
l =left_child(i)
r =right_child(i)
input_length = len(D)
D.heap_size = input_length
if l ≤ D.heap_size and D[l] > D[i] then
largest = l
else
largest = i
end
if r ≤ D.heap_size and D[r] > D[largest] then
largest = r
end
if largest 6= i then
swap D[i] and D[largest]
max_heapify(D, largest)
end
Assignment № 4 Page 3
Algorithm 3 build_max_heap algorithm
Input: D, a sequence.
Output Max-heap D
input_length = len(D)
D.heap_size = input_length
for i = binput_length /2c downto 1 do
max_heapify(D, i)
end
Problem 6: Counting Sort
Implement the counting-sort algorithm given in algorithm 4.
Algorithm 4 Counting-sort algorithm
/* len(D) = len(B), max(D) = k */
Input: D: an unsorted sequence, B : empty sequence, k : an integer.
Output sorted D.
Create a new array C[0 . . . k]
input_length = len(D)
for i = 0 → k do
C[i] = 0
end
for j = 1 → input_length do
C[D[j]] = C[D[j]] + 1
end
for i = 1 → k do
C[i] = C[i] + C[i − 1]
end
for j = input_length downto 1 do
B[C[D[j]]] = D[j]
C[D[j]] = C[D[j]] − 1
end
Assignment № 4 Page 4
Problem 7: Bucket Sort
Implement the bucket sort algorithm given in algorithm 5.
Algorithm 5 Bucket-sort algorithm
Input: D, an unsorted sequence.
Output sorted D.
input_length = len(D)
Create a new array B[0 . . .(input_length − 1)]
for i = 0 → (input_length − 1) do
make B[i] an empty list
end
for i = 1 → n do
insert D[i] into list B[binput_length × D[i]c]
end
for i = 0 → (input_length − 1) do
sort list B[i] with insertion sort
end
concatenate the lists B[0], B[1], . . . , B[n − 1] together in order
Assignment № 4 Page 5
Directions