DM-Ch-4-Lab -- Sage

Chapter 4 Algorithms

그림입니다.
원본 그림의 이름: CLP000113981201.bmp
원본 그림의 크기: 가로 417pixel, 세로 201pixel

그림입니다.
원본 그림의 이름: CLP000113980001.bmp
원본 그림의 크기: 가로 144pixel, 세로 105pixel

[References]

1. Discrete Math - 7th Edition , Richard Johnsonbaugh, Pearson

Chapter 4 Algorithms

그림입니다.
원본 그림의 이름: CLP000113980005.bmp
원본 그림의 크기: 가로 168pixel, 세로 192pixel

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 algorismwas 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%

Table of Contents

(DM Ch. 1, Sets and Logic, Lecture Note) http://matrix.skku.ac.kr/2018-DM/Ch-1/
DM-Ch-1-Lab http://math1.skku.ac.kr/home/pub/2651/ (Use Chrome browser, not IE)
(DM Ch. 1, 동영상강의)
Discrete Math 이산수학 Ch 0 Introduction https://youtu.be/9ahFnOFTWNQ
Discrete Math 이산수학 Ch 1, 1.1, 1.2 Propositions https://youtu.be/QgdKqmCFW2Y
Discrete Math 이산수학 Ch 1, 1.3, 1.4 Rules of Inference https://youtu.be/92siPfThf0M
Discrete Math 이산수학 Ch 1, 1.5, 1.6 Nested Quantifiers https://youtu.be/7M7w9eX5D0Q

(DM Ch. 2, Proofs, Lecture Note) http://matrix.skku.ac.kr/2018-DM/Ch-2/
DM-Ch-2-Lab    http://math1.skku.ac.kr/home/pub/2652/
     (DM Ch. 2, 동영상강의)
DM Ch 2 Lecture 1 Sec 2.1, 2.2 2.2 More Methods of Proof Problem   https://youtu.be/xEMkHb2AkYk
DM Ch 2 Lecture 2 Sec 2.4, 2.5 Math Induction and Well-Ordering Property https://youtu.be/areatkjOjcg

(DM Ch. 3, Functions, Sequences, and Relations, Lecture Note) http://matrix.skku.ac.kr/2018-DM/Ch-3/
http://math1.skku.ac.kr/home/pub/2653/
     (DM Ch. 3, 동영상강의)
DM 이산수학 Ch 3, Functions, Sequences, and Relations 1 https://youtu.be/MhM_9ZuGAis
DM 이산수학 Ch 3, Functions, Sequences, and Relations 2 https://youtu.be/ZjAtN9HkZwM
DM 이산수학 Ch 3, Functions, Sequences, and Relations 3 https://youtu.be/Uuwsx2aiEPI

Ch 4, Algorithms, Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-4/
DM-Ch-4-Lab http://math1.skku.ac.kr/home/pub/2654/
(DM Ch. 4, 동영상강의)
DM 이산수학 Ch 4,
...

[Week 6] Ch 5, Introduction to Number Theory (if time permits) - Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-5/
(DM Ch. 5, 동영상강의)
DM 이산수학 Ch 5,

Ch 6, Counting Methods and the Pigeonhole Principle (lightly covered) - Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-6/
(DM Ch. 6, 동영상강의)
DM 이산수학 Ch 6,

Ch 7, Recurrence Relations, - Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-7/
(DM Ch. , 동영상강의)
DM 이산수학 Ch ,

Ch 8, Graph Theory (if time permits), - Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-8/
(DM Ch. , 동영상강의)
DM 이산수학 Ch ,

Ch 9, Trees (if time permits), - Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-9/
(DM Ch. , 동영상강의)
DM 이산수학 Ch ,

10 Network Models (if time permits)
11 Boolean Algebras and Combinatorial Circuits (if time permits)
12 Automata, Grammars, and Languages (if time permits)
13 Computational Geometry (if time permits)
Appendix

Ch - Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-10/
(DM Ch. , 동영상강의)
DM 이산수학 Ch ,

...
...

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 )

3. is larger than , update

5. is larger than , update

7. return

Algorithm 1.2

Finding the Maximum Value in a Finite Sequence

procedure max(, , : integers)

max

for to

if then

return

그림입니다.
원본 그림의 이름: CLP000113980002.bmp
원본 그림의 크기: 가로 797pixel, 세로 365pixel

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

그림입니다.
원본 그림의 이름: CLP000113980007.bmp
원본 그림의 크기: 가로 894pixel, 세로 698pixel

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.

그림입니다.
원본 그림의 이름: CLP000113980008.bmp
원본 그림의 크기: 가로 909pixel, 세로 1084pixel

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

그림입니다.
원본 그림의 이름: CLP00011398000a.bmp
원본 그림의 크기: 가로 942pixel, 세로 531pixel

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 .

그림입니다.
원본 그림의 이름: CLP00011398000b.bmp
원본 그림의 크기: 가로 512pixel, 세로 207pixel

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

for all ,

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

그림입니다.
원본 그림의 이름: CLP00011398000c.bmp
원본 그림의 크기: 가로 938pixel, 세로 530pixel

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

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

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

그림입니다.
원본 그림의 이름: CLP00011398000e.bmp
원본 그림의 크기: 가로 310pixel, 세로 273pixel

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()

3. for to

4. *

5. return

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()

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

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

Copyright @ 2018 SKKU Matrix Lab. All rights reserved.
Made by Manager: Prof. Sang-Gu Lee and Dr. Jae Hwa Lee
*This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2017R1D1A1B03035865).