For every line that is marked with a "# ?" symbol, try to determine what Python would print in the interactive interpreter. Then check to see if you got the answer right.
def square(x):
return x*x
def neg(f, x):
return -f(x)
neg(square, 4) # ? 1
def first(x):
x += 8
def second(y):
print('second')
return x + y
print('first')
return second
f = first(15) # ? 2
f(16) # ? 3
def foo(x):
def bar(y):
return x + y
return bar
boom = foo(23)
boom(42) # ? 4
foo(6)(7) # ? 5
func = boom
func is boom # ? 6
func = foo(23)
func is boom # ? 7
Define a function make_derivative that
returns a function: the derivative of a function f. Assuming that f is a
single-variable mathematical function, its derivative will also be a
single-variable function. When called with an int a, the derivative will compute the
slope of f at the point a.
The formula for finding the derivative of f at point a is
where h approaches 0. We will approximate the derivative
by setting h to a very small number: 0.00001.
The closer you make h to 0, the more accurate
the derivative approximation will be.
def make_derivative(f, h=1e-5): """Returns a function that is the derivative of f. >>> square = lambda x: x*x >>> derivative = make_derivative(square) >>> result = derivative(3) >>> round(result, 3) 6.0 """ "*** YOUR CODE HERE ***"
Note: make_derivative itself is not the derivative; the function it returns is.
Now, we will visit the idea of helper functions. Sometimes, a function must perform a lot of computations -- so many computations, in fact, that it can get messy for the programmer to write. We can instead define a helper function within the parent function that will take care of some of the computations. The parent function then calls the helper function as needed.
Recall that a quadratic function is a function of the form:
The quadratic equation is a classic algebraic formula used for finding the roots of quadratic functions. Part of the quadratic equation involves finding the discriminant (the part under the square root).
The quadratic equation is
where the discriminant, represented by the delta, is
Define a function find_root that,
given the coefficients a, b, and
c of a quadratic function, will compute
a root of the function (normally, the quadratic equation has a
"+" or "-" sign -- we will focus on the "+" for now).
Your implementation should use a helper function called
discriminant, which also takes in the three
coefficients a, b, c, and computes their discriminant. Remember,
find_root is not returning
the function discriminant; rather,
find_root will call
discriminant to help with some calculations.
from math import sqrt def find_root(a, b, c): """Returns one of two roots of a quadratic function. Since there are two roots to quadratics, return the the larger root. In other words, the + or - part of the quadratic equation should just be replaced with a + >>> find_root(1, 2, 1) -1.0 >>> find_root(1, -7, 12) 4.0 """ "*** YOUR CODE HERE ***"
Newton's method is an example of a problem-solving method called iterative improvement. Iterative improvement starts with an initial guess to the problem; it then uses iteration (like a while loop) to update the guess until it gets close to the optimal solution.
This next application, which will make use of iterative improvement, is called the Hill Climbing problem. Given a certain unknown terrain, you must try to climb to its highest point. The key feature is that you have no knowledge of the terrain beforehand, so you can't determine its highest point just by "looking" at it.
This is an example terrain, defined by the mathematical function
Its contour plot is the following (think of this as a bird's eye view of the terrain).
As you can see, the highest point of the above terrain is at (0, 0), with an elevation of 0 (every other elevation is negative).
In this simplified example, you will start at some arbitrary initial point (x, y). You will then choose one of two actions: go north, or go east. (i.e. along the y-axis, or along the x-axis). You will make your decision based on the following simple heuristic: always choose the direction that will take you to a higher elevation. For example, if going north gets you to elevation 4, while going east only gets you to elevation 3, you'll (greedily) choose to go north.
So how do you know when to stop? If going north or going east both end up taking you to a lower elevation than your current elevation, you can (naively) declare that you are at the highest point in the terrain.
Note: In general, you'd need to avoid local maxima. For simple functions, such as the one proposed above, this heuristic may work. But for other functions, this heuristic will not in general find the maximum value.
Two key components of iterative improvement are the update function and the is_done function. The update function is responsible for updating the current guess; the is_done function is responsible for determining when the current guess is 'sufficiently close to' the optimal value.
climb_updateImplement climb_update. This is a higher-order function
that takes in two arguments: terrain, a mathematical function
that, given a point (x,y), returns the elevation at the point; and stepsize,
which is an integer that determines how large each step is. climb_update
should return a function that takes two arguments: x, the
x-coordinate of the current guess; and y, the y-coordinate
of the current guess.
climb_update will take the current guess (a coordinate
pair) and choose a coordinate to the north or to the east, depending which
elevation is higher. To determine the elevation at (a, b), call
terrain(a, b).
The parameter stepsize indicates the distance of each step.
For example, if the current location is (4, 5), and stepsize is
0.5, going east takes you to (4.5, 5); going north takes you to (4, 5.5). This
is an example of quantizing (or discretizing) the input function - since
there are an infinite number of points on a continuous function, we enforce a
pre-determined stepsize in order to allow us to work with the function
in a tractable manner. You can imagine that varying the stepsize will
lead to a performance/accuracy tradeoff!
def climb_update(terrain, stepsize=0.5):
"""Given a terrain function, and a stepsize, return an update
function that, given an (x,y) guess, returns an updated guess.
>>> terrain = lambda x, y: -x**2 - y**2
>>> start_x, start_y = -1, -2
>>> update = climb_update(terrain)
>>> update(start_x, start_y) # should move north
(-1, -1.5)
"""
def update(x, y):
"*** YOUR CODE HERE ***"
return update
make_ismaxNext, implement make_ismax. This function takes in a
terrain, and returns a function that checks if a given
coordinate pair is the highest point of that terrain.
We won't actually be checking that a given coordinate pair (x, y) is
a mathematical maximum for the terrain (this would be trying
to solve the problem we're originally trying to solve!). Instead, we'll use
the following naive heuristic:
For example, assume the current location (4, 5) is at elevation 5.
Say that the stepsize is 0.5.
Going north to (4, 5.5) gets you to elevation 4; going east to (4.5, 5)
gets you to elevation 3. Your current elevation is higher than both the
northern and eastern points, so is_max (which is returned by
make_ismax) should return True.
def make_ismax(terrain, stepsize=0.5):
"""Given the terrain, and a stepsize, return a function that,
given a guess, tries to determine if the guess is indeed the
maximum of the terrain.
>>> terrain = lambda x, y: -x**2 - y**2
>>> is_max = make_ismax(terrain)
>>> is_max(0, 0)
True
>>> is_max(-1, -1)
False
"""
def is_max(x, y):
"*** YOUR CODE HERE ***"
return is_max
iter_improveFinally, implement iter_improve, the function that continually
iterates until an optimal solution is found. iter_improve
takes four arguments: an update function, like the one returned
by climb_update; an ismax function, like the
one returned by make_ismax; x, and the
(x,y) coordinates of the initial guess.
Your implementation should make use of a while loop that continues
until the maximum has been reached. Each time you go through the loop,
you should keep track of the updated guess (which is a coordinate pair).
If you need help, you can look at the iter_improve
function for Newton's method in the lecture notes.
def iter_improve(update, is_done, x, y):
"""Tries to find an (x,y) that achieves the goal specified
by is_done, by iteratively updating an initial guess.
>>> terrain = lambda x, y: -x**2 - y**2
>>> update = climb_update(terrain)
>>> ismax = make_ismax(terrain)
>>> x, y = iter_improve(update, ismax, -3, -5)
>>> round(x, 3)
0.0
>>> round(y, 3)
0.0
"""
"*** YOUR CODE HERE ***"
You can use the following function to solve the Hill Climbing problem for your own terrain:
def climb(terrain, start_x, start_y): update = climb_update(terrain) ismax = make_ismax(terrain) return iter_improve(update, ismax, start_x, start_y)
One limitation you might have noticed is that the choice of the
initial guess (start_x, start_y) is crucial towards
finding the optimal solution. In particular, if
(start_x, start_y) is not to the south or to the west
of the terrain's maximum, then climb will not find the
terrain's maximum. This is because climb_update only
can move north or east.
If you're up for the challenge, you can
modify the climb_update function to also include
movements that go south and west! This extension will make
climb a little more robust.
Another inherent limitation to the iter_improve framework
is the stepsize. First - can you think of a terrain
function that, for a stepsize=0.5, climb will be
unable to find the maximum height? What could you try to do to fix this
limitation?
A lambda expression is a quick way to define functions without
actually using def statements. In other words, the same
function can be created in two ways: using def statements;
and using lambda expressions. For example, the following
function definition
def double(x): return 2*x
is equivalent to the following lambda function:
square = lambda x: 2*xNotice that there is no
return statement in the lambda expression; Python
will automatically return the expression following the colon. This is
a fundamental limitation of lambda in Python - the 'body'
of a lambda must be a single expression. This
implies that you cannot convert a multi-line
def statement into a lambda expression.
For every line that is marked with a "# ?" symbol, try to determine what Python would print in the interactive interpreter. Then check to see if you got the answer right.
lambda x: 2*x # ? 1
square = lambda x: x*x
square # ? 2
square(4) # ? 3
hello = lambda : print('hello')
hello(3) # ? 4
hello() # ? 5
adds = lambda x, y: x + y
adds(3) # ? 6
adds(4, 5) # ? 7
foo = adds
foo(6, 7) # ? 8
def make_adder(n):
return lambda m: m+n
f = make_adder(4)
f(2) # ? 9
make_adder(5)(6) # ? 10
Because lambda functions can't contain multi-line statements, it is not possible to incorporate while loops in lambda functions. Try the following:
g = lambda x: while x > 0: print(x); x -= 1
It should raise a SyntaxError. However, it is possible to put an if/else statement all on one line. Consider the following:
abs = lambda x: x if x > 0 else -x abs(6) # ? abs(-1) # ?
The one-line if/else statement reads like English: "return x if x is greater than 0, else return -x."
Using only lambda expressions, recreate the piecewise
function that you wrote for Homework 1. This time, however, you may only
use lambda expressions! Recall that piecewise is a
higher-order function that takes three arguments: the left-hand mathematical
function f; an int b; and the right-hand
mathematical function f.
piecewise = ________________________ negate = lambda x: -x identity = lambda x: x abs = piecewise(negate, 0, identity) abs(6) == 6 abs(-3) == 3
Remember, you may only use lambda functions to solve
this problem! It is possible to have nested lambda
expressions, much like you would have nested def statements.
Note: If you're having trouble, you might find it helpful to
first write piecewise using def statements,
and then 'translate' it into an equivalent program using only
lambda expressions.