DEFINITION 1. An algorithm is a finite set of precise instructions for performing a computation or for solving a problem.

Example 1: Describe an algorithm for finding the maximum (largest) value in a finite sequence of integers.

SOLUTION:

1. Set the temporary maximum equal to the first integer in the sequence.

2. Compare the next integer in the sequence to the temporary maximum, and if it is larger than the temporary maximum, set the temporary maximum equal to this integer.

3. Repeat the previous step if there are more integers in the sequence.

4. Stop when there are no integers left in the sequence. The temporary maximum at this point is the largest integer in the sequence.

Look at Appendix 2 for the details of the pseudocode used in Rosen’s book.

ALGORITHM 1 Finding the Maximum Element in a finite sequence.

procedure max(a₁, a₂, …, a_n: integers)

max:= a₁

for i:= 2 to n

if max < a_i then max:= a_i

{max is the largest element}

Properties of algorithms:

INPUT

OUTPUT

PRECISENES

CORRECTNESS

FINITENESS

EFFECTIVENESS

GENERALITY

SEARCH ALGORITHMS

GENERAL SEARCHING PROBLEM:

Locate an element x in a list of distinct elements a₁, a₂, …, a_n, or determine that it is not in the list. The solution to this search problem is the location of the term in the list that equals x (that is, i is the solution if x = a_i) and is 0 if x is not in the list.

ALGORITHM 2 THE LINEAR SEARCH ALGORITHM

procedure linear search(x: integer, a₁, a₂,…, a_n: distinct integers)

i := 1

while (i £ n and x ¹ a_i)

i := i + 1

if i £ n then location := i

else location := 0

{location is the subscript of term that equals x, or is 0 if x is not found}

AN EXAMPLE OF THE BINARY SEARCH ALGORITHM: Search for 19 in the list

1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22

SOLUTION:

1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22

12 13 15 16 18 19 20 22

18 19 20 22

18 19

ALGORITHM 3 THE BINARY SEARCH ALGORITHM

procedure binary search(x: integer, a₁, a₂,…, a_n: distinct integers)

i := 1 {i is left endpoint of search interval}

j := n {j is left endpoint of search interval}

while i < j

begin

m = ë(i+j)2û

if x > a_m then i := m + 1

else j := m

end

if x = a_i then location := i

else location := 0

{location is the subscript of term that equals x, or is 0 if x is not found}