Explore BrainMass
Share

Design and Analysis of Algorithms

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

Consider a set G consisting of m integers.

a) Design an algorithm that finds and gives as output the k smallest numbers of the whole G sorted in ascending order and has time complexity O(m*lg(m)) and spatial complexity O(m).

Note: lg denote the logarithm base 2.

b) Design an algorithm that solves the above problem using a mandatory heap and has time complexity O(m + k*lg(m)) and space complexity O(m).

In response give either pseudocode or the description of the steps of the algorithm and justify the complexities.

© BrainMass Inc. brainmass.com October 17, 2018, 4:09 am ad1c9bdddf
https://brainmass.com/computer-science/sorting/design-analysis-algorithms-451551

Solution Preview

Please note that the explanation in this response is rather verbal as the solutions in this response make (complete/partial) use of standard/well-known sorting algorithms.

(a) We can use Merge Sort to sort the given set G of m integers (stored in an array of size m) in increasing order.
Merge Sort guarantees O(m*lg(m)) time complexity.

We will use another array of size m to store the result of merging at any merging step in the merge sort, which will ensure no shifting of elements in same array during merging, rather writing the merged subsequences into temporary array as the elements are being merged and later copy the merged content to the ...

Solution Summary

The explanation in this response is rather verbal as the solutions presented in this response make (complete/partial) use of standard/well-known sorting algorithms.

$2.19
Similar Posting

Design and Analysis of Algorithms

Consider a table B that consists of m integers B [1], B [2] ... B [m]. Design an algorithm to produce a two-dimensional m x m table C such that each element C[i,j] for i <j contains the sum of the B [i] up to the B [j], that is, (B [i] + B [i +1] + ... + B [j]). The values C[i,j] for i >= j are left unspecified, that is, these can take any value.

a) Design an algorithm that creates the table C according to the above description and has time complexity Theta(m^3).
In response give either pseudocode or the description of the steps of the algorithm, and calculate the time complexity.

b) Design an algorithm that creates the table C according to the above description and has time complexity Theta(m^2).
In response give either pseudocode or the description of the steps of the algorithm, and justify the time complexity.

View Full Posting Details