Book edition 7th

Author(s) Kenneth H. Rosen

Pages 808 pages

ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.

Short Answer

a) Describe an algorithm for locating the last occurrence of the largest number in a list of integers.
b) Estimate the number of comparisons used.

(a) procedure last largest $(a_{1}, a_{2}, \dots a_{n} " : integerswith " n \geq 2)$

$m a x : = a_{1}$

$p o s i t i o n : = 1$

for $i : = 2$ to n

if $a_{i} > m a x$ then

$m a x : = a_{1}$

$p o s i t i o n : = 1$

return position

$(b) n - 1, O (n)$

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

(a)Step 1: Write algorithm

Let us call the algorithm "last largest" and the input of the algorithm is a list of

integers $a_{1}, a_{2}, \dots, a_{n}$ .

procedure last largest $(a_{1}, a_{2}, \dots a_{n} : i n t e g e r s w i t h n \geq 2)$

The variable "max" will keep track of the largest number and then variable "position"

will keep track of the position of the largest number. We initially define the maximum

as the first element.

$m a x : = a_{1}$

$p o s i t i o n : = 1$

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

the element is larger than (or equal, since we are interested in the last occurrence)

the current largest number, then we replace the maximum by this element.

$f o r i : = 2 t o n$

$i f a_{i} \geq m a x t h e n$

$m a x : = a_{i}$

$p o s i t i o n : = i$

Finally, we return the position of the last occurrence of the largest number.

return position

Step 2: Algorithm

Combining these steps, we then obtain the algorithm:

procedure last largest $(a_{1}, a_{2}, \dots a_{n} : i n t e g e r s w i t h n \geq 2)$

role="math" localid="1668488545991" $m a x : = a_{1} p o s i t i o n : = 1 f o r i = 2 t o n i f a_{i} \geq m a x t h e n m a x : = a_{1} p o s i t i o n : = 1$

return position

(b) Step 3: Number of comparisons

The algorithm only makes a comparison when $a_{i} \geq m a x$ is executed, which

occurs in every iteration of the for-loop. Since can take on values from $2 t o n$ ,

there are $n - 1$ iterations of the for-loop and thus $n - 1$ comparisons are made, while $n - 1 i s O (n)$ .

Find Study Materials for

Create Study Materials

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

a) Describe an algorithm for locating the last occurrence of the largest number in a list of integers.
b) Estimate the number of comparisons used.

Step by Step Solution

(a)Step 1: Write algorithm

Step 2: Algorithm

(b) Step 3: Number of comparisons

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

a) Describe an algorithm for locating the last occurrence of the largest number in a list of integers.b) Estimate the number of comparisons used.

Step by Step Solution

(a)Step 1: Write algorithm

Step 2: Algorithm

(b) Step 3: Number of comparisons

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Decision Maths

Calculus

Probability and Statistics

Statistics

Mechanics Maths

Geometry

Pure Maths

a) Describe an algorithm for locating the last occurrence of the largest number in a list of integers.
b) Estimate the number of comparisons used.