程序代写代做代考 python algorithm CS1010S Programming Methodology

CS1010S Programming Methodology

Lecture 3
Recursion, Iteration &

Order of Growth

29 Aug 2018

Python Problems?
cs1010s-staff@googlegroups.com

1 2 3 4 5 6 R 7 8 9 10 11 12 13 14 15

Le
ve

Week

Expected Level Progression

Max Level

Typical Level

Minimum Level

M
id

te
rm

T
e

st
Week

1 2 3 4 5 6 R 7 8 9 10 11 12 13

Difficulty Curve

Reinforcements
Remedial classes

• Every week

• 6:30 – 8:30 pm

• Watch Coursemology for updates

Done with all the
missions?

Got a lot of time to burn?

Optional Trainings

Contests
Due 9 Sep 2018

Winning: 400 EXP + Prize
Participation: 50 EXP

Recap

Inputs Function Output

Don’t need to know how it works
Just know what it does

(the inputs
and output)

Learning Outcomes
After this lesson, you should be able to

• know how apply divide and conquer technique to solve a
problem

• differentiate what is recursion and iteration

• state the order of growth in terms of time and space for
computations

Divide
&

Conquer

Problem

Sub-
problem 1

Sub-
problem 2

Sub-sub
problem 3

Sub-sub
problem 4

Key Insight:
Smaller problems
are easier to solve

What is Recursion
Smaller child problem(s) has
same structure as the parent

A recursive function is
defined as itself

e.g. 𝑓 𝑛 = ⋯𝑓 𝑚 ⋯

Analogy
Your friend is late for lecture…

Caryn
last seen today at 10:10am

Eh where are you?

Ahh… I’m late! Trying to
catch a zulbat.

Pls help me chope seat. Tell
me which row and col ur at

10:10AM

How to find your row?
The Strategy

• Your row number is 1 more than the row in front of you.

• Ask the person in front for his/her row number and add 1 to it.

• The person in front uses the same strategy.

• Eventually, person in front row simply replies 1.

This is Recursion

Example
Consider the factorial function:

𝑛! = 𝑛 × 𝑛 − 1 × (𝑛 − 2)⋯× 1

Rewrite:

𝑛! = ቊ
𝑛 × 𝑛 − 1 ! , 𝑛 > 1

1 , 𝑛 ≤ 1

Factorial

𝑛! = ቊ
𝑛 × 𝑛 − 1 ! , 𝑛 > 1

1 , 𝑛 ≤ 1

def factorial(n):

