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

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.                                               

● 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.

 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 }

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

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, .                                               

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.

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

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:

 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 .      

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]

http://matrix.skku.ac.kr/sglee/vita/LeeSG.htm