Students who complete this tutorial should:
- Understand the concepts of divide and conquer.
- Be familiar with the way this concept can be applied to sorting problems.
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).
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: email@example.com 微信号:vipnxx