Chapter 4  Algorithms

4.1  Introduction

4.2  Examples of Algorithms

4.3  Analysis of Algorithms Problem

4.4  Recursive Algorithms

The term algorithm is a corruption of the name al-Khowarizmi, a mathematician of the ninth century, whose book on Hindu numerals is the basis of modern decimal notation. Originally, the word algorism was used for the rules for performing arithmetic using decimal notation. Algorism evolved into the word algorithm by the eighteenth century.

A+: 10%   A: 10%    B+: 15%   B: 15%    C+: 15%  C: 15%   D, F: 20%

4  Algorithms

An algorithm is a step-by step method for performing a computation or for solving a problem.

4.1  Introduction

Algorithms have the following characteristics:

Input : An algorithm has input values from a set.

Output : From each set of input an algorithm produces output from a set.

The output values are the solution to the problem.

Definiteness : The steps of an algorithm must be defined precisely.

Effectiveness : It must be possible to perform each step of an algorithm exactly and in a finite amount of time.

Finiteness : An algorithm should produce the desired output after a finite number of steps for any input in the set.

Correctness : An algorithm should produce the correct output values for each set of

input values.

Generality : The procedure should be applicable for all problems of the desired form,

not just for a particular set of input values.

Pseudocode  -> Appendix C

 Algorithm  1.1 Algorithm that find the maximum of three numbers , and This algorithm fields the largest of the numbers , and .      Input :  , ,     Output :  large (the largest of , and )  1.   2.     3.    is larger than , update    4.            5.     is larger than , update  6.            7.     return  8.

 Algorithm  1.2 Finding the Maximum Value in a Finite Sequence procedure max(, , : integers)  max  for to        if then  return                  or

4.2  Examples of Algorithms

Searching : The problem of locating an element in an ordered list occurs in many contexts.

The first algorithm that we will present is called the linear search, or sequential search, algorithm.

If the entire list has been searched without locating x, the solution is 0. The pseudocode for the linear search algorithm is displayed as Algorithm 2.1.

 Algorithm  2.1 Linear Search Algorithm

THE BINARY SEARCH We will now consider another searching algorithm.

This algorithm can be used when the list has terms occurring in order of increasing size

(for instance: if the terms are numbers, they are listed from smallest to largest; if they are words, they are listed in lexicographic, or alphabetic, order).

This second searching algorithm is called the binary search algorithm.

EXAMPLE 3

 Algorithm 2.2 The Binary Search Algorithm procedure binary search ( : integer, , , : increasing integers)   { is left endpoint of search interval}   { is right endpoint of search interval}  while              if then       else  if then location  else location return

Sorting

Sorting is putting these elements into a list in which the elements are in increasing order.

Sorting is putting these elements into a list in which the elements are in increasing order. For instance,

sorting the list 7, 2, 1, 4, 5, 9 produces the list 1, 2, 4, 5, 7, 9. Sorting the list d, h, c, a, f (using alphabetical order)

produces the list a, c, d, f, h. An amazingly large percentage of computing resources is devoted to sorting one thing or another.

Hence, much effort has been devoted to the development of sorting algorithms.

The Bubble sort is one of the simplest sorting algorithms, but not one of the most efficient.

EXAMPLE 4  Use the bubble sort to put 3, 2, 4, 1, 5 into increasing order.

The insertion sort is a simple sorting algorithm, but it is usually not the most efficient.

The input to insertion sort is

, , .

The sequence is to sort the data in nondecreasing order.

At the iteration of insertion sort, the first part of the sequence

, ,

will have been rearranged so that it is sorted.

Insertion sort then inserts in

, ,

so that

, , ,

is sorted.

EXAMPLE 5 Insertion Sort

Example

Insertion Sort

Suppose that and , , is

If is , after it is inserted , , becomes

Procedures

To insert in

We first compute and .

is greater then , moves one index to the right

We second compute with .

is greater then , moves one index to the right

We next compute with .

is less then or equal to , we insert to the second index

This subsequence is now sorted.

 Algorithm  2.3 Insertion Sort procedure insertion sort(, , , : real numbers with ) for to          while                     for to               {, , , is in increasing order}

Time and Space for Algorithms

It is important to know or be able to estimate the time and space required by algorithm.

 Best-case-time  The input sequence is already sorted in nondecreasing order, (input value)        will always be false.  The body of the while loop will never be executed.   Worst-case-time  The input sequence is sorted in decreasing order, (input value)      will be true.   The while loop will execute the maximum number of times.

