MHB Finding Min. Element in Sequence: Algo & Steps

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Element Sequence
AI Thread Summary
The discussion revolves around finding the minimum element in a sequence of numbers defined by specific conditions on their arrangement. The sequence is characterized by a pattern where each element is either a peak or a valley. The goal is to develop an algorithm that identifies the minimum element using at most ⌈n/2⌉ comparisons. The initial approach suggests comparing the first two elements to determine whether to search through odd or even indexed elements for the minimum. There is a need for clarification on the method to find the minimum among the selected elements, with a focus on whether to use a while loop or another technique. The conversation emphasizes the importance of understanding the comparison limit and the algorithm's efficiency.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hello! (Smile)

We have a sequence of numbers $A=(a_1, a_2, \dots, a_n), n \geq 3$, for which, it stands the following:

$$\forall i \text{ with } 2 \leq i \leq n-1:$$

either
$$ 1. a_{i-1}<a_i \text{ and } a_i>a_{i+1}$$

or
$$2. a_{i-1}>a_i \text{ and } a_i<a_{i+1}$$

I have to write an algorithm, that finds the minimum element of $A$ with at most $\lceil \frac{n}{2} \rceil$ comparisons.

So, we have to compare the first two elements and if the first is smaller, we will just look at the elements of the odd positions, in order to find the minimum, and if the second element is smaller we will look at the elements of the even positions, right? (Thinking)

Then, how will we find the minimum of the remaining elements we are looking at? Using a while or is there an other way? (Thinking)
 
Last edited:
Technology news on Phys.org
evinda said:
I have to write an algorithm, that finds the minimum element of $A$ with at most $\lceil \frac{n}{2} \rceil$ elements.

Do you mean $\lceil \frac{n}{2} \rceil$ comparisons?
 
magneto said:
Do you mean $\lceil \frac{n}{2} \rceil$ comparisons?

Yes, I am sorry... (Blush)
 
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.

Similar threads

Back
Top