Description
Contents
Problem 1: Algorithm Design 1 2
Problem 2: Algorithm Design 2 2
Problem 3: Algorithm Design 3 2
Problem 4: Merge-sort 2
Problem 5: Heap Sort 3
Heap-sort algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
max_heapify algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
build_max_heap algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Problem 6: Counting Sort 4
Counting-sort algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Problem 7: Bucket Sort 5
Bucket-sort algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
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
