Consider the list [57, 91, 64, 13, 27, 88, 63]. Show how Insertion Sort sorts the list by

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

1. Consider the list [57, 91, 64, 13, 27, 88, 63]. Show how Insertion Sort sorts the list by [10 pts] showing the list after each iteration of the outer for loop, and stating the number of inversions present in the array at that point.

2. Referring to InsertionSort:

(a) Prove using mathematical induction that for all 0 ≤i≤n-1 that after the for loop [15 pts] ends each i that the 0,..., i elements of the list are sorted.

(b) Use your answer to (a) to conclude mathematically that InsertionSort works.

[5 pts]

3. Gnome Sort is a cross between Insertion Sort and Bubble Sort. It behaves like Insertion Sort, but uses progressive downwards Bubble Sort-style swaps instead of storing the value to be inserted. Here is the pseudocode of Gnome Sort:

[15 pts]

PRE: A is a list of length n.

for i 1 to n-1

end

j=i

while (j> 0 and A[j] < A[j-1] swap A[j] and A[j-1] jj 1

end

\\ POST: A is sorted.

Assume assignments take A time, conditional checks take C time, and swaps take S time, all of which are constants. Compute the average-case runtime of Gnome Sort, simplify to a polynomial in terms of n, and state its time complexity. (Ignore the maintenance of the for loop. You may need to first compute the runtime of Gnome Sort in terms of both n and the number of inversions I of the input list, and then use what you know about the expected number of inversions.)

4. Show the steps of binary search when looking for the value 17 in the list:

{-3, 4, 7, 17, 20, 30, 40, 51, 105, 760}

At each step give the value of C and how the comparisons update L and R. Inside the while loop how many comparisons are made?

[10 pts]

 

Attachments:

Expert's Answer

282 Times Downloaded

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of