Min-Max
Write an algorithm that finds both the smallest and
largest numbers in a list of n numbers and with complexity
T(n) is at most about (1.5)n comparisons.
- 10 Answers
- 43478 Views
- ABC, College School Exams Tests, ITC Infotech, Kyambogo University, Qatar University, I also Faced
- E-Mail Answers
Answers were Sorted based on User's Feedback
Answer / oracle
Simple, first compare all elements pairwise, total n/2
comparisons. Then, you got two sets, first set has all
greater elements, and second all smaller ones. Find largest
in the first set (n/2) and smallest in the second set
(n/2). You got both largest and smallest ones, in total n/2
+ n/2 + n/2 = 3n/2 comparisons.
| Is This Answer Correct ? | 54 Yes | 11 No |
Answer / ashekur rahman
Time Complexity T(n) <= 3n/2
Proof:
We will calculate comparison in three steps.
1) compare pairwise will divide two sub array.
2) linear search of first sub array
3) linear search of second sub array
For even number of elements,
step 1 needs n/2 comparisons where both sub array contains
n/2 number of elements. Step 2 or 3 needs (n/2 - 1)
comparisons by linear search.
T(n) = n/2 + 2(n/2 - 1)
= 3n/2 - 1
Again,
For odd number of elements,
step 1 needs (n/2 + 1) comparison.
Now if first sub array contains n/2 number of elements then
second sub array contains (n/2 + 1) number of elements
or if first sub array contains (n/2 + 1) number of elements
then second sub array contains n/2 number of elements
Therefore,
T(n) = (n/2 + 1) + (n/2 + 1 - 1) + (n/2 - 1)
= 3n/2
So, T(n) = 3n/2 - 1, if n is even number
and T(n) = 3n/2, if n is odd number
| Is This Answer Correct ? | 29 Yes | 4 No |
Answer / ashekur rahman
Please follow the link below again, where I have written a
complete C# program. Where I printed the time complexity also.
http://ashikmunna.blogspot.com/2009/05/write-algorithm-that-finds-both_28.html
| Is This Answer Correct ? | 13 Yes | 1 No |
Answer / ashekur rahman
http://ashikmunna.blogspot.com/2009/05/write-algorithm-that-finds-both.html
Please follow the link to see the answer. Where I
implemented the algorithm and also calculated the time
complexity.
Thanks.
- Ashekur Rahman
| Is This Answer Correct ? | 11 Yes | 1 No |
Answer / kush singh
1. Algorithm MaxMin (i,j, max, min)
2. // a[1:n] is a global array Parameter i and j are integers,
3. // 1 „T i „T j < n. The effect is to set max and min to the
4. // largest and smallest values in a [i, j], respectively.
5. {
6. if (i=j) then max:=min:=a[i]; //small(P)
7. else if (i = j ¡V 1) then //Another case of Small (P)
8. {
9. if a [i] < a[j] then
10. {
11. max:=a[j]; min:=a[i];
12. }
13. else
14. {
15. max:=a[i]; min:=a[j]
16. }
17. }
18. else
19. {
20. // If P is not small, divide P into subproblems
21. // Find where to split the set
22. mid:= „¾(i+j)/2„Î;
23. //Solve the subproblems
24. Maxmin (i, mid, max, min);
25. MaxMin (mid+i, j, max1, min1);
26. // Combine the solutions
27. if (max<max 1) then max:=max1;
28. if(min>min1) then min:=min1;
29. }
30. }
| Is This Answer Correct ? | 4 Yes | 0 No |
Answer / srinivasan
#include<stdio.h>
#define size 10
void main()
{
int a[size]={5,3,18,7,20,0,2,1,16,13},i,j,count=0,t,max,min;
clrscr();
for(i=0;i<size;i++)
printf("%5d",a[i]);
for(i=0,j=size-1;i<j;i++,j--)
{
count++;
if(a[i]>a[j])
{
t=a[i],a[i]=a[j],a[j]=t;
}
}
printf("\n\n");
for(i=0;i<size;i++)
printf("%5d",a[i]);
printf("\n\n");
min=a[0];
for(i=1;i<size/2;i++)
{
count++;
if(a[i]<min)
min=a[i];
}
max=a[size/2];
for(j=size/2+1;j<size;j++)
{ count++;
if(a[j]>max)
max=a[j];
}
printf("%d\n%d is max,min",max,min);
printf("\n%d\n",count);
getch();
}
| Is This Answer Correct ? | 10 Yes | 9 No |
Answer / amirhosain shahsavari
hi
Some of notations in answer 5 is absolutely wrong:
for even number n: T(n)=(3/2)n-2
for odd number n: we ignore the last item of array.Now you
can find Min1 (minimum of the array items ignoring the last
item), Max1 (maximum of the array items ignoring the last
item) (notice that n-1 is even so Min1 and Max1 can be found
at (3/2)(n-1)-2 comparisons). After that you should compare
Min1 and Max1 with the last item (that you ignored in the
first step). so you need at most (3/2)(n-1)-2+2=(3/2)n-(3/2)
comparisons to find the entire array items
| Is This Answer Correct ? | 2 Yes | 1 No |
Answer / jeya
in tree the left most elemt is minimum element.the right
most element is max element.
| Is This Answer Correct ? | 4 Yes | 7 No |
#include<iostream.h> //main() //{ class A { friend class B; public: void read(); }; class B { public : int a,b; }; void A::read() { cout<<"welcome"; } main() { A x; B y; y.read(); } In the above program......, as B is a friend of A B can have access to all members,i cant access y.read . could you please tell me the reason and what would i code to execute this program?
create a stucture student containing field for roll no,class,year and marks.create 10 student annd store them in a file
Write a program to enter 10 number of integer entries into an array n and then odds up all the odd entries. the program then displays the result. plssss answer assss fast asss u can...
i really need help about this.. write a program to display the set of odd and even numbers separately. find the highest and lowest value of the given numbers.
Write a function- oriented to convert the input dollar(s) into its equivalent peso. Assume that one dollar is equivalent to 51.60
write a c program, using for loop, that accepts and odds two numbers. The output must be the sum and the addens. This should be repeated 5 times while the first number is decremented by one and the second number is incremented by 1.
write a program that can LOCATE and INSERT elements in array using c++ programming languages.
Write a program using one dimensional array that searches a number and display the number of times it occurs on the list of 12 input values. Sample input/output dialogue: Enter 12 values: 13 15 20 13 30 35 40 16 18 20 18 20 Enter number to search: 20 Occurences: 3
#include<stdio.h> #include<conio.h> void main() { char str[10]; int,a,x,sw=0; clrscr(); printf("Enter a string:"); gets(str); for(x=0;x<=a;a++); for(x=0;x<=a;x++) { if(str[x]==str[a-1-x]) { sw=1; } else sw=0; } if(sw==10 printf("The entered string is palindrome:"); else printf("The entered string is not a palindrome:); } getch(); } wht would be the explanation with this written code???
Write a C/C++ program that connects to a MySQL server and checks if the InnoDB plug-in is installed on it. If so, your program should print the total number of disk writes by MySQL.
write a function that reverse the elements of an array in place.The function must accept only one pointer value and return void.
Definition of priority queue was given. We have to implement the priority queue using array of pointers with the priorities given in the range 1..n. The array could be accessed using the variable top. The list corresponding to the array elements contains the items having the priority as the array index. Adding an item would require changing the value of top if it has higher priority than top. Extracting an item would require deleting the first element from the corresponding queue. The following class was given: class PriorityQueue { int *Data[100]; int top; public: void put(int item, int priority); // inserts the item with the given priority. int get(int priority); // extract the element with the given priority. int count(); // returns the total elements in the priority queue. int isEmpty(); // check whether the priority queue is empty or not. }; We had to implement all these class functions.
0 Answers Nagarro, Wollega University,
C Code 
