Given an specific example of a list of n integers where the running time of Quicksort...
Given an specific example of a list of n integers where the
running time of
Quicksort on them is in Ω(n2). (Assume the pivot is always chosen
at the front of a
list.)
Homework Answers
Quick Sort will have the worst performance of O(n^2) if the pivot chosen is either the the smallest or largest number. (This is because such a pivot will lead to nearly n recursions and the number of comparison in each recursion are of the order of n).
If pivot is chosen as front of list, then a sorted (or reverse sorted) list will lead to worst case complexity. (As the first element will be smallest or largest).
Add Answer to:
Given an specific example of a list of n integers where the
running time of
Quicksort...
3 Quicksort 10 points (5 points each) 1. Suppose that you are given an array A[1..n]...
3 Quicksort 10 points (5 points each) 1. Suppose that you are given an array A[1..n] and that you want to sort it using quicksort. Further suppose that your algorithm could consult an oracle to predict what element to use as the pivot. Which element would it pick so that your algorithm would run as fast as possible? What is the running time given your pivot? 2. Run the partition algorithm to partition the array A (6,7,2,4, 10,8, 1,9)
Implement quicksort and bucket sort. Use the code in your book to help; the partition in...
Implement quicksort and bucket sort. Use the code in your book to help; the partition in quicksort is tricky. Make sure your implementations are correct — it is easy to gain some confidence in the correctness of your code by writing a program which creates arrays filled with random numbers, sorts them, and then checks that they are sorted. Then time your code (using clock() or similar methods) on both methods for arrays filled with random integers of the following...
Algorithms and Basic Data Structures
This part involves writing and testing code. You are to make an experiment with 3 sorting algorithms partially given on Blackboard: Insertion sort, Mergesort, Quicksort. First, create a positive integer array of 10000 (ten thousand) elements with random values in it. Then, run the algorithms on this array by recording their running times. That is, take note of the time just before the sorting starts, and just after the sorting finishes, and record the difference. For a complete experiment, do...
You are given an array of integers, where different integers may have different numbers of digits but the total number of digits over all integers in the array is n. Show how to sort the array in in...
You are given an array of integers, where different integers may have different numbers of digits but the total number of digits over all integers in the array is n. Show how to sort the array in increasing order in O(n) time. Note: The number of integers in the array can be different for same value of n - for example the array with 2 integers 2468 and 12345 has 9 digits as well as the array with 5 integers...
5. Answer the following. (a) (5 points) Suppose you are given a maxheap of n unique...
5. Answer the following.
(a) (5 points) Suppose you are given a maxheap of n unique
numbers. Explain where will the smallest of these n numbers be
located in the maxheap. Explain where will the second largest
number be located on this maxheap. Please be specific.
(b) (5 points) Suppose you are given an array A of n numbers,
where all the elements of the array are already sorted in
decreasing order. Is this a max-heap? Explain.
(c) (5 points)...
(13 pts) Given an array AlI,2,. .. ,n] integers, design and analyze an efficient Divide-and-Conqu...
(13 pts) Given an array AlI,2,. .. ,n] integers, design and analyze an efficient Divide-and-Conquer algorithm to find some i and j, where j > 1, such that A[j]-Ali] is maximized. For example, given A 6, 1,3,8,4,5, 12,6], the maximum value of AL] - Ali] for j > i is 12-1 11 where j -7 and i 2. Give the underlying recurrence relation for your algorithm and analyze its running time. You should carefully state all details of your algorithm:...
A. What is the time complexity of Merge Sort? B. Explain why Merge Sort has the...
A. What is the time complexity of Merge Sort? B. Explain why Merge Sort has the time complexity you listed above in Part A. Algorithm Quicksort (A, left, right) if (left < right) pivot Point = [(left+right)/2] 11 note central pivot i left - 1 ja right + 1 do do it i +1 while (i < A.size) and (A[i] SA[pivot Point]) do jj-1 while (j > i) and (A[il > A[pivot Point]) if (i <j) then swap (A[i], Aljl)...
Java question Given an array of integer numbers, write a linear running time complexity program in...
Java question
Given an array of integer numbers, write a linear running time complexity program in Java to find the stability index in the given input array. For an array A consisting n integers elements, index i is a stability index in A itf ATO] + A[1] + +A[iI-1] Ali+1]+ Ali+2] +... + A[n-1]; where 0 <i< n-1 Similarly, 0 is an stability index if (A[1] A[2]A[n-1]) 0 and n-1 is an stability index if (A[0] A[1]+... A[n-21) 0 Example:...
Define a function called get_n_largest(numbers, n) which takes a list of integers and a value n...
Define a function called get_n_largest(numbers, n) which takes a
list of integers and a value n as parameters and returns a
NEW list which contains the n
largest values in the parameter list. The values in the
returned list should be in increasing order. The
returned list must always be of length n. If the number of values
in the original list is less than n, the value
None should be repeated at the end of the returned list to...
Write a JAVA method that expands a given binomial (ax + by)n, where integers a, b,...
Write a JAVA method that expands a given binomial (ax + by)n,
where integers a, b, n are user inputs. For example, if a = 2, b =
-12, n = 4 are entered the method should print or return
(2x - 12y)^4 = 16x^4 - 384x^3y + 3456x^2y^2 – 13824xy^3 +
20736y^4
Use the Pascal’s triangle method using only one 1-dim array to
calculate all binomial coefficients.
1. Write a JAVA method that expands a given binomial (ax by)",...
3 Quicksort 10 points (5 points each) 1. Suppose that you are given an array A[1..n] and that you want to sort it using quicksort. Further suppose that your algorithm could consult an oracle to predict what element to use as the pivot. Which element would it pick so that your algorithm would run as fast as possible? What is the running time given your pivot? 2. Run the partition algorithm to partition the array A (6,7,2,4, 10,8, 1,9)
You are given an array of integers, where different integers may have different numbers of digits but the total number of digits over all integers in the array is n. Show how to sort the array in increasing order in O(n) time. Note: The number of integers in the array can be different for same value of n - for example the array with 2 integers 2468 and 12345 has 9 digits as well as the array with 5 integers...
5. Answer the following.
(a) (5 points) Suppose you are given a maxheap of n unique
numbers. Explain where will the smallest of these n numbers be
located in the maxheap. Explain where will the second largest
number be located on this maxheap. Please be specific.
(b) (5 points) Suppose you are given an array A of n numbers,
where all the elements of the array are already sorted in
decreasing order. Is this a max-heap? Explain.
(c) (5 points)...
(13 pts) Given an array AlI,2,. .. ,n] integers, design and analyze an efficient Divide-and-Conquer algorithm to find some i and j, where j > 1, such that A[j]-Ali] is maximized. For example, given A 6, 1,3,8,4,5, 12,6], the maximum value of AL] - Ali] for j > i is 12-1 11 where j -7 and i 2. Give the underlying recurrence relation for your algorithm and analyze its running time. You should carefully state all details of your algorithm:...
A. What is the time complexity of Merge Sort? B. Explain why Merge Sort has the time complexity you listed above in Part A. Algorithm Quicksort (A, left, right) if (left < right) pivot Point = [(left+right)/2] 11 note central pivot i left - 1 ja right + 1 do do it i +1 while (i < A.size) and (A[i] SA[pivot Point]) do jj-1 while (j > i) and (A[il > A[pivot Point]) if (i <j) then swap (A[i], Aljl)...
Java question
Given an array of integer numbers, write a linear running time complexity program in Java to find the stability index in the given input array. For an array A consisting n integers elements, index i is a stability index in A itf ATO] + A[1] + +A[iI-1] Ali+1]+ Ali+2] +... + A[n-1]; where 0 <i< n-1 Similarly, 0 is an stability index if (A[1] A[2]A[n-1]) 0 and n-1 is an stability index if (A[0] A[1]+... A[n-21) 0 Example:...
Define a function called get_n_largest(numbers, n) which takes a
list of integers and a value n as parameters and returns a
NEW list which contains the n
largest values in the parameter list. The values in the
returned list should be in increasing order. The
returned list must always be of length n. If the number of values
in the original list is less than n, the value
None should be repeated at the end of the returned list to...
Write a JAVA method that expands a given binomial (ax + by)n,
where integers a, b, n are user inputs. For example, if a = 2, b =
-12, n = 4 are entered the method should print or return
(2x - 12y)^4 = 16x^4 - 384x^3y + 3456x^2y^2 – 13824xy^3 +
20736y^4
Use the Pascal’s triangle method using only one 1-dim array to
calculate all binomial coefficients.
1. Write a JAVA method that expands a given binomial (ax by)",...
Most questions answered within 3 hours.
-
A coach uses a new technique to train gymnasts. Seven
gymnasts were randomly selected and their...
asked 43 minutes ago -
While rotating the tires on your car you notice a rock [mass =
0.1 Kg] stuck...
asked 2 hours ago -
Using MARS simulator, write MIPS programs according to
the following scenarios: Receive a positive integer number...
asked 4 hours ago -
An object in front of a concave mirror has a real image that is
11.5 cm...
asked 4 hours ago -
Consider the reaction, C3 H8 + O2 --> CO2 + H2O. How many
moles of O2...
asked 6 hours ago -
You and your opponent both roll a fair die. If you both roll the
same number,...
asked 6 hours ago -
In a study of the accuracy of fast food drive-through orders,
Restaurant A had 257 accurate...
asked 6 hours ago -
Identify and describe in detail the four categories of
institutions that could be included in a...
asked 6 hours ago -
In python
class Customer:
def __init__(self, customer_id, last_name, first_name, phone_number, address):
self._customer_id = int(customer_id)
self._last_name =...
asked 7 hours ago -
What is an example of a limitation in implementing a new
ERP system and how it...
asked 6 hours ago -
In a section of 9.7cm of an artery with a radius of 2.6mm there
is a...
asked 6 hours ago -
the two carboxylic acid groups of aspartic acid have different
acidities with pKa values of 2.1...
asked 7 hours ago