算法分析代写 | COSC 2123/1285 Workshop 6 Divide and Conquer Algorithmic Paradigm

本次澳洲代写是算法分析的一个quiz

Objective

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.

Questions

5.1.6 Apply mergesort to sort the list E, X, A, M, P, L, E in alphabetical
order.

5.2.1 Apply quicksort to sort the list E, X, A, M, P, L, E in alphabetical
order.

5.1.7 Is mergesort a stable sorting algorithm?

5.2.3 Is quicksort a stable sorting algorithm?

5.1.1

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
problem?

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).

程序辅导定制C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB