(1) [30] Illustrate the operations of Merge-Sort on the following array: A=<16, 20, 10, 5, 13,8, 7, 4, 25, 3, 6, 12>.(2) [15] What are the worst-case and best-case running times of the serial Merge-Sort?Justify your answer.(3) [15] What is the running time T of parallel merge-sort algorithm if the number ofprocessors is unlimited? Justify your answer.

Question 1: Merge Sort Operations on Array A = [16, 20, 10, 5, 13, 8, 7, 4, 25, 3, 12]:Step 1:Divide…

Answered: (1) [30] Illustrate the operations of…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

Problem Description Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is alreadysorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j .Example: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).Requirement Design should be based on divide and conquer.Running time should NOT be worse than .Must use recursion to solve the subproblems. Input Specification Your program should read from an input file, which starts with a line indicating the number of test cases.Each of the following lines indicates a test case, and each test case includes a sequence of numbers(separated by spaces) for which you need to count inversions. Sample Input 32 4 1 3 51 2 4 8 9 3 5 6 1 20 6 4 5Output Specification For each test case, print one line with a format of The sequence has ? inversions in…
Case Study 1 Problem: Merge Sort Merge Sort follows the rule of Divide and Conquer to sort a given set of numbers/elements, recursively, hence consuming less time. Merge sort runs in O(n*log n) time in all the cases. Two functions are involved in this algorithm. The merge() function is used for the merging two halves and the mergesort() function recursively calls itself to divide the array until the size becomes one. Use the array below to perform a Merge Sort. Show all necessary workings. {75, 22, 65, 97, 35, 56, 18, 89} Case Study 2 Problem: Hashing Hashing is a technique to convert a range of key values into a range of indexes of an array. Load Factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased which may cause a collision. When collision occurs, there are two simple solutions: Chaining and Linear Probe. In what order could the elements have been added using the output below and given the following hash table implemented…
(1) Use perf_count and the other ideas from 8.1 above to generate a list of data, where the ith entry is the time tm(i) necessary for merge-sort to sort lists of randomly chosen elements of length 2¹ for i = 1, ..., 10. (2) Plot tm(i) against 2¹ on a loglog plot. Briefly explain (as a comment) what the graph says about merge- sort's speed, using big-O notation. (3) Write a function insertionsort (somelist) that applies the insertion sort algorithm described in lectures to sort a list. (You should use the pop and insert commands as described in the lecture notes.) (4) Use this to find the times tỉ(i) for lists of the same length as in (1). Add tr(i) to your graph (on the same axes as above), and write a comment on-what this says about the speed of insertion sort, in big O notation. (5) Write a function countingsort (mylist) which implements counting sort for lists of non-negative integers, using the algorithm described in lectures. (6) How efficient is countingsort compared to the other…
Case Study 1 Problem: Merge Sort Merge Sort follows the rule of Divide and Conquer to sort a given set of numbers/elements, recursively, hence consuming less time. Merge sort runs in O(n*log n) time in all the cases. Two functions are involved in this algorithm. The merge() function is used for the merging two halves and the mergesort() function recursively calls itself to divide the array until the size becomes one. Use the array below to perform a Merge Sort. Show all necessary workings. (75, 22, 65, 97, 35, 56, 18, 89) Case Study 2 Problem: Hashing Hashing is a technique to convert a range of key values into a range of indexes of an array. Load Factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased which may cause a collision. When collision occurs, there are two simple solutions: Chaining and Linear Probe. In what order could the elements have been added using the output below and given the following hash table implemented…
5(b) Give the two arrays that will be merged by the final step of mergesort on [8, 2, 1, 4, 5, 3, 7, 9].
C++ Illustrate the operation of MERGE-SORT algorithm on the array A = < 25, 11, 41, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0 > Donot copy paste from google
5. Consider the following Algorithms and explain (a) Merge Sort uses what sort of optimisation: greedy, backtracking or divide and conquer? MergeSort (arr[), 1, r) If r > 1 1. Find the middle point to divide the array into two halves: middle m = 1+ (r-1)/2 2. Call mergeSort for first half: Call mergeSort(arr, 1, m) 3. Call mergeSort for second half: Call mergeSort(arr, m+1, r) 4. Merge the two halves sorted in step 2 and 3: Call merge (arr, 1, m, r) (b) Find Shortest Path to Node To search for shortest path you can use Breadth First or Depth First Search. What is the optimum approach? Traverse the graph breadthwise as follows: a. First move horizontally and visit all the nodes of the current layer b. Move to the next layer Traverse the graph depthwise as follows: a. Create a recursive function that takes the index of the node and a visited array. b. Mark the current node as visited and print the node. c. Traversę all the adjacent and unmarked nodes and call the recursive function with…
Consider the following list of elements (M-2) 18, 40, 16, 82, 64, 67, 57, 50, 37, 47, 72,14, 17, 27, 35Using quicksort algorithm, Use pivot as the median of the first, last, and middle elements of the list.a. What is the pivot?b. Give the resulting list after one call to the partition procedure. (Data structure and algorithm in c++)
Question 5: Professor Bond has developed the following algorithm that he claims is going to be a break through in computer science. 1 23400 HER 2 { 6 7 8 9 10 11 Assuming array is zero indexed, A[0] is the first and A[n-1] is the last element, the algorithm is as follows: mystery Function (A, n) 12 13 } int last Pos=n-1; while (last Pos > 0) { } int maxPos=0; for (int i=0; i A[maxPos]) i; maxPos = swap (A, maxPos, lastPos); last Pos last Pos - 1; - Given all of this, answer the following questions. Explain what the algorithm does in plain English. Why does the while loop in the algorithm's pseudocode iterate over all ele- ments but the last, rather than for all elements? (c) (d) What is the best-case of this algorithm? What is the (...) bound on the running time of the best-case of this algorithm? What is the worst-case of this algorithm? What is the (...) bound on the running time of the worst-case of this algorithm?
Consider a situation where swap operation is very costly. Which of the following sorting algorithms should be preferred so that the number of swap operations are minimized in general? (a) Insertion Sort (b) Quick Sort (c) Heap Sort (d) Selection Sort (e) Merge Sort
11.) (a) Show how to Merge (not Mergesort) three ordered lists each of size n/3, with a total of at most 53 n compare operations. (b) Let's examine a new Merge sort algorithm, where parameter A in (A,n) is a list of numbers to be sorted and n is the total length of list A. Procedure mergeSort (A,n):: if Else n=1 then return A divide A into three equal size lists B, C, D, B:= mergesort(B,n/3) C:=mergesort(C,n/3) D: mergesort(D,n/3) return merge(B, C, D) End. Set up and solve a recurrence relation to analyze the worst-case number of operations of compares that this version does.
Question 6: Professor Holmes has come up with a new sorting algorithm. He calls it Trinary Sort and "claims" that it is asymptotically faster than Merge Sort, despite the fact both the algorithms operate using similar logic. But, unlike Merge Sort, Trinary Sort splits the input array into (roughly) 3 equal parts at each step of the recursion as long as the array is splittable (i.e., has at least 3 elements). Trinary Sort's merge subroutine, similar in principle to the one used by Merge Sort, takes 3 sorted subarrays and merges them to produce a single sorted array. Given all of this, answer the following questions. (a) In Merge Sort, the merge subroutine makes n-1 comparisons to merge 2 arrays of size n/2, which takes (n) time. How many comparisons will the merge subroutine of Trinary Sort make to merge 3 arrays of size n/3? What would be the (...) bound on the running time for this subroutine? (b) What is the (...) bound on the running time of the Trinary Sort algorithm? Come up with…

