CSCI-B505 - Applied Algorithms - (3 cr.) № 4 - Solved

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.

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)

 

 

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

 

 

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

 

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

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