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

List all the steps used to search for 9 in the sequence 1, 3, 4, 5, 6, 8, 9, 11 using
a) A linear search. b) A binary search.

This type of algorithm is also known as Sequential Search because it follows a particular path in a pre-defined sequence, whenever it is executed.

A linear search algorithm starts by comparing two variables, that is x and a_1.If x = a₁, it implies that outcome is the location of a_1.Only iff, if x ≠ a_1,then next search should be executed, which is, if x = a_2,it implies that outcome is the location of a_2.

This process of sequential search continues to execute until a match of the required result is found.

According to given question,

The sequence is 1, 3, 4, 5, 6, 8, 9, 11 and we need to search for the element 9.

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

Step 1

Comparing x = a₁⇒ 9 = a₁

Step 2

Substituting a₁ = 1.

Step 3

1 does not match 9

Step 4

Comparing x = a₂⇒ 9 = a₂

Step 5

Substituting a₂ = 3.

Step 6

3 does not match 9

Step 7

Comparing x = a₃⇒ 9 = a₃

Step 8

Substituting a₃ = 4

Step 9

4 does not match 9

Step 10

Comparing x = a₄⇒ 9 = a₄

Step 11

Substituting a₄ = 1.

Step 12

5 does not match 9

Step 13

Comparing x = a₅⇒ 9 = a₅

Step 14

Substituting a₅ = 6

Step 15

6 does not match 9

Step 16

Comparing x = a₆⇒ 9 = a₆

Step 17

Substituting a₆ = 8.

Step 18

8 does not match 9

Step 19

Comparing x = a₇⇒ 9 = a₇

Step 20

Substituting a₇ = 9.

Step 21

9 matches with 9

Therefore, by linear search 9 is contained at the 7^thelement in the sequence.

Subpart (b)Answer

A binary search algorithm is when the searching list of elements has monotonically increasing terms. Its mechanism works by comparing the element which is to be locates to the middle term of the list while breaking or splitting the list into further small smaller sub lists of the same size. This process continues by bringing down the sub list based on the comparison of the elements which is to be located.

According to the question,

The given sequence is 1, 3, 4, 5, 6, 8, 9, and 11

Step 23

Split the sequence in half. 1,3,4,5 and 6, 8, 9, 11

Step 24

5 is the maximum of the sequence of 1, 3, 4, 5

Step 25

5 is less than 7.

Thus, 7 is not in the sequence 1,3,4,5. Therefore, discarding the sequence 1,3,4,5.

Step 26

Split the sequence 6, 8,9,11 in half. 6, 8 and 9, 11

Step 27

It is clear that 8 is the maximum of the sequence amongst 6,8 and 7 is less than 8

Step 28

Thus 7 is not in the sequence 6,8. Therefore discarding the sequence 6,8

Step 29

Split the sequence 9, 11 in half . 9 and 11

Step30

9 is the maximum of the sequence 9 and it is not greater than 9

Step 31

Thus 9 is not in the sequence of 11.

Step 32

We have sequence 9 remaining.

Step 33

Since, 9 is equal to 9, location of 9 is determined in the sequence as 7^th element.

Therefore, the obtained 9 is the 7^thelement of the sequence 1,3,4,5,6,8,9,11.

Select your language

Discrete Mathematics and its Applications