Suppose you have an array of n elements containing three distinct keys, true, false, and maybe....
Suppose you have an array of n elements containing three distinct keys, true, false, and maybe. Give an O(n) algorithm to rearrange the list so that all false elements precede the maybe elements, which in turn precede all true elements. You may use only constant extra space.
Homework Answers
![Program void My-sort (ElemType A [ ], int M) int Counter [3] / using constant_extra_space int a, b, ci for (a 0 a <3 at+ Counter[a 0; for (a 0, a < M; at+) // initializing counters // increment respective counter for each key if (A[a]false) Counter [0]++ if (A[a] maybe) else else Counter [1] +; Counter [2] +; // resetting keys for (a = 0; a < Counter [0]; a++) A [a] false; c += Counter [0]; for (a 0 a <Counter [1]; a++) AIca]maybe; C + Counter [1]; for (a 0 a < Counter [2]; at+) A [c + a] true;](http://img.homeworklib.com/questions/77b6aa00-d14d-11ea-abd1-edf46135c979.png?x-oss-process=image/resize,w_560)
Add Answer to:
Suppose you have an array of n elements containing three
distinct keys, true, false, and maybe....
6. Give an efficient algorithm to rearrange an array of n keys so that all negative...
6. Give an efficient algorithm to rearrange an array of n keys so that all negative keys precede all nonne- gative keys. Your algorithm must be in-place meaning you cannot allocate another array to temporarily hold the items.
Suppose that you are given an array of N elements. Develop an optimum algorithm that finds...
Suppose that you are given an array of N elements. Develop an optimum algorithm that finds the minimum k elements of this array in at most nlogn time. Try your algorithm on an example N-sized array and some value of k.
the programming language is in java Problem 2 You are given an array A with n...
the
programming language is in java
Problem 2 You are given an array A with n distinct elements. Implement an (n log n)-time algorithm that creates an array B where all elements are in range from 0 to n - 1 and where the order of elements is the same as in A. That is, 0 has the same index in B as the smallest element in A, 1 has the same index in B as the second smallest element...
1. Suppose that an array al] is a max-heap that contains the distinct integer keys 1,...
1. Suppose that an array al] is a max-heap that contains the distinct integer keys 1, 2,.., N with N> 7. The key N must be in gl1] and the key N-1 must be in either al2) or al3) a. Give all possible positions for the key N-2 as a function of N. b. Repeat the same question for the key 2
3. Suppose you have an array of n random elements. You are required to perform n...
3. Suppose you have an array of n random elements. You are required to perform n different searches on the array. What is best big-oh time for your entire task? Explain how to achieve that time. 4. Suppose you are given two sorted integer arrays int[] A and int[] B. Write a method that returns an array which contains only the common elements (elements that are present in both A and B) of these two sorted arrays. Indicate the big-Oh...
5. A three-heap with n elements can be stored in an array A, where A[O] contains...
5. A three-heap with n elements can be stored in an array A, where A[O] contains the root of the tree. a) Draw the three-heap that results from inserting 5, 2, 8, 3, 6, 4, 9, 7, 1 in that order into an initially empty three-heap. You do not need to show the array representation of the heap. You are only required to show the final tree, although if you draw intermediate trees. b) Assuming that elements are placed in...
4. (10 points) Suppose we are given a sequence S of n elements, each of which...
4. (10 points) Suppose we are given a sequence S of n elements, each of which is colored red or blue. Assuming S is represented by an array, give a linear-time in-place algorithm for ordering S so that all the blue elements are listed before all the red elements. What is the running time of your method?
I need help In the lecture you got acquainted with the median algorithm, which calculates the median of an unsorted array with n∈N elements in O (n). But the algorithm can actually do much more: it is...
I need help In the lecture you got acquainted with the median algorithm, which calculates the median of an unsorted array with n∈N elements in O (n). But the algorithm can actually do much more: it is not limited to finding only the median, but can generally find the ith element with 0≤i <n. Implement this generic version of the median algorithm by creating a class selector in the ads.set2.select package and implementing the following method: /** * Returns the...
def slice_list(lst: List[Any], n: int) -> List[List[Any]]: """ Return a list containing slices of <lst> in...
def slice_list(lst: List[Any], n: int) -> List[List[Any]]: """ Return a list containing slices of <lst> in order. Each slice is a list of size <n> containing the next <n> elements in <lst>. The last slice may contain fewer than <n> elements in order to make sure that the returned list contains all elements in <lst>. === Precondition === n <= len(lst) >>> slice_list([3, 4, 6, 2, 3], 2) == [[3, 4], [6, 2], [3]] True >>> slice_list(['a', 1, 6.0, False],...
Suppose we have an array that contains tuples. These tuple contains three positive numbers. Implement an...
Suppose we have an array that contains tuples. These tuple contains three positive numbers. Implement an algorithm that counts how many distinct tuple that an array has(contains same number in same order). ex) [(1, 2, 1), (2, 2, 2), (3, 8, 3), (1, 2, 1), (3, 4, 3)] gives 4. 1 The algorithm should be implemented in Python3. 2 The function must have average-case runtime of O(n). You can assume Simple Uniform Random Hashing. 3 Python built-in dictionary cannot be...
6. Give an efficient algorithm to rearrange an array of n keys so that all negative keys precede all nonne- gative keys. Your algorithm must be in-place meaning you cannot allocate another array to temporarily hold the items.
the
programming language is in java
Problem 2 You are given an array A with n distinct elements. Implement an (n log n)-time algorithm that creates an array B where all elements are in range from 0 to n - 1 and where the order of elements is the same as in A. That is, 0 has the same index in B as the smallest element in A, 1 has the same index in B as the second smallest element...
1. Suppose that an array al] is a max-heap that contains the distinct integer keys 1, 2,.., N with N> 7. The key N must be in gl1] and the key N-1 must be in either al2) or al3) a. Give all possible positions for the key N-2 as a function of N. b. Repeat the same question for the key 2
5. A three-heap with n elements can be stored in an array A, where A[O] contains the root of the tree. a) Draw the three-heap that results from inserting 5, 2, 8, 3, 6, 4, 9, 7, 1 in that order into an initially empty three-heap. You do not need to show the array representation of the heap. You are only required to show the final tree, although if you draw intermediate trees. b) Assuming that elements are placed in...
4. (10 points) Suppose we are given a sequence S of n elements, each of which is colored red or blue. Assuming S is represented by an array, give a linear-time in-place algorithm for ordering S so that all the blue elements are listed before all the red elements. What is the running time of your method?
Most questions answered within 3 hours.
-
How much must I invest today if I want to withdraw 1/3 of my
original investment...
asked 37 minutes ago -
What is meant by a “term premium”?
What can explain such a premium? Is it a...
asked 2 hours ago -
23. Which molecule has only covalent bonds? A. CO2 B. Al2O3 C.
Mg3N2
24. The octet...
asked 2 hours ago -
the
total pressure for a mixture of N2O4 and NO2 is 2.20 atm. If Kp=
7.10...
asked 2 hours ago -
Delaware Corp. prepared a master budget that included $22,385
for direct materials, $28,600 for direct labor,...
asked 2 hours ago -
For pesticide HCB (hexachlorobenzene), its logarithmic partition
coefficient log Kow is 5.6. What would be the...
asked 2 hours ago -
A chemist requires 0.422 mil Na2CO3 for a reaction. How many
grams does this correspond to?
asked 2 hours ago -
If the vapor pressure of carvone is approximately 9.4 torr at 99
°C, approximately how much...
asked 3 hours ago -
A juice bottling company is carrying out a test at 10%
significance that the mean population...
asked 3 hours ago -
What is the reflectivity (in percent) needed to keep water at a
temperature near its freezing...
asked 3 hours ago -
Suppose that the average surface temperature of Earth is 300K.
Assume this is uniform over its...
asked 3 hours ago -
Draw the condensed structural formula for alkenes and alkynes or
the line-angle structural formula for cycloalkenes...
asked 3 hours ago