Relaxation the requirements of an algorithm

Finiteness

An operating system never terminates

Determinism

Algorithms for multiprocessor machine or distributed environment are rarely deterministic

Generality or Correctness

Many practical problem are too difficult to be solved efficiently

Randomized Algorithm

A randomized algorithm does not require that the intermediate of each step of execution be uniquely defined and depend only on the inputs and results of the preceding steps.

By definition, when a randomized executes, at some points it makes random choices. In practice, a pseudorandom number generator is used.

We shall assume the existence of a function

,

which returns a random integer between the integers and , inclusive.

 Algorithm  2.4 Shuffle  - skip procedure change(, , : values of denominations of coins, where   ; : a positive integer) for to       { counts the coins of denomination used}     while       {add a coin of denomination }       { is the number of coins of denomination in the change for }

Example  2.5

Suppose that the sequence

is input to shuffle.

Assume that the values of rand are

,   ,   ,

Solution

We first swap and where and .

If After the swap we have

Next, . If . After the swap we have

Next, . If . The sequence is unchanged.

Finally, . If . The sequence is again unchanged.

The output depends on the random choices made by the random number generator.

Exercises  1, 4

4.3  Analysis of Algorithms Problem-

Solving Corner: Design and Analysis of an Algorithm

Useless program for certain type of input

even though derived from a correct algorithm

the time needed to run the program is too big or

the space needed to hold the data is too big.

Example

a set of elements some elements are labeled 'red', some labeled 'black'.

Find the number of subsets of that contain at least one red item.

Since a set that has elements has subsets, the program would require at least units of time to execute.

What if is very big?

The time needed to execute an algorithm is a function of the input. Instead of dealing directly with the input, we use parameters that characterize the size of the input.

For example,

The input is a set containing elements.      The size of the input is .

 Best-case-time: We can ask for the minimum time needed to execute the algorithm among all inputs of size .  This time is the best-case-time for inputs of size .   Worst-case-time: We can ask for the maximum time needed to execute the algorithm among all inputs of size .  This time is the worst-case-time for inputs of size .   Average-case time: Another important case is average-case time that the average time needed to execute  the algorithm over some finite set of inputs all of size .

 Example 3.1 A reasonable definition of the size of input for Algorithm that finds the largest value in a finite sequence is the number of elements in the input sequence. A reasonable definition of the execute time is the number of iterations of the while loop. With these definitions, For Algorithm for input of size             the loop is always executed time             the worst-case, best-case and average-case times are each .

We are in how the best-case or worst-case time grows as the size of the input increases.

How the best-case or worst-case time grows as the size of input increase. For example, suppose an algorithm is

for input of size . For large , the term is approximately equal to (see Table ). In this case grows like .

 Definition  3.2 Let and be functions with domain .      is big oh of       is of order at most                     is positive constant such that          is omega of     is of order at least                       is positive constant such that          is theta of       is of order                       and

Definition can be loosely paraphrased as follows:

 if, except for a constant factor and a finite number of exceptions,   is bounded above by .   is an asymptotic upper bound for .     if, except for a constant factor and a finite number of exceptions,   is bounded below by .   is an asymptotic lower bound for .     if, except for constant factors and a finite number of exceptions,   is bounded above and below by .   is an asymptotic tight bound for .

THE HISTORY OF BIG-O NOTATION

Big-O notation has been used in mathematics for more than a century. In computer science it is widely used in the analysis of algorithms,

The German mathematician Paul Bachmann first introduced big-O notation in 1892 in an important book on number theory.

The use of big-O notation in computer science was popularized by Donald Knuth,

who also introduced the big-omega and big-theta notations defined in this section.

 Example  3.3 Show that .

Solution

Since

( not, fix it as    ... + 2n^5 = 23 n^5)   for all ,

Taking   C_1 =23   in Definition to obtain

.

Since

for all ,

Taking in Definition to obtain

.

Therefore,

and

.

 Theorem  3.4 Prove that , is a polynomial in of degree , where each is nonnegative.

Proof

Show that .

Let

.

Then, for all ,

Therefore, .

We show that .

For all

, where .

Therefore, .

and       .

 Example  3.5 Show that   3n^2 + 8n lg n= Theta(n^2)  .

Solution

(the logarithm of to the base ).

Since   for all ,

for all .

Thus

3n^2 + 8n lg n= O(n^2)

Also,

for all .

Thus

3n^2 + 8n lg n= Omega(n^2)

Therefore

3n^2 + 8n lg n= Theta(n^2)

 Example  3.6 Show that .

