Using Oz Programming Language: (a) Write an Oz function which has at its input a
ID: 3757552 • Letter: U
Question
Using Oz Programming Language:
(a) Write an Oz function which has at its input a list of integers and returns the maximum element. For example, {Max [3 ~2 0 4 5 1]} should return 5. The optimal algorithm for determining the maximum element of a list with N elements is doing N-1 comparisons.
(b) Write an Oz function which has at its input a list of integers and returns the first two maximum elements. For example, {Max [3 ~2 0 4 5 1]} should return 5 and 4. What is the optimal number of comparisons needed?
Explanation / Answer
Answer :
Pseudo code:
1. You can use some kind of sorting, to sort the ArrayList, I would advise quick sort.
2. You can simply return the last element
*This will most probably take O(n logn) time complexity.*
// second method
1. traverse the ArrayList, define max;
2.Check if the element coming is greater than max
3.Replace max
4. At the end of the loop return max;
*This will most probably take O(n) time complexity.*
class Test{
int Oz(ArrayList<Integer> a){
int max=Integer.MIN_VALUE;
for(int i=0;i<a.size();a++){
if(max<a.get(i)){
max=a.get(i);
}
}
}
return max;
}
The optimal no. of comaprisions needed is n.
int [] 0z(ArrayList<Integer>arr)
{
int a[2],i,max1,max2;
max1=arr.get(0),max2=arr(1);
for(i=1;i<arr.size();i++)
{
if(arr.get(i)>max1)
{
max2=max1;
max1=arr.get(i);
}
else if(arr.get(i)>max2 && arr.get(i)!=max1)
max2=arr.get(i);
else if(max1==max2)
max2=arr.get(i);
}
a[0]=max1;
a[1]=max2;
return a;
}
*It needs at least N-1 comparisons if the largest 2 elements are at the beginning of the array and at most 2N-3 in the worst case (one of the first 2 elements is the smallest in the array).*
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.