Suggested languages for you:

Americas

Europe

Q5SE

Expert-verifiedFound in: Page 233

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

**a) Adapt Algorithm 1 in Section 3.1 to find the maximum and the minimum of a sequence of ** ** elements by employing a temporary maximum and a temporary minimum that is updated as each successive element is examined.**

** **

**b) Describe the algorithm from part (a) in pseudocode.**

** **

**c) How many comparisons of elements in the sequence are carried out by this algorithm? (Do not count comparisons used to determine whether the end of the sequence has been reached.)**

(a) We add a variable “min” which keeps track of the minimum. We assigns the

first element as the minimum “ min” . then it checks if each element is smaller than

the maximum, the value of the element is assigned as the new value of the

maximum.

(b) procedure last largest $\left({a}_{1},{a}_{2},...{a}_{n}:\text{integers with}n\ge 2\right)$

$max:={a}_{1}$

$min:={a}_{1}$

**for** $i:=2$ **to n**

** if ${a}_{i}>max$** **then $max:={a}_{1}$ **

**if **${a}_{i}<min$** then $\mathrm{min}:={\mathrm{a}}_{1}$ **

**return **max, min

(c) $2n-2$ comparisons** **

The mentioned algorithm 1 initially assigns the first element as the maximum

“max” . Then it checks if each element is larger than the maximum , every time an

element is larger than the maximum, the value of element is assigned as the new

value of the maximum.

We will do the same for the minimum. We assigns the first element as the minimum

“min” Then it checks if each element is smaller than the maximum , every time an

element is smaller than the maximum, the value of element is assigned as the new

value of the maximum.

Let us call the algorithm “min and max” and the input of the algorithm is a list of

Integers ${a}_{1},{a}_{2},\dots ,{a}_{n}$.

**Procedure** min and max $({a}_{1},{a}_{2},\dots {a}_{n}:integerswithn\ge 2)$

The variable “max” will keep track of the largest number and variable “min” will keep

track of the smallest number .

$max:={a}_{1}$

$min:={a}_{1}$

Next we compare every(other) element in the list with the current largest number.

If the element is larger than the current largest number, then we replace the

Maximum by this element.

If the element is smaller than the current smallest number, then we replace the

Minimum by this element.

**for ** $i:=2$ **to n **

** if ${a}_{i}>max$ ** **then $max:={a}_{1}$ **

**if** ${a}_{i}<min$** then $\mathrm{min}:={\mathrm{a}}_{1}$**

Finally, we return the largest and smallest number.

**return **max, min

Combining these steps, we then obtain the algorithm:

procedure last largest $({a}_{1},{a}_{2},\dots {a}_{n}:integerswithn\ge 2)$

$max:={a}_{1}$

$min:={a}_{1}$

**for $i:=2$** **to ** *n*

** if ${a}_{i}>max$** **then $max:={a}_{1}$ **

**if ${a}_{i}<min$** ** then $min:={a}_{1}$ **

**return **max, min

The algorithm only makes a comparison when “.${a}_{i}>max$ ” and “ ${a}_{i}<min$” is

Executed, which each occurs once in every iteration of the **for – **loop and thus

There are 2 comparisons in every iteration of the **for – **loop.

Since can take on values from $2ton$ , there are $n-1$ iteration of the **for – **loop

And thus $2(n-1)=2n-2$ comparisons are made.

94% of StudySmarter users get better grades.

Sign up for free