Assume we want to sort an array A[1..n] based on merge sort algorithm and you have been already provided with an implementation of the merge procedure Merge(A, p, q, r) to combine two sorted arrays A[p..q] and A[q+1..r], that is you can use this procedure directly:Write the pseudocode for the merge sort algorithm.Draw a tree diagram to demonstrate the merge sorting process of the following sequence: 5 4 3 2 1.Similarly, if you are provided with a procedure Find-Max-Crossing-Subarray (A, low, mid, high), write the pseudocode for a divide-and-conquer algorithm to solve the maximum subarray problem, which has been described in Question 2.Here is question 2 for the third part (I have also provided an image of the array problem as well):Given an array A[1…n] of numeric values (can be positive, zero, and negative) determine the subarray A[i…j] (1≤ i ≤ j ≤ n) whose sum of elements is maximum over all subvectors. Below is a brute-force algorithm. Analyze its best case, worst case and average case time complexity in terms of a polynomial of n and the asymptotic notation of ɵ. You need to show the steps of your analysis. MAX-SUBARRAY-BRUTE-FORCE (A)n = A.lengthmax-so-far88for 1 to nsum = 0for h=1 to nsum = sum + A[h]if sum > max-so-farmax-so-far sumlow = 1high = hreturn (low, high)=

MERGE-SORT(A, p, r)if p < r q = ⌊(p+r)/2⌋ MERGE-SORT(A, p, q) MERGE-SORT(A, q+1, r)…

Answered: Assume we want to sort an array A[1..n]…

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

Related questions

Question

Assume we want to sort an array A[1..n] based on merge sort algorithm and you have been already provided with an implementation of the merge procedure Merge(A, p, q, r) to combine two sorted arrays A[p..q] and A[q+1..r], that is you can use this procedure directly:

Write the pseudocode for the merge sort algorithm.
Draw a tree diagram to demonstrate the merge sorting process of the following sequence: 5 4 3 2 1.
Similarly, if you are provided with a procedure Find-Max-Crossing-Subarray (A, low, mid, high), write the pseudocode for a divide-and-conquer algorithm to solve the maximum subarray problem, which has been described in Question 2.

Here is question 2 for the third part (I have also provided an image of the array problem as well):

Given an array A[1…n] of numeric values (can be positive, zero, and negative) determine the subarray A[i…j] (1≤ i ≤ j ≤ n) whose sum of elements is maximum over all subvectors. Below is a brute-force algorithm. Analyze its best case, worst case and average case time complexity in terms of a polynomial of n and the asymptotic notation of ɵ. You need to show the steps of your analysis.

MAX-SUBARRAY-BRUTE-FORCE (A)
n = A.length
max-so-far
88
for 1 to n
sum = 0
for h=1 to n
sum = sum + A[h]
if sum > max-so-far
max-so-far sum
low = 1
high = h
return (low, high)
=

Expert Solution

Step by step

Solved in 3 steps with 1 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions