If we require insertionSort() to sort a list of 10-billion elements in no more than one...
If we require insertionSort() to sort a list of 10-billion elements in no more than one minute, how many times faster would your new computer system need to be than the fastest system currently in existence, i.e., the one that performs a comparison in 25 ns?
Homework Answers
In insertion sort, we know that in worst case,there can be n(n-1)/2 comparisons and n(n-1)/2 swaps.
From above given information I am assuming that one comparison one operation takes 25ns in fastest computer available.
Assuming fastest computer takes 25ns in both operations(i.e comparison and swaps)
Total time taken by insertion sort in fastest computer= Total number of comparisons * time taken by single comparison + Total number of swaps*time taken by single swaps
=( n(n-1)/2)*25ns + (n(n-1)/2)*25ns
= 25n(n-1)
Now put n = 10 billion = 10 * 109 = 1010
Time taken by insertion sort in fastest computer = 1010(1010-1)*25 * 10-9
= (1020-1010)*25*10-9
= 25 *(1011-10)
= (25 * 1011 - 250)seconds
Ignore -250 in above expression because it would not affect our answer as 25*1011 is very very big number compared to 250.
So,time taken by insertion sort in fastest computer in existence= 25*1011s
Now,we have a computer system in which we want time taken by insertion sort <=60 seconds
Do, required speedup = execution time in fastest computer / execution time required in new computer system
= 25*1011/ 60
= 0.4167 * 1011
= 4.167 * 1010
Required speedup = 4.167 * 1010
so,in order for new system to execute insertion sort on 10 billion elements in no more than 1 minute it needs to 4.167 * 1010 faster than current fastest available system.
Add Answer to:
If we require insertionSort() to sort a list of 10-billion
elements in no more than one...
THIS PROBLEM GIVES YOU MORE INFORMATION THAN YOU NEED SO PLEASE READ THE QUESTIONS CAREFULLY; I try to clarify by referring to the sample sizes. TBNF is a new computer program that is supposed to sol...
THIS PROBLEM GIVES YOU MORE INFORMATION THAN YOU NEED SO PLEASE READ THE QUESTIONS CAREFULLY; I try to clarify by referring to the sample sizes. TBNF is a new computer program that is supposed to solve transportation planning problems. We would like to compare the results of TBNF to a currently used solver called TRoute. TRoute is known to give the best routes in the fastest time so the same problems will be submitted to both systems and the results...
An array of 100 elements is to be sorted using the bubble sort in the modules (the one that tests...
An array of 100 elements is to be sorted using the bubble sort in the modules (the one that tests the return value of floatLargestToTop0 to see if it can return "early".) Check all the true statements about the sort algorithm, i.e., the sort method and its support methods. (Check all that apply.) It will sometimes return (completely sorted) after only 99 data comparisons. It will always require at least one swap. It will always require at least 99 comparisons...
Need help with program. I'm stuck Objectives: In this assignment, we will practice manipulating lists of...
Need help with program. I'm stuck
Objectives: In this assignment, we will
practice manipulating lists of data and arranging items in an
ascending/descending order. you will also explore storing
lists/arrays using different sorting algorithms including, the
selection sort, bubble sort, and insertion sort algorithm.
Comparison between the three algorithms are made based on the
number of comparisons and item assignments (basic operations) each
algorithms executes.
Background: Ordering the elements of a list is
a problem that occurs in many computer...
I need this in C++. This is all one question Program 2: Linked List Class For...
I need this in C++. This is all
one question
Program 2: Linked List Class For this problem, let us take the linked list we wrote in a functional manner in a previous assignment and convert it into a Linked List class. For extra practice with pointers we'll expand its functionality and make it a doubly linked list with the ability to traverse in both directions. Since the list is doubly linked, each node will have the following structure: struct...
//bubble sort implementation// Fig 6.15 with simplified convention for the for loop. #define _CRT...
//bubble sort implementation// Fig 6.15 with simplified
convention for the for loop.
#define _CRT_SECURE_NO_WARNINGS //for windows os only
#include <stdio.h>
#include <stdlib.h>
// Fig. 6.15: fig06_15.c
// Sorting an array's values into ascending order.
#include <stdio.h>
#define SIZE 10
// function main begins program execution
int main(void)
{
// initialize a
int a[SIZE] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37
};
printf("Data items in original order");
// output original array
for (int i = 0;...
I need the report like this (idea) *Sorting Algorithms: A sorting algorithm is an algorithm that...
I need the report like this (idea) *Sorting Algorithms: A sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other algorithms (such as search and merge algorithms) which require input data to be in sorted lists; it is also often useful for canonical zing data and for producing human-readable output. More formally, the output must satisfy...
Read the attached article. Do you feel one style of banking control is more stable than...
Read the attached article. Do you feel one style of banking
control is more stable than the other? Why? Does one banking method
minimize market volatility and risk better or is it just packaged
differently? Do you feel the US (Western) Banking system can better
control the patterns of behavior going forward that have caused
economic damage in the past? Should the Fed continue its stimulus
policy, reduce it or abandon it entirely (Google some recent
articles to research this)? (Please...
In this question, we will think about how to answer shortest path problems where we have more than just a single sourc...
In this question, we will think about how to answer shortest path problems where we have more than just a single source and destination. Answer each of the following in English (not code or pseudocode). Each subpart requires at most a few sentences to answer. Answers significantly longer than required will not receive full credit You are in charge of routing ambulances to emergency calls. You have k ambulances in your fleet that are parked at different locations, and you...
Answer the question: "what is a system?" It can be as short as one page or...
Answer the question: "what is a system?" It can be as short as one page or as long as 3 pages. What is a System? The term “system” originates from the Greek term syst¯ema, which means to “place together.” Multiple business and engineering domains have definitions of a system. This text defines a system as: System An integrated set of interoperable elements, each with explicitly specified and bounded capabilities, working synergistically to perform value-added processing to enable a User to...
In Python! Search Exercise 11.A: Mergesort with a Comparator CS 1410 Background The sort algorithms we...
In
Python!
Search Exercise 11.A: Mergesort with a Comparator CS 1410 Background The sort algorithms we have looked at in Module 8 have all sorted list elements in ascending because it compares elements with the less-than operator. For example, in our mergesort program, the comparison appears as follows: 18 L[1] R01 The effect of this comparison is that if L(i) is less than RC), then L[is considered to come before R[i] in the sorted result. Hence the ascending order of...
An array of 100 elements is to be sorted using the bubble sort in the modules (the one that tests the return value of floatLargestToTop0 to see if it can return "early".) Check all the true statements about the sort algorithm, i.e., the sort method and its support methods. (Check all that apply.) It will sometimes return (completely sorted) after only 99 data comparisons. It will always require at least one swap. It will always require at least 99 comparisons...
Need help with program. I'm stuck
Objectives: In this assignment, we will
practice manipulating lists of data and arranging items in an
ascending/descending order. you will also explore storing
lists/arrays using different sorting algorithms including, the
selection sort, bubble sort, and insertion sort algorithm.
Comparison between the three algorithms are made based on the
number of comparisons and item assignments (basic operations) each
algorithms executes.
Background: Ordering the elements of a list is
a problem that occurs in many computer...
I need this in C++. This is all
one question
Program 2: Linked List Class For this problem, let us take the linked list we wrote in a functional manner in a previous assignment and convert it into a Linked List class. For extra practice with pointers we'll expand its functionality and make it a doubly linked list with the ability to traverse in both directions. Since the list is doubly linked, each node will have the following structure: struct...
//bubble sort implementation// Fig 6.15 with simplified
convention for the for loop.
#define _CRT_SECURE_NO_WARNINGS //for windows os only
#include <stdio.h>
#include <stdlib.h>
// Fig. 6.15: fig06_15.c
// Sorting an array's values into ascending order.
#include <stdio.h>
#define SIZE 10
// function main begins program execution
int main(void)
{
// initialize a
int a[SIZE] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37
};
printf("Data items in original order");
// output original array
for (int i = 0;...
Read the attached article. Do you feel one style of banking
control is more stable than the other? Why? Does one banking method
minimize market volatility and risk better or is it just packaged
differently? Do you feel the US (Western) Banking system can better
control the patterns of behavior going forward that have caused
economic damage in the past? Should the Fed continue its stimulus
policy, reduce it or abandon it entirely (Google some recent
articles to research this)? (Please...
In this question, we will think about how to answer shortest path problems where we have more than just a single source and destination. Answer each of the following in English (not code or pseudocode). Each subpart requires at most a few sentences to answer. Answers significantly longer than required will not receive full credit You are in charge of routing ambulances to emergency calls. You have k ambulances in your fleet that are parked at different locations, and you...
In
Python!
Search Exercise 11.A: Mergesort with a Comparator CS 1410 Background The sort algorithms we have looked at in Module 8 have all sorted list elements in ascending because it compares elements with the less-than operator. For example, in our mergesort program, the comparison appears as follows: 18 L[1] R01 The effect of this comparison is that if L(i) is less than RC), then L[is considered to come before R[i] in the sorted result. Hence the ascending order of...
Most questions answered within 3 hours.
-
Please explain steps:
An 80 kg swimmer steps off a platform 10 m above the water...
asked 29 minutes ago -
A lottery exists where balls numbered 1 to 17 are placed in an
urn. To win,...
asked 32 minutes ago -
26) Briefly describe, using words or simple diagrams, the
chemiosmotic theory for coupling oxidation to phosphorylation...
asked 2 hours ago -
Suppose that XX is a random variable with mean 16 and standard
deviation 5 . Also...
asked 3 hours ago -
Calculate the number density of argon gas at a temperature of
24C and a pressure of...
asked 6 hours ago -
Alternative
Classification
How to Estimate
Probabilities from Data? ( For continuous Attributes)
And How to generate...
asked 6 hours ago -
An explosion breaks a 20.0-kg object into three parts. The
object is initially moving at a...
asked 7 hours ago -
Calculate the approximate number of residues of Rubisco, which
is involved in carbon fixation in plants,...
asked 8 hours ago -
Other decisions about scientific claims can have a much broader
impact.ENERGYarrow-10x10.png, environment, health, security - all...
asked 9 hours ago -
I need to write a research paper and work cited about this
topic: The United States...
asked 9 hours ago -
Hello! I was wondering if I could have some help?
If the vapor pressure of carvone...
asked 10 hours ago -
An economist wants to estimate the mean per capita income (in
thousands of dollars) for a...
asked 10 hours ago