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.
-
Calculate the pH of a solution that is 0.650 M HOCl and 1.10 M
OCl-.
asked 4 minutes ago -
A principal randomly selects six students to take an aptitude
test, their scores are: 80.1, 75.8,...
asked 21 minutes ago -
the
wuestion is here about Amazon’s online success to the detriment of
traditional store front retailing....
asked 14 minutes ago -
A health care professional attempted to explain infant care
techniques to Iranian parents. Since the mother...
asked 22 minutes ago -
A 283 g283 g silver figure of a polar bear is dropped into the
245 g245...
asked 25 minutes ago -
. If two stocks are correctly priced according to CAPM, they
will have the same: ___A....
asked 37 minutes ago -
Below are the jersey numbers of 11 players randomly selected
from a football team. Find the...
asked 45 minutes ago -
Which of the following is NOT a specific target of
antimicrobials and antibiotics?
A)Cell wall
B)Cell...
asked 1 hour ago -
Which of the following models would provide the fastest
determination of the access cotrol privilege for...
asked 53 minutes ago -
In New England, the horizontal component of the Earth's magnetic
field has a magnitude of 2.5...
asked 1 hour ago -
In a test of hypothesis Ho: P = .31 versus Ha: P > .31 at the...
asked 1 hour ago -
Vertical Analysis of Balance Sheet
Balance sheet data for Alvarez Company on December 31, the end...
asked 1 hour ago