算法分析代写 | COSC 2123/1285 Workshop 6 Divide and Conquer Algorithmic Paradigm
Students who complete this tutorial should:
5.1.6 Apply mergesort to sort the list E, X, A, M, P, L, E in alphabetical
5.2.1 Apply quicksort to sort the list E, X, A, M, P, L, E in alphabetical
5.1.7 Is mergesort a stable sorting algorithm?
5.2.3 Is quicksort a stable sorting algorithm?
a Write a pseudocode for a divide-and-conquer algorithm for nding a po-
sition of the largest element in an array of n numbers.
b What will be your algorithm’s output for arrays with several elements of
the largest value?
c Set up and solve a recurrence relation for the number of key comparisons
made by your algorithm.
d How does this algorithm compare with the brute-force algorithm for this
5.2.11 Nuts and bolts You are given a collection of n bolts of different widths
and n corresponding nuts. You are allowed to try a nut and bolt together, from
which you can determine whether the nut is larger than the bolt, smaller than
the bolt, or matches the bolt exactly. However, there is no way to compare
two nuts together or two bolts together. The problem is to match each bolt
to its nut. Design an algorithm for this problem with average-case efficiency of
Omega(n log n).