In this task an algorithm is to be developed that searches for minimal elements in partially

ordered sets $).$ For the definition of partial orders and minimal elements we refer to exercise

G$4.($a$)$ Give an example of a partially ordered set $($M$)$ with at least two different minimums

elements. Also indicate the minimal elements and justify that they are indeed minimal. $($

b$)$ Give pseudocode for an algorithm MinElements that takes as input a finite partially ordered

set $(M$ with $M=$ninN elements and outputs all minimal elements in the set. Your

algorithm should call the ordering relation at most $n^2$ times.

Justify Your design Note: You can:

the set $M$ as an array $[$M$[0],..,$ M$[$n $-1]].$

use the ordering relation without implementing it$.$

$($c$)$ Prove the correctness of the algorithm you provided.

$($d$)$ Discuss a way to reduce the number of calls to the ordering relation below $n^2.$ Does this reduction

always apply $($worst case$)$ or only on average $($average case$)?$

$($e$)$ Prove: If a partially ordered set $(M,-$ has a smallest element, then this is uniquely

determined.

$($f$)$ Prove: In a totally ordered set $(M,<mtext></mtext><mi>)</mi>$ every minimal element is also a smallest element.