 Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q5SE

Expert-verified Found in: Page 233 ### Discrete Mathematics and its Applications

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} then $\mathrm{min}:={\mathrm{a}}_{1}$

return max, min

(c) $2n-2$ comparisons

See the step by step solution

## (a)Step 1: Find maximum and minimum

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.

## (b)Step 2: Form Algorithm

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 $\left({a}_{1},{a}_{2},\dots {a}_{n}:integerswithn\ge 2\right)$

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} then $\mathrm{min}:={\mathrm{a}}_{1}$

Finally, we return the largest and smallest number.

return max, min

## Step 3: Write complete Algorithm

Combining these steps, we then obtain the algorithm:

procedure last largest $\left({a}_{1},{a}_{2},\dots {a}_{n}:integerswithn\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} then $min:={a}_{1}$

return max, min

## (c)Step 4: Number of comparisons

The algorithm only makes a comparison when “.${a}_{i}>max$ ” and “ ${a}_{i}” 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\left(n-1\right)=2n-2$ comparisons are made. ### Want to see more solutions like these? 