Given an array of numbers, you want to find out the three greatest numbers. Do you...
Given an array of numbers, you want to find out the three greatest numbers. Do you have to sort the array, or is there a faster way than applying a sorting algorithm? Explain why you use or not use sorting in terms of the worst-case running time. Give an example.
Homework Answers
=>There's no need to use sorting any algorithm for finding the greatest numbers. Because we may use three variables name Max1,Max 2,Max3.
=>while traversing the array we'll update the three variables If needed otherwise go for next index element.
=> This method takes O(n) time but any sorting Algorithm takes at least O(n logn)time so the O(n) method is efficient.
Ex : A={1,2,3,4,5,6,7,8,9,10,11,12,13}
Max 1 = 13
Max 2 = 12
Max 3 = 11
After iterations... If sorting it takes O(13 log 13) but the actual method takes O(13)
Add Answer to:
Given an array of numbers, you want to find out the
three greatest numbers. Do you...
2.1 Searching and Sorting- 5 points each 1. Run Heapsort on the following array: A (7,3, 9, 4, 2,5, 6, 1,8) 2. Run merge sort on the same array. 3. What is the worst case for quick sort? What is...
2.1 Searching and Sorting- 5 points each 1. Run Heapsort on the following array: A (7,3, 9, 4, 2,5, 6, 1,8) 2. Run merge sort on the same array. 3. What is the worst case for quick sort? What is the worst case time com- plexity for quick sort and why? Explain what modifications we can make to quick sort to make it run faster, and why this helps. 4. Gi pseudocode for an algorithm that will solve the following...
Subject: Algorithm need this urgent please. 2.1 Searching and Sorting- 5 points each 1. Run Heapsort on the following array: A 17, 3, 9, 4, 2,5, 6, 1,8) 2. Run merge sort on the same array 3. What...
Subject: Algorithm
need this urgent please.
2.1 Searching and Sorting- 5 points each 1. Run Heapsort on the following array: A 17, 3, 9, 4, 2,5, 6, 1,8) 2. Run merge sort on the same array 3. What is the worst case for quick sort? What is the worst case time com- plexity for quick sort and why? Explain what modifications we can make to quick sort to make it run faster, and why this helps.
2.1 Searching and Sorting-...
4. [30 pts; 10+9+11] a) You are given traffic data (number of p large number, in the order of hundreds of thousands.) with greatest amount of traffic (k is much smaller than n). Which of inserti...
4. [30 pts; 10+9+11] a) You are given traffic data (number of p large number, in the order of hundreds of thousands.) with greatest amount of traffic (k is much smaller than n). Which of insertion sort, m quicksort, or heapsort may be used to devise the fastest (in worst case) algorithm for this task? What would be its worst case big O running time, in terms of n and k? (Note: it as soon as you get the top...
please I need it urgent thanks algorithms 2.1 Searching and Sorting- 5 points each 3. What is the worst case for quick sort? What is the worst case time com- plexity for quick sort and why? Ex...
please I need it urgent thanks algorithms
2.1 Searching and Sorting- 5 points each 3. What is the worst case for quick sort? What is the worst case time com- plexity for quick sort and why? Explain what modifications we can make to quick sort to make it run faster, and why this helps. 4. Give pseudocode for an algorithm that will solve the following problem. Given an array AlL..n) that contains every number between 1 and n +1 in...
7. (14 points) Use LSD-first Radix Sort algorithm to sort the following array of numbers. Write...
7. (14 points) Use LSD-first Radix Sort algorithm to sort the following array of numbers. Write the worst case, the best case time complexity and discuss if these sorting algorithms are stable and in-place? In what cases using these algorithms would not be efficient? (You must run Counting Sort for each digit explicitly.) A=[22,15,16,13,23,45,0,23,123]
4. [30 pts:10+9+11] a) You are given traffic data (number of page hits) for n websites for some time period. (n is a large number, in the order of hundreds of thousands.) You are asked to print t...
4. [30 pts:10+9+11] a) You are given traffic data (number of page hits) for n websites for some time period. (n is a large number, in the order of hundreds of thousands.) You are asked to print the top k websites with greatest amount of traffic (k is much smaller than n). Which of insertion sort, mergesort quicksort, or heapsort may be used to devise the fastest (in worst case) algorithm for this task? What would be its worst case...
That tells how many swaps are done in the worst case given n elements Consider this modification ...
solve 3
that tells how many swaps are done in the worst case given n elements Consider this modification of the partition algorithm. Randomly choose three potential pivots. Partition around the median of the three pivots 3. a) Write the pseudocode for this algorithm b) If this use the quicksort algorithm, what is the running time for the worst-case scenario? When will this happen? c) Why is this algorithm better than the regular quicksort algorithm? 4. Give the pseudocode of...
For [Select], there are three choices: worse than, the same as, better than Answer the following...
For [Select], there are three choices: worse than, the same as,
better than
Answer the following questions about the computational properties of divide-and-conquer sorting algorithms, based on tight big-Oh characterizations of the asymptotic growth rate of the functions for the running time or space size, depending on the question. Assume that the input sequence is given as a list, and the output sequence is also a list. Also assume a general implementation of the sorting algorithms, as opposed to an...
In C++ language, implement a class that can sort an array of numbers using all three...
In C++ language, implement a class that can sort an array of numbers using all three algorithms we have seen in this course, but each method updates a “counter” value every time it accesses the array. Have it print this at the end of the sorting process. Store the array values in an “original” array so you don’t have to re-type it for different sorts (since each sort alters the array), and have the sort modify a copy. Note: IF...
In C++ language, implement a class that can sort an array of numbers using all three...
In C++ language, implement a class that can sort an array of numbers using all three algorithms we have seen in this course, but each method updates a “counter” value every time it accesses the array. Have it print this at the end of the sorting process. Store the array values in an “original” array so you don’t have to re-type it for different sorts (since each sort alters the array), and have the sort modify a copy. Note: IF...
2.1 Searching and Sorting- 5 points each 1. Run Heapsort on the following array: A (7,3, 9, 4, 2,5, 6, 1,8) 2. Run merge sort on the same array. 3. What is the worst case for quick sort? What is the worst case time com- plexity for quick sort and why? Explain what modifications we can make to quick sort to make it run faster, and why this helps. 4. Gi pseudocode for an algorithm that will solve the following...
Subject: Algorithm
need this urgent please.
2.1 Searching and Sorting- 5 points each 1. Run Heapsort on the following array: A 17, 3, 9, 4, 2,5, 6, 1,8) 2. Run merge sort on the same array 3. What is the worst case for quick sort? What is the worst case time com- plexity for quick sort and why? Explain what modifications we can make to quick sort to make it run faster, and why this helps.
2.1 Searching and Sorting-...
4. [30 pts; 10+9+11] a) You are given traffic data (number of p large number, in the order of hundreds of thousands.) with greatest amount of traffic (k is much smaller than n). Which of insertion sort, m quicksort, or heapsort may be used to devise the fastest (in worst case) algorithm for this task? What would be its worst case big O running time, in terms of n and k? (Note: it as soon as you get the top...
please I need it urgent thanks algorithms
2.1 Searching and Sorting- 5 points each 3. What is the worst case for quick sort? What is the worst case time com- plexity for quick sort and why? Explain what modifications we can make to quick sort to make it run faster, and why this helps. 4. Give pseudocode for an algorithm that will solve the following problem. Given an array AlL..n) that contains every number between 1 and n +1 in...
7. (14 points) Use LSD-first Radix Sort algorithm to sort the following array of numbers. Write the worst case, the best case time complexity and discuss if these sorting algorithms are stable and in-place? In what cases using these algorithms would not be efficient? (You must run Counting Sort for each digit explicitly.) A=[22,15,16,13,23,45,0,23,123]
4. [30 pts:10+9+11] a) You are given traffic data (number of page hits) for n websites for some time period. (n is a large number, in the order of hundreds of thousands.) You are asked to print the top k websites with greatest amount of traffic (k is much smaller than n). Which of insertion sort, mergesort quicksort, or heapsort may be used to devise the fastest (in worst case) algorithm for this task? What would be its worst case...
solve 3
that tells how many swaps are done in the worst case given n elements Consider this modification of the partition algorithm. Randomly choose three potential pivots. Partition around the median of the three pivots 3. a) Write the pseudocode for this algorithm b) If this use the quicksort algorithm, what is the running time for the worst-case scenario? When will this happen? c) Why is this algorithm better than the regular quicksort algorithm? 4. Give the pseudocode of...
For [Select], there are three choices: worse than, the same as,
better than
Answer the following questions about the computational properties of divide-and-conquer sorting algorithms, based on tight big-Oh characterizations of the asymptotic growth rate of the functions for the running time or space size, depending on the question. Assume that the input sequence is given as a list, and the output sequence is also a list. Also assume a general implementation of the sorting algorithms, as opposed to an...
Most questions answered within 3 hours.
-
Write a simple Python program to find the day for the given
date. The procedure to...
asked 3 minutes ago -
5) A semi-permeable membrane is used to separate pyruvic acid
from an aqueous solution of 0.1...
asked 6 minutes ago -
The resistance of the body varies from approximately 500 kΩ
(when it is very dry) to...
asked 10 minutes ago -
Please explain how participation income and expenses are
allocated to each partner. Where is this defined?
asked 19 minutes ago -
The tires of a car make 61 revolutions as the car reduces its
speed uniformly from...
asked 34 minutes ago -
Peabody, Inc., sells fireworks. The company’s marketing director
developed the following cost of goods sold budget...
asked 39 minutes ago -
A signal transduction pathway includes the steps listed
below.
1. An inactive signal transduction molecule is...
asked 38 minutes ago -
1. The correlation coefficient determined for two variables has
a value of 0.89. Describe, in words,...
asked 44 minutes ago -
The following data relate to direct materials costs for
November:
Actual costs
4,700 pounds at $5.35...
asked 42 minutes ago -
Kyle, a 95.0 kg football player, leaps straight up into the air
(with no horizontal velocity)...
asked 1 hour ago -
Which of the following is a measure of profitability?
A.
Quick (acid-test) ratio
B.
Net sales...
asked 1 hour ago -
Find the total pressure exerted by 2 grams of ethane and 3 grams
of CO2 contained...
asked 1 hour ago