AExercise 16. Develop an efficient in-place algorithm called Partition-Even-Odd(A) that partitions an array A in even and odd numbers. The algorithm must terminate with A containing all its even elements preceding all its odd elements. For example, for input A = (7, 17, 74, 21, 7, 9, 26, 10), the result might be A = (74, 10, 26, 17, 7, 21, 9, 7). Partition-Even-Odd must be an in-place algo, which means that it may use only a constant memory space in addition to. In practice, A this means that you may not use another temporary array. Question 1: Write the pseudo-code for Partition-Even-Odd.
AExercise 16. Develop an efficient in-place algorithm called Partition-Even-Odd(A) that partitions an array A in even and odd numbers. The algorithm must terminate with A containing all its even elements preceding all its odd elements. For example, for input A = (7, 17, 74, 21, 7, 9, 26, 10), the result might be A = (74, 10, 26, 17, 7, 21, 9, 7). Partition-Even-Odd must be an in-place algo, which means that it may use only a constant memory space in addition to. In practice, A this means that you may not use another temporary array. Question 1: Write the pseudo-code for Partition-Even-Odd.
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
![▲Exercise 15. Consider the following max-heap
H= (37, 12, 30, 10, 3, 9, 20, 3, 7, 1, 1, 7, 5)
Write the exact output of the following Extract-All algorithm run on H
Extract-All(H)
Heap-Extract-Max(H)
1
while H. heap-size > 0
1 if H. heap-size > 02
k=H[1]
Heap-Extract-Max (H)
for i=1 to H. heap-size
output H[i] 4
output "." end-of-line 5
return k
3 H[1] =H[H. heap-size]
H. heap-size=H. heap-size-1
Max-Heapify(H)
23456
Answer:](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F8d98f69c-4cd2-4f3d-87b5-f9613d57a0bc%2Fe1133ea5-8dbc-4e22-8cf3-d5552618bb52%2F6yp0l9p_processed.jpeg&w=3840&q=75)
Transcribed Image Text:▲Exercise 15. Consider the following max-heap
H= (37, 12, 30, 10, 3, 9, 20, 3, 7, 1, 1, 7, 5)
Write the exact output of the following Extract-All algorithm run on H
Extract-All(H)
Heap-Extract-Max(H)
1
while H. heap-size > 0
1 if H. heap-size > 02
k=H[1]
Heap-Extract-Max (H)
for i=1 to H. heap-size
output H[i] 4
output "." end-of-line 5
return k
3 H[1] =H[H. heap-size]
H. heap-size=H. heap-size-1
Max-Heapify(H)
23456
Answer:
![AExercise 16. Develop an efficient in-place algorithm called Partition-Even-Odd(A) that
partitions an array A in even and odd numbers. The algorithm must terminate with A containing
all its even elements preceding all its odd elements. For example, for input A = (7, 17, 74, 21,
7, 9, 26, 10), the result might be A = (74, 10, 26, 17, 7, 21, 9, 7). Partition-Even-Odd must be
an in-place algo, which means that it may use only a constant memory space in addition to. In
practice, A this means that you may not use another temporary array.
Question 1: Write the pseudo-code for Partition-Even-Odd.
Question 2: Characterize the complexity of Partition-Even-Odd. Briefly justify your answer.
Question 3: Formalize the correctness of the partition problem as stated above, and prove that
Partition-Even-Odd is correct using a loop-invariant.
Question 4: If the complexity of your algorithm is not already linear in the size of the array, write a
new algorithm Partition-Even-Odd-Optimal with complexity O(N) (with N= |A|).](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F8d98f69c-4cd2-4f3d-87b5-f9613d57a0bc%2Fe1133ea5-8dbc-4e22-8cf3-d5552618bb52%2Fer583s_processed.jpeg&w=3840&q=75)
Transcribed Image Text:AExercise 16. Develop an efficient in-place algorithm called Partition-Even-Odd(A) that
partitions an array A in even and odd numbers. The algorithm must terminate with A containing
all its even elements preceding all its odd elements. For example, for input A = (7, 17, 74, 21,
7, 9, 26, 10), the result might be A = (74, 10, 26, 17, 7, 21, 9, 7). Partition-Even-Odd must be
an in-place algo, which means that it may use only a constant memory space in addition to. In
practice, A this means that you may not use another temporary array.
Question 1: Write the pseudo-code for Partition-Even-Odd.
Question 2: Characterize the complexity of Partition-Even-Odd. Briefly justify your answer.
Question 3: Formalize the correctness of the partition problem as stated above, and prove that
Partition-Even-Odd is correct using a loop-invariant.
Question 4: If the complexity of your algorithm is not already linear in the size of the array, write a
new algorithm Partition-Even-Odd-Optimal with complexity O(N) (with N= |A|).
Expert Solution
![](/static/compass_v2/shared-icons/check-mark.png)
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps with 2 images
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
![C How to Program (8th Edition)](https://www.bartleby.com/isbn_cover_images/9780133976892/9780133976892_smallCoverImage.gif)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
![Database Systems: Design, Implementation, & Manag…](https://www.bartleby.com/isbn_cover_images/9781337627900/9781337627900_smallCoverImage.gif)
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
![Programmable Logic Controllers](https://www.bartleby.com/isbn_cover_images/9780073373843/9780073373843_smallCoverImage.gif)
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education