ODE Iterative Procedure
xi = xl stands xi
delta
= xl= wisechoice()
dy 2 2 fi = f0
‣ Find y, a function of y s.t. = x + y , given that y(1)for=‘≤’0 fi
xi == f0
xl # assumes xh > xl
☚
dx while xi <= x: while
fi = f0 xi ≤ x done before
• How to represent a function? fi += delta * g(xi, fi)
while
fi+1 xi=<fi + xi g(xi,
x: delta updatefi)
☚
xi += delta xi > x? xi
fi +=
+= delta
delta * g(xi, fi)
- Maybe, a “program” that produces f(x), given x
xi += delta
d # xi d>= x now
‣ 1st order ODE: Solve f′(x) = g(x, f(x)) where g : [xl, xh] × ℝ → ℝ and f(xl) = f0
delta = (x - xi)
• How to represent input (including g)?
fi += delta * g(xi, fi)
Iterate from xl until x in small steps 𝛿
- xl, xh, f0, g — a program
‣ Approximate f(x + δ) if f(x) is known
• Euler’s method: fi+1 = fi + δg(xi, fi), where δ = xi+1 − xi
ODE Iterative Procedure
Repeat every time for a new x?
dy 2 2
xi = xl
‣ Find y, a function of y s.t. = x + y , given that y(1) = 0 fi = f0
dx f[xi+delta] = f[xi]+delta*g(xi, f[xi])
xi updated first while xi < x:
• How to represent
NOT a function?
EQUIVALENT ! xi += delta fi += delta * g(xi, fi)
xi += delta Remember
- Maybe, a “program”
f[xi] = f[xi-delta] + that ➜
produces f(x), given x xi += delta
1. Let R be the location of f[xi] delta = (x - xi)
delta*g(xi-delta, f[xi-delta]) 2. Find value of R, call it B
d d
‣ 1st order ODE: Solve f′(x) = g(x, f(x)) where g : [xl, xh] × ℝ → ℝfi += f(xl)* =g(xi,
anddelta f0 fi)
3. Compute g(xi, B), call it C
• How to represent input (including g)? Reliable Identities:
4. Compute B+delta*C, call it D
x * 0 == 0
- xl, xh, f0, g — a program 5. Compute xi+delta, call it A
6. Let L be the location of f[A] x + 0 == x
‣ Approximate f(x + δ) if f(x) is known 7. Change L to what D is x * 1 == x
• Euler’s method: fi+1 = fi + δg(xi, fi), where δ = xi+1! − xi precision for Real numbers
Finite
Iterate from xl until x in small steps 𝛿
(A - delta) need not yield xi
Recursion
‣ Find factorial(n), n is positive
What happens if n <= 0?
‣ n! = 1 * 2 * … n def factorial(n):
• factorial0 = 1 f=1 ?
for i in range(n):
• Iterate: for i going from 1 to n: factoriali = i * factoriali-1 f = f*i
return f
Recursion
‣ Find factorial(n), n is positive
What happens if n <= 0?
‣ n! = 1 * 2 * … n def factorial(n):
=
• factorial0 = 1 f=1
for i in range(2,n+1):
• Iterate: for i going from 1 to n: factoriali = i * factoriali-1 f *= i
‣ Also: n! = n * (n-1)!, with 1! = 1 0! ? return f 720
Calling a function
def factorial(n):
if(n == 0):
return 1 x = factorial(6) 6
else:
return n * factorial(n-1) print(factorial(x))
ai redux Recursive Procedure
‣ ai = ai/2 * ai/2 = a * ai-1 def a to power i(a, i):
if i == 0:
• where, a0 = 1 return 1 stands for
else: quotient
☚
‣ Difficult if power is a fraction
return a to power i(a,i//2) * a to power i(a, i-i//2)
def atopoweri(a, i):
How many calls to the function? In-lined after ‘:’ allowed
if i == 0: return 1 ☚
Stands ☚ elif i == 1: return a
1. def a_to_power_i(a, i): for ‘else if’ else: return atopoweri(a, i//2) * atopoweri(a, i-i//2)
2. if i == 0: return 1 1f(i) 2f(i//2) 4f(i//4) 8f(i//8) .. 2if(0)
3. if i % 2 == 0:
4. return a_to_power_i(a, i//2)**2
Do 5. if condition on 3.‘if’ is false. But no ‘else’ used
5. return a*a_to_power_i(a, i//2)**2 ☚ here, so control would normally reach 5 after 4. It
f(i) f(i//2) f(i//4) f(i//8) .. f(0) won’t if 4. returns control to the caller instead.
Find Root by Bisection Recursive Procedure
f(x)
‣ Find x0, s.t. f(x0) = 0
‣ Given f : ℝ → ℝ, a, and b, s.t. f(a) < 0 and f(b) > 0
a b x
function name is a name. Can use it
as parameter in another function, just b middle
as we can use other names
☚
def root(f, lo, hi): assumes a <= b?
mid = (lo+hi)/2
if abs(f(mid)) < epsilon: return mid check f(middle) middle = (a+b)/2
elif f(mid) < 0: return root(f, mid, hi)
+ve: restrict range to (a, middle)
else: return root(f, lo, mid)
-ve : restrict range to (middle, b)
def sqrtf(x): return x*x - 40
0 : f(middle) is 0 answer
r = root(sqrtf, 0, 40)
Recall GCD
def GCD(a, b): GCD(60, 18) = GCD(18, 6) = GCD(6, 0)
if (a < b):
GCD(6, 60) = GCD(60, 6) = GCD(18, 6) = GCD(6,0)
(a,b) = (b,a)
if(b == 0): GCD(6, 0) = 6?
return a
else: def GCD(a, b):
return GCD(b, a%b) if(b == 0): return a
return GCD(b, a%b)
Logical Disjunction
def doGCD(a, b): ☚
if a <= 0 or b <= 0: return None
return GCD(a, b)
if a or b <= 0: return None
Find Extrema
‣ Given a list of integers [L] Find the smallest and the largest
• Produces a pair tuple in Python
‣ MIN(L) = given min(a, b) = max(a, b) =
|L| == 1: L0 a < b: a a < b: b
|L| > 1 : min(L0, MIN(L-L0)) a ≥ b: b a ≥ b: a
def minmax(L): Stands for L0
‣
☚
MINMAX(L) = ☚
Stands for |L| if len(L) == 1: return (L[0], L[0])
|L| == 1: L0, L0 ? ?
|L| > 1 : min(L0, MIN(L-L0)), max(L0, MAX(L-L0)) return ( min( L[0], minmax(L[1:])[0] ),
max( L[0], minmax(L[1:])[1] ) )
|L| == 1: L0, L0 Stands for a
☚
|L| > 1 : min(L0, MINMAX(L-L0)0), max(L0, MINMAX(L-L0)1) slice of L, from
1 until its end
Tower of Hanoi Recursive Procedure
T0 T1 Extra
Move all disks to Tower 1
Axiom: Move top disk from one tower to another (move1)
Never stack a larger disk on top of a smaller one
Tower of Hanoi Recursive Procedure
T0 T1 Extra
Move all disks to Tower 1
Axiom: Move top disk from one tower to another (move1)
Never stack a larger disk on top of a smaller one
Tower of Hanoi Recursive Procedure
T0 T1 Extra
Move all disks to Tower 1
Axiom: Move top disk from one tower to another (move1)
Never stack a larger disk on top of a smaller one
Tower of Hanoi Recursive Procedure
T0 T1 Extra
Move all disks to Tower 1
Axiom: Move top disk from one tower to another (move1)
Never stack a larger disk on top of a smaller one
Tower of Hanoi Recursive Procedure
T0 T1 Extra
Move all disks to Tower 1
Axiom: Move top disk from one tower to another (move1)
Never stack a larger disk on top of a smaller one
Tower of Hanoi Recursive Procedure
def hanoi(ndisk, src, dest, third):
if(ndisk == 1): move1(src, dest)
else:
hanoi(ndisk-1, src, third, dest)
move1(src, dest)
1 hanoi(ndisk-1, third, dest, src)
n-1
disks return
3
2 Functions need not ‘return’ a
value. (Some do not have an
T0 T1 Extra explicit ‘return’ statement.)
hanoi(4, 0, 1, 2)
Move all disks to Tower 1
Axiom: Move top disk from one tower to another (move1)
Never stack a larger disk on top of a smaller one
Algorithm Lessons: Approaches
‣ In this course, We will rely on knowing simple algorithms
• Combining multiple known algorithms in a simple way is expected
‣ One type of algorithms systematically search through a broad space of solutions
• Understand how to form, classify, and enumerate cases exhaustively a < b: …
a > b: …
‣ Solution can often be expressed in terms of solutions of subproblems
• Subproblems must get ‘smaller’ until a ‘base case’ is reached
• Specification may itself suggest a recursive algorithm, or could easily be transformed
‣ When designing iterative solution: think of what progress each iteration makes
• solve each subproblem, move closer to the solution Form loop-invariants
(to come later)
Algorithm Lessons: Top-down design
‣ Step-wise refinement
• Devise high-level steps needed to solve
- without initially worrying about how the steps are implemented
• For each step, similarly divide it into sub-steps … and so on Often subdivided
into two parts
- until steps become trivial to solve, and ‘hard-wire’
Divide and
‣ We will also see how to subdivide the input into smaller pieces Conquer
• and each piece into even smaller pieces, until each piece is very simple
‣ A general way to explore solution space (i.e., possible solutions)
• Make groups of potential solutions, rule some out, Subdivide the rest …
- Keep repeating until the remaining space is the solution
Exercises Algorithms
‣ Factorize x
• Devise an iterative and a recursive solution
‣ Find the total area enclosed by the curve f(x) and lines x = 0, y = a, and y = b
‣ Given an ordinal list of 2D points [P]
• Find the pair (Pi, Pj), i ≠ j, s.t. L2Distance(Pi, Pj) ≤ L2Distance(Pk, Pl), k ≠ l.
‣ Find the smallest area upright rectangle enclosing a list of 2D points [P]
• (First formalize the specification)
