[Acua] Consider the following array: 8, 9, 17, 4, 3, 20, 25, 5 Show a trace...

 

Transcribed Image Text:

[Acuña] Consider the following array: 8, 9, 17, 4, 3, 20, 25, 5 Show a trace of execution for top-down mergesort using the method shown in lecture (where both sides are updated at once). Illustrate the contents of the array as it is broken down, and then merged into an ordered state. Enter each subsequent state as a comma separated list (as shown by the initial state). Do not include any spaces or brackets in your answer. If you follow these directions exactly and are marked off by the auto-grader, reach out to the instructional staff. 1 (initial): 8,9,17,4,3,20,25,5 (given as example) 2 (down): 8,9,17,4,3,20,25,5 (given as example; nothing changed!) 3 (down): 4 (mid): 5 (up): 6 (up): 7 (up): Question 2 0.5 pts How (in general) are priority queues related to other sorting algorithms? Both priority queues and the other four sorting algorithms must obey the lower bound proof. Priority queues are more efficient implementation of insertion sort. ○ They both involve comparing elements, and PQs may be used to create a straightforward sorting algorithm. O Priority queues are implementations of the same ADT that the sorting algorithms use. Question 3 1.5 pts [Acuña] Consider the following values: 5, 9, 1, 5, 6, 2, 5, 6, 9, 10. Select a valid binary heap for this data. 5 о 10 10 5 Question 4 [Acuña] Is your answer to the previous question unique? Explain. No - the same nodes can be used to draw multiple valid heaps. Yes - the previous question had only one answer. No - the nodes can also be arranged to fit the BST ordering rule. Yes - these nodes can only be used to draw a specific tree. 1 pts Question 5 1.5 pts [Acuña/Morris] Consider the following priority queue array: [0, 8, 6, 7, 4, 4, 4, 5, 1, 3, 1]. Which of the diagrams below accurately represents it? Remember: The first element of the array is never used. A B C D A B 7 0.5 pts [Acuña] Suppose that you are inserting a node with value 4 into the max PQ show below. When it is initially added, which position (see lettered nodes) does it have in the heap/tree? Question 6 10 5 m 0 O O F О 0 D ய E A О B Question 7 0.5 pts [Acuña] What is the Tilde approximation order of the following code fragment? Assume that you are measuring the number of comparisons (less) and that n represents the number of nodes in the heap. private void sink(int k) { while (2 k < N) { int j = 2*k; if (j < N && less(j, j+1)) j++; if (!less (k, j)) break; exch(k, j); k = j; } ~(logn)^2 ~(1/2)n ~logn Does not exist, or cannot be determined with information given. ~(1/2)logn [Acuña] Consider the following array: 8, 9, 17, 4, 3, 20, 25, 5 Show a trace of execution for top-down mergesort using the method shown in lecture (where both sides are updated at once). Illustrate the contents of the array as it is broken down, and then merged into an ordered state. Enter each subsequent state as a comma separated list (as shown by the initial state). Do not include any spaces or brackets in your answer. If you follow these directions exactly and are marked off by the auto-grader, reach out to the instructional staff. 1 (initial): 8,9,17,4,3,20,25,5 (given as example) 2 (down): 8,9,17,4,3,20,25,5 (given as example; nothing changed!) 3 (down): 4 (mid): 5 (up): 6 (up): 7 (up): Question 2 0.5 pts How (in general) are priority queues related to other sorting algorithms? Both priority queues and the other four sorting algorithms must obey the lower bound proof. Priority queues are more efficient implementation of insertion sort. ○ They both involve comparing elements, and PQs may be used to create a straightforward sorting algorithm. O Priority queues are implementations of the same ADT that the sorting algorithms use. Question 3 1.5 pts [Acuña] Consider the following values: 5, 9, 1, 5, 6, 2, 5, 6, 9, 10. Select a valid binary heap for this data. 5 о 10 10 5 Question 4 [Acuña] Is your answer to the previous question unique? Explain. No - the same nodes can be used to draw multiple valid heaps. Yes - the previous question had only one answer. No - the nodes can also be arranged to fit the BST ordering rule. Yes - these nodes can only be used to draw a specific tree. 1 pts Question 5 1.5 pts [Acuña/Morris] Consider the following priority queue array: [0, 8, 6, 7, 4, 4, 4, 5, 1, 3, 1]. Which of the diagrams below accurately represents it? Remember: The first element of the array is never used. A B C D A B 7 0.5 pts [Acuña] Suppose that you are inserting a node with value 4 into the max PQ show below. When it is initially added, which position (see lettered nodes) does it have in the heap/tree? Question 6 10 5 m 0 O O F О 0 D ய E A О B Question 7 0.5 pts [Acuña] What is the Tilde approximation order of the following code fragment? Assume that you are measuring the number of comparisons (less) and that n represents the number of nodes in the heap. private void sink(int k) { while (2 k < N) { int j = 2*k; if (j < N && less(j, j+1)) j++; if (!less (k, j)) break; exch(k, j); k = j; } ~(logn)^2 ~(1/2)n ~logn Does not exist, or cannot be determined with information given. ~(1/2)logn

Answer rating: 100% (QA)

Answer 1 initial 2131637231225 2 down 2131637231225 3 down 2131637231225 4mid 2131637231225 5up 2133... View the full answer