[Solved] PIC16A Homework 2

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

• Problem 1:

Write a function longestpath(d) that finds 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 Newtons method (also known as the Newton-Raphson method) to find a root (zero) of a function. No prior knowledge of this algorithm is needed. Just follow the steps.

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

Algorithm:

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

, then you are done because x₀ is close enough to the root. Otherwise, a better approximation than x₀ is given by.

3. Keep updating your guess x_n using the formula until you have

Instructions:

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

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

• Test your solve function using the following functions f(x), their derivatives f⁰(x), and initial guesses x₀:

f(x) = x² 1, f⁰(x) = 2x, x₀ = 3 f(x) = x² 1, f⁰(x) = 2x, x₀ = 1 f(x) = exp(x) 1, f⁰(x) = exp(x), x₀ = 1 f(x) = sin(x), f⁰(x) = cos(x), x₀ = 0.5.

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

Due 5 PM, Wednesday, Jan. 20 Homework 2 PIC 16A

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 Newtons method with two iterations: https://www.youtube.com/watch?v=xdLgTDlFwrc