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 your method?
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 No 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 ̸= i then
swap D[i] and D[largest]
max_heapify(D, largest) end
Assignment No 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 = ⌊input_length /2⌋ 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
B[C[D[j]]] = D[j] C[D[j]] = C[D[j]] − 1
end
1 do
Assignment No 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[⌊input_length × D[i]⌋]
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
