ZuoTi.Pro
Question

2. Suppose that you are given an translating the algorithm for inputs of size 4 into a decision tree, you find that the decis

engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

There is no leaf corresponding to the permutation <3,1,2,4> which means that this algorithm cannot sort 4 numbers such that the resulting sorted order of the indexes of the four elements are <3,1,2,4>. Here I'm assuming sorting in non-decreasing order.

In this permutation the first index is 3 so, the third element of the sorted list should be the smallest number say 12. Next, we have 1, so the second smallest number should be the first element and let it be 15. Now, we have 2 so, the second number in the list should be greater than 15 let it be 17. Finally, the 4th number should be largest and let that number be 20.

So, if the input is <15,17,12,20> the algorithm cannot sort it correctly.

0 0
Add a comment
Know the answer?
Add Answer to:
2. Suppose that you are given an translating the algorithm for inputs of size 4 into...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • Suppose we have an algorithm A that does comparison-based sorting. Answer true or false for each...

    Suppose we have an algorithm A that does comparison-based sorting. Answer true or false for each of the following. Assume our input size is n, and that each of the n inputs is distinct. 1. There can be an input ordering for which algorithm A executes no more than n comparisons to determine the sorted order. 2. There can be an input ordering for which algorithm A executes no more than 2n comparisons to determine the sorted order. 3. There...

  • Write a program that inputs ten (10) integers and then sorts them in order from largest...

    Write a program that inputs ten (10) integers and then sorts them in order from largest to smallest in the programming language called Perl. You do not need to error check the input; you can assume the user enters integers. You can select the sorting algorithm of your choice, but you must implement this algorithm yourself. You cannot use a built-in sorting function. [15 points] Below is an example of a sample program run: Unsorted: 10, 4, 23, 99, 7,...

  • Write an algorithm that takes an array B and a number N as inputs. Suppose that...

    Write an algorithm that takes an array B and a number N as inputs. Suppose that the array B contains n distinct numbers. Compute the sum of the N largest numbers in the array B. Example: if the array B= [4, 5, 8, 11, 3] and N = 3, then the algorithm should return 24 (11+8+5).

  • MIPS insertion sort program......could really use some assistance

    Write a program in MIPS assembly language that implements the DESCENDING insertion sort algorithm to sort a variable-sized array of signed 32-bit integers (words)that are read from the console. Be reminded that in a descending sort, the integers are sorted from the largest to the smallest. A “special value” 99999 will beused to signify the end of the input sequence. This value is not to be considered part of the input data set. However, any value greater than 99999 that...

  • MIPS insertion sort program......could really use some assistance

    Write a program in MIPS assembly language that implements the DESCENDING insertion sort algorithm to sort a variable-sized array of signed 32-bit integers (words)that are read from the console. Be reminded that in a descending sort, the integers are sorted from the largest to the smallest. A “special value” 99999 will beused to signify the end of the input sequence. This value is not to be considered part of the input data set. However, any value greater than 99999 that...

  • 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...

  • Suppose you are given k sorted arrays of size n. Give an algorithm, that runs in...

    Suppose you are given k sorted arrays of size n. Give an algorithm, that runs in O(nk log k)time, that merges them into a single list.

  • Write a program in MIPS assembly language that implements the DESCENDING bubble sort algorithm to sort a variable-sized array of signed 32-bit integers

    Write a program in MIPS assembly language that implements the DESCENDING bubble sort algorithm to sort a variable-sized array of signed 32-bit integers (words)that are read from the console. Be reminded that in a descending sort, the integers are sorted from the largest to the smallest. A “special value” 99999 will beused to signify the end of the input sequence. This value is not to be considered part of the input data set. However, any value greater than 99999 that...

  • Full and complete answer in order to get credit. Thank you. Suppose you are given an...

    Full and complete answer in order to get credit. Thank you. Suppose you are given an unsorted list of n distinct numbers. However, the list is close to being sorted in the sense that each number is at most k positions away from its original position in the sorted list. For example, suppose the sorted list is in ascending order, then the smallest element in the original list will lie between position 1 and position k + 1, as position...

  • 1. Please write a Divide-and-Conquer Java algorithm solving the following problem: Given an "almost sorted" array...

    1. Please write a Divide-and-Conquer Java algorithm solving the following problem: Given an "almost sorted" array of distinct integers, and an integer x, return the index of x in the array. If the element x is not present in the array, return -1. "Almost sorted" means the following. Assume you had a sorted array A[0…N], and then split it into two pieces A[0…M] and A[M+1…N], and move the second piece upfront to get the following: A[M+1]…A[N]A[0]…A[M]. Thus, the "almost sorted"...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT