For this task, save your work in MinMax.java Consider the following problem: given an array of n numbers, we want to find both the minimum and the maximum of these numbers. For such a problem, we often measure the cost in terms of the number of comparisons made-that is, if we compare any two numbers from the input, that's one comparison. As an example, the following algorithm requires n-1 comparisons: // assume a.length > 0 int maxArray(int[] a) { int maxSoFar = a[0]; for (int i=1;i
For this task, save your work in MinMax.java Consider the following problem: given an array of n numbers, we want to find both the minimum and the maximum of these numbers. For such a problem, we often measure the cost in terms of the number of comparisons made-that is, if we compare any two numbers from the input, that's one comparison. As an example, the following algorithm requires n-1 comparisons: // assume a.length > 0 int maxArray(int[] a) { int maxSoFar = a[0]; for (int i=1;i
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
![For this task, save your work in MinMax.java
Consider the following problem: given an array of n numbers, we want to find both the minimum
and the maximum of these numbers. For such a problem, we often measure the cost in terms of the
number of comparisons made-that is, if we compare any two numbers from the input, that's one
comparison.
As an example, the following algorithm requires n-1 comparisons:
// assume a.length > 0
int maxArray(int[] a) {
int maxSoFar = a[0];
for (int i=1;i<a.length; i++) {
}
}
if (a[i]
maxSoFar)
maxSoFar = a[i]%;B
return maxSoFar;
This is because in an array a of length n, only a[1], a[2],..., a[n-1] are compared with our maxSoFar
in the if statement. Notice that a[0] is not involved in the if statement.
You can use this algorithm to the find the maximum value and an almost-identical algorithm to
find the minimum value. However, you'll need 2n-2 comparisons (n-1 for max and another n - 1 for
min). Only comparisons between input integers (either directly or indirectly) matter here, which is why
we don't count comparisons made by i<a.length in the above example. Your goal in this problem is to
do better!
Subtask I: First, implement a function
public static double minMaxAverage (int[] numbers) {
// your code goes here
int myMin = ...;
int myMax =
return (myMin + myMax)/2.0;
}
that takes in an array of integer numbers, finds the minimum and the maximum among these numbers,
and returns the average of the minimum and the maximum (as the code above shows). For full credit, if
input contains n numbers, your function must use fewer than 3n/2 comparisons.
Subtask II: As a comment block in your code file, make a logical argument-as close to an airtight
mathematical proof as possible-for why your code is indeed using strictly fewer than 3n/2 comparisons.
(Hint: Remember the maximum-number problem from class? What happens after one round in the
pairing-up algorithm?)](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Ff97c0725-689e-40d7-87a0-46553d65cfc3%2F585db04c-a461-41f9-ba1f-5247517fe58a%2F4kdjjhb_processed.png&w=3840&q=75)
Transcribed Image Text:For this task, save your work in MinMax.java
Consider the following problem: given an array of n numbers, we want to find both the minimum
and the maximum of these numbers. For such a problem, we often measure the cost in terms of the
number of comparisons made-that is, if we compare any two numbers from the input, that's one
comparison.
As an example, the following algorithm requires n-1 comparisons:
// assume a.length > 0
int maxArray(int[] a) {
int maxSoFar = a[0];
for (int i=1;i<a.length; i++) {
}
}
if (a[i]
maxSoFar)
maxSoFar = a[i]%;B
return maxSoFar;
This is because in an array a of length n, only a[1], a[2],..., a[n-1] are compared with our maxSoFar
in the if statement. Notice that a[0] is not involved in the if statement.
You can use this algorithm to the find the maximum value and an almost-identical algorithm to
find the minimum value. However, you'll need 2n-2 comparisons (n-1 for max and another n - 1 for
min). Only comparisons between input integers (either directly or indirectly) matter here, which is why
we don't count comparisons made by i<a.length in the above example. Your goal in this problem is to
do better!
Subtask I: First, implement a function
public static double minMaxAverage (int[] numbers) {
// your code goes here
int myMin = ...;
int myMax =
return (myMin + myMax)/2.0;
}
that takes in an array of integer numbers, finds the minimum and the maximum among these numbers,
and returns the average of the minimum and the maximum (as the code above shows). For full credit, if
input contains n numbers, your function must use fewer than 3n/2 comparisons.
Subtask II: As a comment block in your code file, make a logical argument-as close to an airtight
mathematical proof as possible-for why your code is indeed using strictly fewer than 3n/2 comparisons.
(Hint: Remember the maximum-number problem from class? What happens after one round in the
pairing-up algorithm?)
Expert Solution
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
Recommended textbooks for you
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)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
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)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education