CS61A Lab 3: Newton's Method

Week 3, 2012

Exercise 1: Higher Order Functions

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):
		return x + y
	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

Exercise 2: Returning Functions

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)
	"*** YOUR CODE HERE ***"

Note: make_derivative itself is not the derivative; the function it returns is.

Exercise 3: Helper functions

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)
	>>> find_root(1, -7, 12)
	"*** YOUR CODE HERE ***"

Application: Iterative Improvement

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.

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.

Exercise 4: climb_update

Implement 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

Exercise 5: make_ismax

Next, 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)
    >>> is_max(-1, -1)
    def is_max(x, y):
        "*** YOUR CODE HERE ***"
    return is_max

Exercise 6: iter_improve

Finally, 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)
	>>> round(y, 3)
	"*** 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)

Open Questions ('Extra for Experts')

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

  2. 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?

Lambda Expressions

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*x
Notice 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.

Exercise 7: Lambda expressions

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

Exercise 8: Nested Lambda Expressions

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.