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]
Copyright by SGLee, SKKU sglee@skku.edu