ZuoTi.Pro
Question

Problem 1. 1. Draw the decision tree for the merge-sort algorithm for the input consisting of...

Problem 1.

1. Draw the decision tree for the merge-sort algorithm for the input consisting of 3 numbers: a, b,c.

2. Draw the 4 top levels of the decision tree for the merge-sort algorithm for the input consisting of 4 numbers: a, b, c, d

3. How may leaves does this tree have?

4. How many levels does this tree have?

5. What is the number of comparisons needed to sort these 4 numbers by the merge-sort algorithm in the worst case?

6. What is this number in the best case?

7. Is there an algorithm that in the worst case sorts 4 numbers with a smaller number of comparisons?

Justify the answers to all these questions.

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

Homework Answers

Answer #1

Please find my answer for Q1.

Please repost others in separate post.

Number of levels: 4

Number of leaves: 6

Decision tree (for 3 distinct elements) a <b worst-case number of compares yes no code between comparisons e.g, sequence of e

0 0
Add a comment
Know the answer?
Add Answer to:
Problem 1. 1. Draw the decision tree for the merge-sort algorithm for the input consisting of...
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

  • Java Merge sort algorithm

    Implement MERGE-SORT() algorithm that reads from a file named “inputHW02.txt” a list of double numbers (max = 3,000,000 numbers), sorts those numbers and indicates time consumption. This programming question will address the advantage of using iteration loops over recursive calls as well as using INSERTION-SORT() as a procedure in MERGESORT(). Your program must perform the following actions: 1. Opens the given file name and reads all double numbers. For simplicity, we assume this file only contains numbers and nothing else....

  • Draw the partial decision tree for merge sort with four distinct integers. You are not asked...

    Draw the partial decision tree for merge sort with four distinct integers. You are not asked to draw the whole decision tree, but the partial decision tree should contain at least six tree nodes.

  • 6 6. Merge Bubble Sort: a) How does the merge bubble sort break the array into...

    6 6. Merge Bubble Sort: a) How does the merge bubble sort break the array into sublists? b) What does it need to use for each sublist and then what does it do with all of the sublists? c) What is the Big-O notation for this sort? 7. Merge Sort: a) How does the merge sort use recursion to break the array into sublists? b) What happens to each of these sublists to get the final sorted list? c) What...

  • Implement MERGE-SORT() algorithm that reads from a file named “inputHW02.txt” a list of double numbers (max...

    Implement MERGE-SORT() algorithm that reads from a file named “inputHW02.txt” a list of double numbers (max = 3,000,000 numbers), sorts those numbers and indicates time consumption. This programming question will address the advantage of using iteration loops over recursive calls as well as using INSERTION-SORT() as a procedure in MERGESORT(). Your program must perform the following actions: 1. Opens the given file name and reads all double numbers. For simplicity, we assume this file only contains numbers and nothing else....

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

  • 4. Use the Insertion Sort algorithm to sort the following array in nondecreasing order. arr =...

    4. Use the Insertion Sort algorithm to sort the following array in nondecreasing order. arr = { 896 745 23 } a. Show the order of the array after every i-loop iteration. (4 points) b. How many comparisons are made for this specific array? (1 point) C. State the best, worst, and average-case performance of Insertion Sort. (1 point)

  • Part 1: Extend your sorting framework with two advanced sorting methods of your choice: (Shell Sort OR Radix Sort) AND (...

    Part 1: Extend your sorting framework with two advanced sorting methods of your choice: (Shell Sort OR Radix Sort) AND (Merge Sort OR Quick Sort). If you choose Shell Sort, experiment with different incremental sequences to see how they affect the algorithm's run time efficiency (count the number of comparisons and exchanges). If you choose to implement Radix Sort, answer the following question as well: Can you write a version of Radix Sort to work with real numbers? If yes,...

  • Here is a recursive algorithm that answers the same question as posed on Group HW3, finding...

    Here is a recursive algorithm that answers the same question as posed on Group HW3, finding the number of people who are taller than everyone before them in line. NumCanSeeRec(a1,... , an : list of n 2 1 distinct heights) (a) ifn -1 then (b return 1 (c) c= ŅumCanSeeRee(a1, , an-1) d) for i:- 1 ton- 1 (e) if a, an then return c (g) return c+1 Answer the following questions about this algorithm. Please show your work. (a)...

  • . Shell sort is a sorting algorithm similar to insertion sort. Research shell sort and apply...

    . Shell sort is a sorting algorithm similar to insertion sort. Research shell sort and apply that to the following array. Show your work in Detail. [15 points] 45 20 50 10 80 30 60 70 40 90 2. Is Shell sort a stable sorting algorithm? Answer this with an example. [10 points] 3. Apply Merge Sort to sort the following list. Show your work in Detail. [15 Points] 45 20 50 10 80 30 60 70 40 90 4....

  • Consider a variation of Merge sort called 4-way Merge sort. Instead of splitting the array into...

    Consider a variation of Merge sort called 4-way Merge sort. Instead of splitting the array into two parts like Merge sort, 4-way Merge sort splits the array into four parts. 4-way Merge divides the input array into fourths, calls itself for each fourth and then merges the four sorted fourths. a)Implement 4-way Merge sort from Problem 4 to sort an array/vector of integers and name it merge4. Implement the algorithm in the same language you used for the sorting algorithms...

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