Starting from:
$35

$29

Homework 2 Solution

Instructions: Name your  le hw2.py and submit on CCLE. Add comments to each function.

Problem 1:

Write a function longestpath(d) that  nds the length of the longest path, (a : b) !

(b : c) !   , in a dictionary d. It counts each pointer from a key to a value as one

step. For example, the path (a : b) ! (b : c) has length 2. To avoid cycles, we do not allow any key to appear more than once in a path (as a key).

Test cases:

d1 = {"a":"b","b":"c"}

d2 = {"a":"b","b":"c","c":"d","e":"a","f":"a","d":"b"} longestpath(d1) should return 2.

longestpath(d2) should return 5.

Problem 2:

Implement Newton’s method (also known as the Newton-Raphson method) to nd a root (zero) of a function. No prior knowledge of this algorithm is needed. Just follow the steps.

Given a function f(x) , the function’s derivative f0(x), and a desired tolerance (usually a very small positive number), your goal is to nd a desired value x which is close enough to a root of f(x) such that jf(x )j . The algorithm is as follows:

Algorithm:

        1. Starting from an initial guess x0, calculate the error of your guess f(x0).

        2. If jf(x0)j   , then you are done because x0 is close enough to the root. Otherwise,
a better approximation than x0 is given by x1 = x0
f (x0)
:



f 0 (x0)




3. Keep updating your guess xn using the formula xn+1 = xn

f (xn)
until you have


f 0 (xn)

jf(xn)j   :



Instructions:




{ Write your algorithm in a solve function that takes as input a function f(x), its derivative f0(x), an initial guess x0 and the tolerance . This function can be called like this:

print solve(lambda x: [x**2-1, 2*x], 3, 0.0001)

{ Test your solve function using the following functions f(x), their derivatives f0(x), and initial guesses x0:
f(x) = x2    1, f0(x) = 2x, x0 = 3

f(x) = x2    1, f0(x) = 2x, x0 =    1
f(x) = exp(x)    1, f0(x) = exp(x), x0 = 1

f(x) = sin(x), f0(x) = cos(x), x0 = 0:5.

Use a calculator to test if the solutions provided by your code are correct, and put results in comment in your script.
Suggestions:

{ You can start by hard-coding the function, its derivative, the initial guess, and the tolerance in your script without getting user input. This will help you better understand the algorithm.

{ If you are still confused, watch this video for an example of Newton’s method with two iterations: https://www.youtube.com/watch?v=xdLgTDlFwrc.

More products