if n <= 1: return 1 else: return n * factorial(n – 1) Recursion def factorial(n): if n <= 1: return 1 else: return n * factorial(n – 1) Function that calls itself is called a recursive function terminating condition recursive call Recursive process factorial(5) 5 * factorial(4) 5 * (4 * factorial(3)) 5 * (4 * (3 * factorial(2)) 5 * (4 * (3 * (2 * factorial(1))) 5 * (4 * (3 * (2 * 1))) 5 * (4 * (3 * 2)) 5 * (4 * 6) 5 * 24 120 Note the build up of pending operations. Recursion n n - 1 computed with n - 2 computed with 2 computed with 1 computed with Terminating condition Answer is trivial How to write recursion 1. Figure out the base case - Typically n = 0 or n = 1 2. Assume you know how to solve n – 1 - Now how to solve for n? Factorial: Linear recursion def factorial(n): if n <= 1: return 1 else: return n * factorial(n – 1) factorial(4) factorial(3) factorial(2) factorial(1) Fibonacci Numbers Leonardo Pisano Fibonacci (12th century) is credited for the sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, … Note: each number is the sum of the previous two. Fibonacci in Math 𝑓𝑖𝑏(𝑛) = ቐ 0, 𝑛 = 0 1, 𝑛 = 1 𝑓𝑖𝑏 𝑛 − 1 + 𝑓𝑖𝑏(𝑛 − 2) 𝑛 > 1

Fibonacci in Python

𝑓𝑖𝑏(𝑛) = ቐ
0, 𝑛 = 0
1, 𝑛 = 1

𝑓𝑖𝑏 𝑛 − 1 + 𝑓𝑖𝑏(𝑛 − 2) 𝑛 > 1

def fib(n):

if (n == 0):

return 0

elif (n == 1):

return 1

else:

return fib(n – 1) + fib(n – 2)

Tree recursion

leaves

root
fib(5)

fib(4) fib(3)

fib(3) fib(2)

fib(1)

fib(2) fib(1)

fib(0) 1

1 0

fib(1) fib(0)

1 0

fib(2)

fib(1) fib(0)

fib(1)

1 0

Mutual recursion
def ping(n):

if (n == 0):

return n

else:

print(“Ping!”)

pong(n – 1)

def pong(n):

if (n == 0):

return n

else:

print(“Pong!”)

ping(n – 1)

ping(10)

Ping!

Pong!

Ping!

Pong!

Ping!

Pong!

Ping!

Pong!

Ping!

Pong!

Iteration
the act of repeating a process with the

aim of approaching a desired goal, target
or result.

– Wikipedia

Iterative Factorial
Idea

Start with 1, multiply by 2, multiply by 3, … , multiply by n.
𝑛! = 1 × 2 × 3⋯× 𝑛

Product

1 ×2624120
Counter

12345

Iterative Factorial
𝑛! = 1 × 2 × 3⋯× 𝑛

Computationally
Starting:

product = 1
counter = 1

Iterative (repeating) step:
product  product × counter
counter  counter + 1

End:
product contains the result

Iterative Factorial
Start with 1, multiply by 2, multiply by 3, …

𝑛! = 1 × 2 × 3⋯× 𝑛

Python Code
def factorial(n):

product, counter = 1, 1

while counter <= n: product = product * counter counter = counter + 1 return product while loop while :

expression
• Predicate (condition) to stay within the loop

body
• Statement(s) that will be evaluated if predicate is True

Yet another way
𝑛! = 1 × 2 × 3⋯× 𝑛

Factorial rule:

product  product × counter

counter  counter + 1

def factorial(n):

product = 1

for counter in range(2, n+1):

product = product * counter

return product

non-inclusive.
Up to n.

for loop
for in :

sequence
• a sequence of values

var
• variable that take each value in the sequence

body
• statement(s) that will be evaluated for each value in the sequence

range function
range([start,] stop[, step])

creates a sequence of integers
• from start (inclusive) to stop (non-inclusive)
• incremented by step

Examples
for i in range(10):

print(i)

for i in range(3, 10):

print(i)

for i in range(3, 10, 4):

print(i)

break & continue
for j in range(10):

print(j)

if j == 3:

break

print(“done”)

for j in range(10):

if j % 2 == 0:

continue

print(j)

print(“done”)

done

Break out
of loop

Continue with
next value

Iterative process
def factorial(n):

product, counter = 1, 1

while counter <= n: product = (product * counter) counter = counter + 1 return product factorial(6) counter > n (7 > 6)
return product (720)

product counter

1 1

1 2

2 3

6 4

24 5

120 6

720 7

Recursion
vs

Iteration

Recursive process occurs when there
are deferred operations.

Iterative process does not have
deferred operations.

Recursive Process
factorial(5)

5 * factorial(4)

5 * (4 * factorial(3))

5 * (4 * (3 * factorial(2))

5 * (4 * (3 * (2 * factorial(1)))

5 * (4 * (3 * (2 * 1)))

5 * (4 * (3 * 2))

5 * (4 * 6)

5 * 24

120
deferred
operations

Orders of Growth

Like Physicists, we care about two
things:

1. Space
2. Time

Rough measure of resources
used by a computational process

Space: how much memory do we need to
run the program

Time: how long it takes to run a program

Order of growth
Why do we care?

We want to know how much
resource our algorithm needs

Analogy
Suppose you want to buy a Blu-ray movie
from Amazon (~40GB)

Two options:
1. Download

2. 2-day Prime Shipping

Which is faster?

Buying the Entire Series
What if you want more movies?

• 8 Blu-ray discs

• ~320 GB

Which is faster?

1. Download, or

2. 2-day delivery

Even more movies?

Download vs Delivery

# of movies

Time

Delivery2 days

Download

1 hour

We want to ask questions like:
factorial(5) → factorial(10) ?

fib(10) → fib(20)?

How much more time?

How much more space?
2x?
Same?
4x?

Order of Growth is NOT the absolute
time or space a program takes to run

Order of Growth is the proportion of
growth of the time/space of a

program w.r.t. the growth of the
input

Formal Definition
Let n denote size of the problem.

Let 𝑅 𝑛 denote the resources needed.

Definition:

𝑅 𝑛 has order of growth Θ(𝑓 𝑛 ) written

𝑅 𝑛 = Θ(𝑓 𝑛 )

If there are positive constants 𝑘1 and 𝑘2 such that

𝑘1𝑓 𝑛 ≤ 𝑅(𝑛) ≤ 𝑘2𝑓(𝑛)

for any sufficiently large value of 𝑛

Diagram

For 𝑛 >= 𝑛0, 𝑅(𝑛) is sandwiched between

O(𝑓(𝑛))

(𝑓(𝑛))

(𝑓(𝑛))

Some common 𝑓(𝑛)
• 1

• 𝑛

• 𝑛2

• 𝑛3

• log 𝑛

• 𝑛 log 𝑛

• 2𝑛

Intuitively
If 𝑛 is doubled

(i.e. increased to 2𝑛)

then 𝑅(𝑛)

(the resource required),

is increased to 𝑓(2𝑛)

Another analogy
• Suppose you can run 10 m in 1.5 secs

• Time is linear to distance

20 m
100 m

10 m

20 m

Shuttle Run
• Run and return

• Time is _______ to distance

10 m

Recap: Recursive Factorial
def factorial(n):

if n <= 1: return 1 else: return n * factorial(n – 1) Order of growth? 1. Time 2. Space Recursive process factorial(5) 5 * factorial(4) 5 * (4 * factorial(3)) 5 * (4 * (3 * factorial(2)) 5 * (4 * (3 * (2 * factorial(1))) 5 * (4 * (3 * (2 * 1))) 5 * (4 * (3 * 2)) 5 * (4 * 6) 5 * 24 120 • Time  #operations • Linearly proportional to n Recursive process factorial(5) 5 * factorial(4) 5 * (4 * factorial(3)) 5 * (4 * (3 * factorial(2)) 5 * (4 * (3 * (2 * factorial(1))) 5 * (4 * (3 * (2 * 1))) 5 * (4 * (3 * 2)) 5 * (4 * 6) 5 * 24 120 • Space  #pending operations • Linearly proportional to n Recursive Factorial factorial(5) 5 * factorial(4) 5 * (4 * factorial(3)) 5 * (4 * (3 * factorial(2)) 5 * (4 * (3 * (2 * factorial(1))) 5 * (4 * (3 * (2 * 1))) 5 * (4 * (3 * 2)) 5 * (4 * 6) 5 * 24 120 Time: O(𝑛) Space: O(𝑛) Linear Linear Iterative Factorial def factorial(n): product, counter = 1, 1 while counter <= n: product = (product * counter) counter = counter + 1 return product factorial(6) product counter 1 1 1 2 2 3 6 4 24 5 120 6 720 7 Iterative process Time (# of steps): • linearly proportional to n Space (memory): • constant • no deferred operations • All information contained in 2 variables (old values overwritten by new) Time: O(𝑛) Space: O(1) Linear Constant product: counter: 1 1 1 2 2 3 6 4 24 5 120 6 720 7 Recap: Fibonacci 𝑓𝑖𝑏(𝑛) = ቐ 0, 𝑛 = 0 1, 𝑛 = 1 𝑓𝑖𝑏 𝑛 − 1 + 𝑓𝑖𝑏(𝑛 − 2) 𝑛 > 1

def fib(n):

if (n == 0):

return 0

elif (n == 1):

return 1

else:

return fib(n – 1) + fib(n – 2)

Tree recursion

leaves

root
fib(5)

fib(4) fib(3)

fib(3) fib(2)

fib(1)

fib(2) fib(1)

fib(0) 1

1 0

fib(1) fib(0)

1 0

fib(2)

fib(1) fib(0)

fib(1)

1 0

Fibonacci
• Number of leaves in tree is 𝑓𝑖𝑏(𝑛 + 1)

• Can be shown that fib(n) is the closest integer to
Φ𝑛

– Where Φ =
1+ 5

2
≈ 1.6180

– called the golden ratio

• Therefore time taken is ≈ Φ𝑛

– (exponential in n)

Tree recursion
• Time:

– Proportional to number of leaves, i.e.,
exponential in n.

• Space (memory):
– Proportional to the depth of the tree, i.e.,

linear in n.

General form
Suppose a computation 𝐶 takes 3𝑛 + 5 steps

to complete, what is the order of growth?

O(3𝑛 + 5) = O(𝑛)

Take the largest term.
Drop the constants.

Another Example
How about 3𝑛 + 4𝑛2 + 4?

Order of growth
= O 3𝑛 + 4𝑛2 + 4

= O(3𝑛)

Tips
• Identify dominant terms, ignore smaller terms

• Ignore additive or multiplicative constants
– 4𝑛2 – 1000𝑛 + 300000 = O(𝑛2)

–
𝑛

7
+ 200𝑛 log 𝑛 = O(𝑛 log 𝑛)

• Note: log𝑎 𝑏 =
log𝑐 𝑏

log𝑐 𝑎

– So base is not important

More tricks in CS1231,
CS3230

Some involve sophisticated proofs

For now…
Count the number of “basic computational
steps”.

– Identify the basic computation steps
– Try a few small values of n
– Extrapolate for really large n
– Look for “worst case” scenario

Numeric example

13.7 billion years ≈ 259 seconds

100

200

300

1000

2000

3000

106

𝑛

13.8

0.69

1.098

2.3

2.99

3.4

4.6

5.29

5.7

6.9

7.6

log 𝑛

13.8 × 10

1.38

3.29

23.0

59.9

109

461

1060

1710

6910

15200

24019

𝑛 log 𝑛

100

400

900

10000

40000

90000

106

4 × 106

9 × 106

𝑛2

1000

8000

27000

106

8 × 106

27 × 106

109

8 × 109

27 × 109

𝑛3

1024

106

109

1.2 × 1030

1.6 × 1060

2.03 × 1090

1.07 × 10301

2𝑛

Time: how long it takes to run a program

Space: how much memory do we need to
run the program

pythontutor.com

itoday.com

Moral of the story
Different ways of performing a

computation (algorithms) can consume
dramatically different amounts of

resources.

Recursion Revisited
• Solve the problem for a simple (base) case

• Express (divide) a problem into one or more
smaller similar problems

• Similar to

Mathematical Induction

Comparison
Mathematical Induction

•Start with a base case 𝑏

•Assume 𝑘 works, derive a
function to show 𝑘 + 1 also
works

•Therefore, it must be true for
all cases ≥ 𝑏

Recursion

•Find base case(s) b where we
can just state the answer

•Derive a function to express
the problem of size n as sub-
problems of 𝑘 < 𝑛 •The function can therefore solve all 𝑛 ≥ 𝑏 Sometimes it may be possible that you will need more than one base case? When? Why? Tree recursion fib(5) fib(4) fib(3) fib(3) fib(2) fib(1) fib(2) fib(1) fib(0) 1 1 0 fib(1) fib(0) 1 0 fib(2) fib(1) fib(0) fib(1) 1 0 1 Other times you may have to express a problem in another form and the other form back in the present form (mutual recursion) - E.g. sin and cos More Examples Greatest Common Divisor The 𝐺𝐶𝐷 of two numbers 𝑎 and 𝑏, is the largest positive integer that divides both 𝑎 and 𝑏 without remainder. Greatest Common Divisor Naïve Algorithm: Given two numbers 𝑎 and 𝑏 Start with 1. Check if it divides both 𝑎 and 𝑏. Try 2, then 3, and so on… until you reach 𝑎 or 𝑏. Greatest Common Divisor Euclid’s Algorithm: Given two numbers 𝑎 and 𝑏, where 𝑎 = 𝑏 ∙ 𝑄 + 𝑟 (the remainder of the division), then we have 𝐺𝐶𝐷 𝑎, 𝑏 = 𝐺𝐶𝐷 𝑏, 𝑟 , ∀𝑎, 𝑏 > 0

𝐺𝐶𝐷(𝑎, 0) = 𝑎

Greatest Common Divisor
def gcd(a, b):

if (b == 0):

return a

else:

return gcd(b, a % b)

GCD(206,40) = GCD(40,6)

= GCD(6,4)

= GCD(4,2)

= GCD(2,0)

= 2

𝐺𝐶𝐷(𝑎, 𝑏) = 𝐺𝐶𝐷(𝑏, 𝑟), ∀ 𝑎, 𝑏 > 0

𝐺𝐶𝐷(𝑎, 0) = 𝑎

Tower of Hanoi

Towers of Hanoi
Goal: Move all discs from one stick to another

Rules:

1. Can only move one disc at a time

2. Cannot put a larger disc over a smaller disc

Towers of Hanoi
Goal: Move all discs from one stick to another

Rules:

1. Can only move one disc at a time

2. Cannot put a larger disc over a smaller disc

Towers of Hanoi

Suppose we know how to move 3
discs from A to C

A B C

Towers of Hanoi

Suppose we know how to move 3
discs from A to C

A B C

Towers of Hanoi

Claim: we can move 3 discs from
A to B. Why?

A B C

Towers of Hanoi

Claim: we can move 3 discs from
A to B. Why?

A B C

Towers of Hanoi

How to move 4 discs from A to C?

A B C

Towers of Hanoi

How to move 4 discs from A to C?
• Move 3 disc from A to B

A B C

Towers of Hanoi

How to move 4 discs from A to C?
• Move 3 disc from A to B

• Move 1 disc from A to C

A B C

Towers of Hanoi

How to move 4 discs from A to C?
• Move 3 disc from A to B

• Move 1 disc from A to C

• Move 3 disc from B to C

A B C

Divided into smaller problem

• Move 4 discs

• Move 5 discs?

• Move 𝑛 discs?

→Move 3 discs

→Move 4 discs

→Move 𝑛 − 1
discs

Recursion
1. Expressed (divided) the problem into one

or more smaller problems
𝑛 = 𝑓(𝑛 − 1)

2. Solve the simple (base) case
– 1 disc?
– 0 disc? Move directly from X to Y

Do nothing

High Level Idea
To move 𝑛 discs from A to C using B

A B C

…

𝑛

High Level Idea
To move 𝑛 discs from A to C using B
1. move 𝑛 − 1 discs from A to B using C

A B C

…

High Level Idea
To move 𝑛 discs from A to C using B
1. move 𝑛 − 1 discs from A to B using C

2. move disc from A to C

A B C

…

High Level Idea
To move 𝑛 discs from A to C using B
1. move 𝑛 − 1 discs from A to B using C

2. move disc from A to C

3. move 𝑛 − 1 discs from B to C using A

A B C

…

Towers of Hanoi
def move_tower(size, src, dest, aux):

if size == 1:

print_move(src, dest) # display the move

else:

move_tower(size-1, src, aux, dest)

print_move(src, dest)

move_tower(size-1, aux, dest, src)

src aux dest

Tower of Hanoi
def print_move(src, dest):

print(“move top disk from “, src” to “, dest)

Another example

What does this function compute?

def foo(x, y):

if (y == 0):

return 1

else:

return x * foo(x, y-1)

This?

def power(b, e):

if (e == 0):

return 1

else:

return b * power(b, e-1)

Exponentiation (𝑏𝑒)
def power(b, e):

if (e == 0):

return 1

else:

return b * power(b, e-1)

• Time requirement?

• Space requirement?

Can we do better?

O(𝑛)
O(𝑛)

Another way to express 𝑏𝑒

𝑏𝑒 = ൞

1, 𝑒 = 0

(𝑏2)
𝑒
2, 𝑒 is even

𝑏𝑒−1 ∙ 𝑏, 𝑒 is odd

Fast Exponentiation
def fast_expt(b, e):

if e == 0:

return 1

elif e % 2 == 0:

return fast_expt(b*b, e/2)

else:

return b * fast_expt(b, e-1)

• Time requirement?

• Space requirement?

Can we do this iteratively?

O(log 𝑛)
O(log 𝑛)

𝑏𝑒 = ൞

1, 𝑒 = 0

(𝑏2)
𝑒
2, 𝑒 is even

𝑏𝑒−1 ∙ 𝑏, 𝑒 is odd

Summary
• Recursion

– Solve the problem for a simple (base) case
– Express (divide) a problem into one or more smaller

Published by admin

Leave a Reply Cancel reply