# CS61A Lab 3: Newton's Method

### 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):
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
```

### 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)
6.0
"""
```

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

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

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

### 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):
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:

• A point (x,y) is a maximum if and only if going north or east will take us to a lower elevation.

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):
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)
0.0
>>> round(y, 3)
0.0
"""
```

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

foo(6, 7)               # ? 8

return lambda m: m+n

f(2)                    # ? 9
```

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.