代做CSE 2321 SP24 Project 7代写数据结构语言

日期：2024-04-20 06:23

CSE 2321 SP24 Project 7

Sorting Algorithms

Due: April 19, 2024

1    A History of Algorithms

An algorithm is simply a well-defined method of achieving a certain result. Algorithms have been invented for mathematical problems for thousands of years.  In fact, the English word “algorithm” comes from the name of mathematician Muhammad ibn Mˉusˉa al-Khwˉarizmˉ? (c.  780-850). Al- Khwarizmi’s work was later translated into Latin, and was responsible for introducing the positional decimal number system of Hindu-Arabic numerals to Europe.

The first known computer  algorithm (and computer program!)   is Ada Lovelace’s program to compute the Fibonacci sequence on Charles Babbage’s theoretical mechanical computer, the Analytical Engine.  Below is her program from so-called “Note G”, published in 1843:

2 Insertion Sort

Insertion sort is an algorithm which predates computer science. It is a somewhat common-sense method for sorting that many people use without thinking much about it.  Examine a pseudocode implementation of Insertion Sort given below. Assume that all ∧ and ∨ operators in pseudocode in this project use short-circuit evaluation.

function  InsertionSort(Arr[])

n  =  length(Arr)

for  i  =  1  to  n  -  1

x  =  Arr[i]

j  =  i  -  1

while  (  j  ≥  0  ∧ Arr[j]  >  x  )

Arr[j  +  1]  =  Arr[j]

j  -=  1

end  while

Arr[j  +  1]  =  x

end  for

return  Arr

end  function

1. Explain how Insertion Sort guarantees that the array is sorted by the time it returns.  State your reasoning.  (Hint:  You may want to make the argument using a loop invariant.)  [2 points]

2. Demonstrate the asymptotic lower bound on the runtime of Insertion Sort. Show your work and explain your reasoning.  [2 points]

3. Demonstrate the asymptotic upper bound on the runtime of Insertion Sort. Show your work and explain your reasoning.  [2 points]

4. Explain an ideal use case for Insertion Sort.  Give an example, in- cluding implementation details.  [1 points]

5. Suppose you’re given an array where all the elements are no more than k positions away from their sorted locations.  Give an expression for an upper bound on the runtime of Insertion Sort on that array.  Explain your reasoning.  [3 points]

6. Explain why using a binary search to determine the insertion loca- tion wouldn’t improve the asymptotic runtime of Insertion Sort.  State your reasoning.  [2 points]

3 Merge Sort

Merge Sort was invented in 1945. It uses the divide-and-conquer design paradigm to improve upon na¨?ve sorting algorithms. Examine a pseudocode implementation of Merge Sort given below. Note that Arr[a:b] will in- dicate the subarray beginning at index a inclusive and ending at index b exclusive. Assume that the subarray process runs in constant time.

function  MergeSort(Arr[])

n  =  length(Arr)

if  (  n  >  1  )

left  =  MergeSort(Arr[0:n/2])

right  =  MergeSort(Arr[n/2:n])

leftIndex  =  0

rightIndex  =  0

for  i  =  0  to  n  -  1

if  (? (rightIndex  < n/2) ∨

(leftIndex  < n/2 ∧

left[leftIndex]  < right[rightIndex])) Arr[i] = left[leftIndex]

leftIndex++

else

Arr[i]  =  right[rightIndex]

rightIndex++

end  if

end  for

end  if

return  Arr

end  function

7. Explain why short-circuit evaluation ensures that the if condition will never access elements out of the bounds of the arrays left and right. [2 points]

8. By assuming that the recursive calls return the expected results, argue why Merge Sort must return a sorted array.  State your reasoning.  (Hint: You may want to make the argument using a loop invariant.)  [2 points]

9. Demonstrate the asymptotic complexity of Merge Sort.  You may use any method you wish to determine the asymptotic complexity of the recursive form. Show your work.  [3 points]

10. Explain why the given implementation of Merge Sort is not adaptive. [1 points]

11. Explain how you could alter the given implementation of Merge Sort to be adaptive to the use case where the array given is composed of two sorted arrays of possibly different lengths appended together. Give sufficient implementation details.  [2 points]

4    Merge-Insertion Sort

Merge-Insertion Sort was invented in 1959.  As the name suggests, it is a hybrid algorithm between Insertion Sort and Merge Sort. The process is as follows:

1.  Pair off all the elements in the array.

2.  Recursively sort the collection of pairs according to the larger element in each pair.

3. Insert the smaller element in each pair into the sorted array of larger elements. Note that you only need to search for the insertion location of an element to the left of the element’s corresponding paired value.

Merge-Insertion Sort has asymptotic runtime in Θ(nlog2 (n)).

12. Explain how Merge-Insertion sort uses features of or ideas from both Merge Sort and Insertion Sort.  [2 points]

13. Explain at least one way that Merge-Insertion Sort has better effi- ciency than Merge Sort. State your reasoning.  [1 points]

14. Explain at least one way that Merge-Insertion Sort has better effi- ciency than Insertion Sort. State your reasoning.  [1 points]

5 Shellsort

Shellsort was invented in 1959, and is named after its inventor, Donald Shell. It is an extension of Insertion Sort. The process is as follows:

1.  Use a gap sequence of decreasing integers which ends with 1.  Select the first gap integer as g.

2. Apply insertion sort to the g subarrays that start at each of the first g  elements and skip g ? 1 elements to reach the next value in the subarray.

3.  Unless g = 1, select the next gap integer as g.

The runtime of Shellsort is highly dependent on the gap sequence cho- sen.   The  most  optimal known asymptotic complexity for  Shellsort is in Θ(n(log2 (n))2 ), using 3-smooth numbers as the gap sequence, as shown in this paper.  (No need to read the paper unless you’re curious.)

15. Explain why as long as the gap sequence ends in 1, Shellsort will return a sorted array. State your reasoning.  [2 points]

16. Explain  how  insertion  sort  is reasonably efficient for the larger, earlier gap values.  [1 points]

17. Explain how insertion sort is reasonably efficient for the smaller, later gap values.  (Hint:  Consider what the array is like after multiple iter- ations with different gap values.)  [1 points]

6    Bonus: Master Theorem Regularity Condition

Recall the type of recursive form that the Master Theorem applies to:

Where a ≥ 1 and b > 1. Further, recall the formulation of Case 3:

The second condition is referred to as the Regularity Condition. For this bonus problem, we will show that for certain forms of f(n), it is in fact a redundant condition.  (You may want to attach additional scrap paper.)

a. Suppose that 二p e R : f(n) = np.  Show that the following statement is true.  [3 Extra Credit points]

b. Suppose that

Show that the following statement is true.  [3 Extra Credit points]