## 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 № 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

Please follow the syllabus guidelines in turning in your homework. While testing your programs

(Questions 4-7), run them with a variety of inputs, e.g. ordered and unordered sequences, etc.,

and discuss your findings. The first four questions and question 7 are worth 15 points each. Any

question you choose among them is optional. If you answer all, one question will be counted

as an extra credit question. Questions 5 and 6 are worth 20 points each . This homework is

due Sunday, Oct 17, 2021 10:00pm. OBSERVE THE TIME. Absolutely no homework will be

accepted after that time. All the work should be your own.

Assignment № 4 Page 6