Solution

Therefore

.

Now

.

,    .

Therefore,

.

Hence,

Therefore,

and       .

 Example  3.7 Prove that for all .

Solution

Show that .

, .

Taking , we obtain

.

Show that .

.

Taking , we obtain      .

Hence

and       .

 Example  3.8 Prove that for all .

Solution

Show that .

, .

Taking , we obtain

.

Show that .

.

Taking , we obtain

.

Hence

and .

 Example  3.9 Prove that .

Solution

Show that .

.

Taking , we obtain

.

Show that .

.

Taking , we obtain

.

Hence

and       .

 Example  3.10 Show that  if and then .

Solution

By definition of , is constants such that

,   .

By definition of , is constants such that

,

Therefore

,

Therefore, .

 Definition  3.11 If an algorithm requires units of time to terminate in the best case for an input    of size and ,  The best-case time required by the algorithm is of order at most .  Test-case time required by the algorithm is .    If an algorithm requires units of time to terminate in the worst case for an input   of size and ,  The worst-case time required by the algorithm is of order at most .  The worst-case time required by the algorithm is .    If an algorithm requires units of time to terminate in the average case for an      input of size and ,  The average-case time required by the algorithm is of order at most .  The average-case time required by the algorithm is .

 Example  3.12 Algorithm is unit of time to terminate in the worst case for inputs of size .  We showed in Example .  Thus the worst-case time required by this algorithm is .

 Example  3.13

 Algorithm  3.17 Searching an Unordered Sequence Given the sequence and a value , this algorithm returns the index of .  If is not found, the algorithm returns .     Input : sequence and (the value to search for)    Output : The index of , or if is not found,  1. linear_search (, , key)  2.   for to  3.      if(key )  4.        return // successful search  5.   return // unsuccessful search  6.

 Algorithm  3.19 Matrix Multiplication This algorithm computes the product of the matrices and directly from the definition of matrix multiplication.     Input:  , ,   Output:  , the product of and   matrix_product(, , )    for to        for to                 for to            *                return

TABLE 3.3 Common growth functions.

 Theta Form Name Theta Form Name Constant Quadratic Log log Cubic Log Polynomial Linear Exponential n log n Factorial

 Expression Name Estimate Reference Polynomial Theorem Arithmetic() Example Sum of Powers Example Factorial Example

Exercises  1,7,10,13,16,19,33

4.4  Recursive Algorithms

Example 4.4.1

Algorithm  4.2  Computing Factorial

 Algorithm  4.2 Computing Factorial This non-recursive algorithm computes .     Input:  , an integer greater than or equal to   Output:   1. factorial()  2.     3.    for to  4.    *  5.    return  6.

 Theorem  4.3 Algorithm returns the value of , .

Proof

Basis Step ()

Taking ,

Inductive Step

[Assume that Algorithm correctly returns the value of , .]

Suppose is input to Algorithm .

Since , when we execute the function in Algorithm we proceed to line .

By the inductive assumption,

the function correctly computes the value of .

At line ,

the function correctly computes the value .

Therefore, Algorithm correctly returns the value of for every integer .

 Example  4.5 A robot can takes of meters or meters. We write an algorithm to calculate the number of ways the robot can walk meters.

As examples:

 Distance Sequence of Steps Number of Ways to Walk , or ,, or , or 2, ,,, or ,,2 or ,2, or 2,, or 2,2

is the number of ways the robot can walk meters.

,

.

The robot begins by taking a step of meters or a step of meters.

The robot begins by taking a meter step      a distance of meters remains.

The remainder of the walk can be completed in ways.

The robot begins by taking a meter step      a distance of meters remains.

The remainder of the walk can be completed in ways.

The walk must begin with either a meter or a meter step, all the ways to walk meters are accounted for.

We obtain

.

Recursive algorithm to compute is

The base cases are and .

 Algorithm  4.6 Robot Walking This algorithm computes the function defined by     Input :    Output :   walk()   walk()      if         return      return

The sequence

, , ,

whose values begin

is related to the Fibonacci sequence.

The Fibonacci sequence is defined by the equations

for all .

The Fibonacci sequence begins

.

Since

and

,    for all .

it follows that

for all .

 Example  4.7 Use mathematical induction to show that    for all .

Solution

Basis step

.

Inductive step

and prove case

The definition of the Fibonacci numbers

for all .

The given equation is true for all .

Exercises 1, 5, 27

Exercises  1, 4, 8, 11, 14, 16, 19, 25        [End of Ch. 3]