SEE MORE QUESTIONS

Recommended textbooks for you

Database System Concepts

Computer Science

ISBN:

9780078022159

Author:

Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:

McGraw-Hill Education

Starting Out with Python (4th Edition)

Computer Science

ISBN:

9780134444321

Author:

Tony Gaddis

Publisher:

PEARSON

Digital Fundamentals (11th Edition)

Computer Science

ISBN:

9780132737968

Author:

Thomas L. Floyd

Publisher:

PEARSON

Database System Concepts

Computer Science

ISBN:

9780078022159

Author:

Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:

McGraw-Hill Education

Starting Out with Python (4th Edition)

Computer Science

ISBN:

9780134444321

Author:

Tony Gaddis

Publisher:

PEARSON

Digital Fundamentals (11th Edition)

Computer Science

ISBN:

9780132737968

Author:

Thomas L. Floyd

Publisher:

PEARSON

C How to Program (8th Edition)

Computer Science

ISBN:

9780133976892

Author:

Paul J. Deitel, Harvey Deitel

Publisher:

PEARSON

Database Systems: Design, Implementation, & Manag…

Computer Science

ISBN:

9781337627900

Author:

Carlos Coronel, Steven Morris

Publisher:

Cengage Learning

Programmable Logic Controllers

Computer Science

ISBN:

9780073373843

Author:

Frank D. Petruzella

Publisher:

McGraw-Hill Education

SEE MORE TEXTBOOKS