MHB Algorithm with ceil(n/2) comparisons

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Algorithm
AI Thread Summary
The discussion revolves around designing an efficient algorithm to find the minimum element in a strictly alternating sequence of numbers, defined by specific conditions for the sequence's elements. The algorithm aims to achieve this with at most ⌈n/2⌉ comparisons. Participants explore various implementations, focusing on initializing the minimum value based on comparisons between the first two elements. The algorithm iterates through the array, skipping every other element to reduce the number of comparisons. Key points include the realization that tracking the index of the minimum value is more efficient than storing the value itself. The final analysis clarifies that the number of comparisons needed aligns with the expected complexity of ⌈n/2⌉, whether n is even or odd. The discussion emphasizes the importance of simplicity in coding for clearer analysis and correctness, ultimately confirming the algorithm's efficiency in finding the minimum element in the alternating sequence.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hello! (Wave)

I am looking at the following exercise:

We say that a sequence of numbers $A=(a_1,a_2, \dots, a_n) , n \geq 3$, is strictly alternating if for each $i$, with $2 \leq i \leq n-1$, one of the following conditions stands:

  • $a_{i-1}< a_i$ and $a_i>a_{i+1}$
    $$$$
  • $a_{i-1}>a_i$ and $a_i<a_{i+1}$

For example, the sequences $(2,10,5,6,3,11,-1,7,4)$ and $(2,-7,4,3,6,0,33,2)$ are alternating, but the sequnce $(5,6,7,3,4,-2,7,10)$ isn't.

Design an algorithm, that, given an alternating sequence of numbers $A$, executes at most $\lceil \frac{n}{2} \rceil$ comparisons, in order to calculate the minimum element of $A$. Justify your answer.

I wrote the following code:

Code:
#include <stdio.h>

int main()
{
int n,i,min,position_min;
printf("Give n: \n");
scanf("%d",&n);
while (n<3){
   printf("	Give an other value for n: \n");
   scanf("%d", &n);
}
int A[n];
for (i=0; i<n; i++){
     printf("Give the value of the %dth position of the array: \n",i+1);
     scanf("%d",&A[i]);
}
min=A[0];
position_min=0;
if (A[1]<min) {
    min=A[1];
    position_min=1;
}
for (i=position_min+2; i<n; i+=2){
    if (A[i]<min){
       min=A[i];
       position_min=i;
    }
}
printf("min=%d \n ",min);
return 0;
}

So, we need $2 \left ( \frac{n-\text{position_min}-2+1}{2} \right )=n-\text{position_min}-1$ comparisons..But.. we don't need $\lceil \frac{n}{2} \rceil$ comparisons, at the algorithm I wrote.. (Sweating)

How could I do it otherwise? :confused:
 
Technology news on Phys.org
If the first number is smaller than the second then you have the indecies are even. Otherwise they are odd.

You don't need to store the value of the element but rather you store the index.

For example :

Code:
A = {4,6,5,7,3,8,2}  
Then min is initialized to 0 since 4 <6.  counter =2;
Since A[min]<A[counter] , min stays 0;
Counter = counter+2 = 4;
Since A[min]>A[counter] min=4;
Counter = counter+2=6;
Since A[min]>A[counter] min=6;
Counter = counter+2=8 > length(A)
Hence min = 6 and the minimum is A[6]=2;

Since each time we travel almost to the end of the array and we skip one element at a time we expect the complexity to be $$\frac{n}{2}$$.Fore the case were the first element is greater than the second initialize min=1 and counter = 3.
 
ZaidAlyafey said:
If the first number is smaller than the second then you have the indecies are even. Otherwise they are odd.

You don't need to store the value of the element but rather you store the index.

For example :

Code:
A = {4,6,5,7,3,8,2}  
Then min is initialized to 0 since 4 <6.  counter =2;
Since A[min]<A[counter] , min stays 0;
Counter = counter+2 = 4;
Since A[min]>A[counter] min=4;
Counter = counter+2=6;
Since A[min]>A[counter] min=6;
Counter = counter+2=8 > length(A)
Hence min = 6 and the minimum is A[6]=2;

