(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

This question concerns the following sorting algorithm (attachment). (b) Consider the operation of SORT on a list of length N. How many comparisons in line 4 take place when i = 1 and when i = N-1? (c) How many comparisons take place in total? Show your working. You may use the result 1+2+...+n=n[(n+1)/2] (d) Based on the analysis above, or otherwise, what is the worst, best and average- case time complexity of SORT? Explain your answer.
determine if each following statement is True or False
I will vote your solution
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…
Suppose we wish to sort the following values: 84, 22, 19, 11, 60, 68, 31, 29, 58, 23, 45, 93, 48, 31, 7. Assume that: we have three pages of memory for sorting; we will use an external sorting algorithm with a 2-way merge; a page only holds two values. We do not use double buffering and we use quick sort in pass 0 to produce the initial runs. For each sorting pass, show the contents of all temporary files except that you should fully utilize the buffers by sorting every 3 pages into a run in pass 0. Could you show step by step detailed explaination for this?
(b) Consider the two sorting algorithms below, which each take as input array A] indexed from s to f. SwapSort2(A, s, f) SwapSort1(A, s, f) swapped = true while (swapped) swapped = false for i = s to f-2 swapped = true while (swapped) swapped = false for i = s to f-2 if A[i] > A[i+2] Swap A[i] and A[i+2] swapped = true if A[i] > Ali+2] Swap A[i] and A[i+2] swapped = true swapped = true while (swapped) swapped = false for i = s to f-1 if A[i] > A[i+1] Swap A[i] and A[i+1] swapped = true • Execute SwapSort1 on array A = [7,6, 5, 4, 3, 2, 1] indexed from s = 1 to f = 7. • Which of the above two algorithms is correct?. Justify your answer. • What is the worst-case number of comparisons are made by SwapSort2 when the input array A has length n and is sorted in reverse order? • Does your result from above represent the worst-case number of comparisons made by SwapSort2? Justify your answer. • Justify that the worst-case runtime of SwapSort2 is of the form T(n) a, b, c. = an? + bn +c for…
use the partition function given when writing quicksort algorithm
All parts of Q11 please.
(c) Consider the sorting algorithm: 1 SORT(A, a, b) 2 if a
A. Using the algorithm in deleting an element at the beginning of the array and the traversing algorithm, simulate the given array below: TRAVERSE OPERATION DELETION AT THE BEGINNING OF THE ARRAY Algorithm: Algorithm: Step 1: Set index = 0 Step 2: Repeat step 3 while (i < max) Step 3: Step 1: Set index = 0 Step 2: Repeat step 3 while (index < max) Step 3: Set array [index] = array [index + 1] Print array[index] index = index + 1 index = index + 1 Step 4: Set max = max - 1 Step 4: End Step 5: End 1. array 5 2
Please solve

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