Since each time we travel almost to the end of the array and we skip one element at a time we expect the complexity to be $$\frac{n}{2}$$.Fore the case were the first element is greater than the second initialize min=1 and counter = 3.

So, at this for loop:

Code:
for (i=position_min+2; i<n; i+=2){
    if (A[i]<min){
       min=A[i];
       position_min=i;
    }
}

we don't need to write the command:
Code:
position_min=i;
, right? (Thinking)

So,should it be like that? :confused:

Code:
#include <stdio.h>

int main()
{
int n,i,min,j;
printf("Give n: \n");
scanf("%d",&n);
while (n<3){
   printf("	Give an other value for n: \n");
   scanf("%d", &n);
}
int A[n];
for (i=0; i<n; i++){
     printf("Give the value of the %dth position of the array: \n",i+1);
     scanf("%d",&A[i]);
}
min=A[0];
j=0;
if (A[1]<min) {
    min=A[1];
    j=1;
}
for (i=j+2; i<n; i+=2){
    if (A[i]<min){
       min=A[i];
    }
}
printf("min=%d \n ",min);
return 0;
}
 
Generally we are not interested in the element but rather the index so we have

Code:
if(A[0] < A[1])
    min=0;
else
    min=1;

for(counter = min+2; counter < n ; counter+=2)
    if(A[counter] < A[min])
          min = counter;

printf("The minimum is %d ", A[min]);
 
ZaidAlyafey said:
Generally we are not interested in the element but rather the index so we have

Code:
if(A[0] < A[1])
    min=0;
else
    min=1;

for(counter = min+2; counter < n ; counter+=2)
    if(A[counter] < A[min])
          min = counter;

printf("The minimum is %d ", A[min]);

So, we need $n-min-2+1=n-min-1=\left\{\begin{matrix}
\frac{n-1}{2} &, min=0 \\
\\
\frac{n-2}{2} & ,min=1
\end{matrix}\right.$ comparisons, right? (Thinking)

But.. how can we show that we need $ \lceil \frac{n}{2} \rceil$ comparisons? :confused:
 
Just don't bother only checking the last element if min = 0, do it every time. It doesn't affect correctness, and makes your code simpler to analyze, because in that case you simply have this number of comparisons:

$$1 + \left ( \left \lfloor \frac{n}{2} \right \rfloor - 1 \right ) + (n \bmod 2) = \left \lfloor \frac{n}{2} \right \rfloor + (n \bmod 2)$$

Where the first $1$ is the initial comparison, the second term is the for loop (note that you must subtract $1$ because you've already processed the first two elements) and the final $n \bmod 2$ is because we need one more comparison if $n$ is odd for the last element.

If $n$ is even, then this gives:

$$\frac{n}{2} = \left \lceil \frac{n}{2} \right \rceil$$

And if $n$ is odd, then this gives:

$$\frac{n - 1}{2} + 1 = \frac{n + 1}{2} = \left \lceil \frac{n}{2} \right \rceil$$

And so you are done. Sometimes it pays off to not be too clever :)
 
Thread 'Is this public key encryption?'
I've tried to intuit public key encryption but never quite managed. But this seems to wrap it up in a bow. This seems to be a very elegant way of transmitting a message publicly that only the sender and receiver can decipher. Is this how PKE works? No, it cant be. In the above case, the requester knows the target's "secret" key - because they have his ID, and therefore knows his birthdate.
I tried a web search "the loss of programming ", and found an article saying that all aspects of writing, developing, and testing software programs will one day all be handled through artificial intelligence. One must wonder then, who is responsible. WHO is responsible for any problems, bugs, deficiencies, or whatever malfunctions which the programs make their users endure? Things may work wrong however the "wrong" happens. AI needs to fix the problems for the users. Any way to...
Back
Top