Exercises¶

Problem 1

A polynomial \(p(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots\) can be represented with a list of coefficients in ascending order of degree, so that element i is the coefficient \(a_i\) multiplying \(x^{i}\).

\(p(x) = 1 + 5x + 3x^2 + 9x^3\) can be represented with [1, 5, 3, 9].
\(p(x) = x^2\) can be represented with [0, 0, 1].
\(p(x) = 4\) can be represented with [4].

The derivative of a polynomial \(p(x)\) is another polynomial, \(p'(x)\):

\[\begin{split} \begin{aligned} p(x) &= a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots + a_{n-1} x^{n-1} = \sum_{i=0}^{n-1} a_i x^i, \\ p'(x) &= a_1 + 2a_2 x + 3a_3 x^2 + \cdots + (n - 1) a_{n-1} x^{n-2} = \sum_{i=1}^{n-1} i a_i x^{i-1}. \end{aligned} \end{split}\]

Write a function named poly_derivative() that accepts a NumPy array of \(n\) coefficients representing a polynomial \(p(x)\) and returns a NumPy array of the \(n - 1\) coefficients of the derivative \(p'(x)\). In other words, given \([a_0,a_1,a_2\ldots,a_{n-1}]\), return \([a_1, 2a_2, \ldots, (n - 1)a_{n-1}]\). Represent the zero polynomial \(p(x) = 0\) as the single-element array \([0]\).

Reminder: np.zeros(n) creates an array of n zeros.

Test Cases

# d/dx[1 + 5x + 3x^2 + 9x^3] = 5 + 6x + 27x^2
print(poly_derivative(np.array([1, 5, 3, 9])))

# d/dx[3.14 + 6.28x + x^2 - 0.6x^4] = 6.28 + 2x - 2.4x^3
print(poly_derivative(np.array([3.14, 6.28, 1, 0, -0.6])))

# d/dx[4] = 0
print(poly_derivative(np.array([4])))

[ 5.  6. 27.]
[ 6.28  2.    0.   -2.4 ]
[0.]

Problem 2

A polygon can be described by a list of at least three \((x, y)\) points giving its corners, or vertices, in order: \([(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)]\). Gauss’s area formula, also known as the shoelace formula, gives the enclosed area as

\[ A = \frac{1}{2}\left| \sum_{i=1}^{n} \left( x_{i} y_{i+1} - x_{i+1} y_{i} \right) \right|, \]

where the vertex after the last one wraps back around to the first, \((x_{n+1}, y_{n+1}) = (x_1, y_1)\). For the triangle with vertices \((0,0)\), \((4,0)\), and \((1,3)\), this sum has three terms, one per edge.

\[ A = \frac{1}{2}\left| \big(0 \cdot 0 - 4 \cdot 0\big) + \big(4 \cdot 3 - 1 \cdot 0\big) + \big(1 \cdot 0 - 0 \cdot 3\big) \right| = \frac{1}{2}\left| 12 \right| = 6. \]

The following code plots a polygon with the vertices given in this format.

def plot_polygon(vertices):
    """Draw the polygon with the given vertices."""
    P = np.array(vertices + [vertices[0]])
    plt.plot(P[:, 0], P[:, 1], "o-", markersize=5, linewidth=1)
    plt.axis("equal")
    plt.show()

Write a function named polygon() that accepts a list of \((x, y)\) points representing the vertices of a polygon. Compute the perimeter (the sum of the lengths of the sides) and, using Gauss’s area formula, the area enclosed by the polygon. Return both the perimeter and the area, in that order.

Reminder: Use return x, y to return two values.
Hint: There are several ways to approach this problem, but whatever strategy you choose, remember to account for the edge between the last and first points in the list.

Test Cases

perimeter, area = polygon([(0, 0), (1, 0), (1, 1), (0, 1)])
print(perimeter, area)

perimeter, area = polygon([(0, 0), (1, 0), (2, 2), (0, 1)])
print(perimeter, area)

perimeter, area = polygon([(-1, -1), (3, 0), (1, 0.5), (2, 2), (0, 3)])
print(perimeter, area)

0 1.0
47213595499958 2.0
346607679275937 7.25

Problem 3

A lattice point is a point \((x, y)\) whose coordinates are both integers. The circle of radius \(r = 2.5\) shown below encloses 21 lattice points.

Write a function named lattice_points() that accepts a nonnegative number \(r\) and counts the lattice points lying on or within the circle of radius \(r\) centered at the origin. That is, find the number of pairs \((x, y)\) satisfying \( x^2 + y^2 \le r^2 \) where \(x\) and \(y\) are both integers. Return the number of lattice points.

Hint: The radius \(r\) may not be an integer, but range() only accepts integers. A built-in function can help with this.

Test Cases

print(lattice_points(0))
print(lattice_points(1))
print(lattice_points(2.5))
print(lattice_points(20))

Problem 4

As we saw in Problem 1, a polynomial \(p(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots\) can be represented with a list of coefficients in ascending order of degree, so that element i is the coefficient \(a_i\) multiplying \(x^{i}\).

\(p(x) = 1 + 5x + 3x^2 + 9x^3\) can be represented with [1, 5, 3, 9].
\(p(x) = x^2\) can be represented with [0, 0, 1].
\(p(x) = 4\) can be represented with [4].

The product of a polynomial \(p(x)\) with \(n\) coefficients and a polynomial \(q(x)\) with \(m\) coefficients is a polynomial with \(n + m - 1\) coefficients:

\[\begin{split} \begin{aligned} p(x) &= a_0 + a_1 x + a_2 x^2 + \cdots + a_{n-1} x^{n-1} = \sum_{i=0}^{n-1} a_i x^i, \\ q(x) &= b_0 + b_1 x + b_2 x^2 + \cdots + b_{m-1} x^{m-1} = \sum_{j=0}^{m-1} b_j x^j, \\ p(x)q(x) &= a_0 b_0 + (a_0 b_1 + a_1 b_0)x + (a_0 b_2 + a_1 b_1 + a_2 b_0)x^2 + \cdots = \sum_{i=0}^{n-1}\sum_{j=0}^{m-1} a_i b_j x^{i + j}. \end{aligned} \end{split}\]

Another way to describe this is that the coefficient on \(x^{k}\) in the product polynomial \(p(x)q(x)\) is the sum of all products \(a_i b_j\) such that \(i + j = k\).

Write a function named poly_product() that accepts a NumPy array of \(n\) coefficients representing a polynomial \(p(x)\) and a NumPy array of \(m\) coefficients representing a polynomial \(q(x)\). Return a NumPy array of the \(n + m - 1\) coefficients of the product polynomial \(p(x) q(x)\).

Hint: enumerate() may be helpful.

Test Cases

# (1 + x)(1 - x) = 1 - x^2
print(poly_product(np.array([1, 1]), np.array([1, -1])))

# (2 + 3x + x^2)(1 - 4x) = 2 - 5x - 11x^2 - 4x^3
print(poly_product(np.array([2, 3, 1]), np.array([1, -4])))

# (1 + x + x^2 + x^3)(0) = 0 + 0x + 0x^2 + 0x^3
print(poly_product(np.array([1, 1, 1, 1]), np.array([0])))

[ 1.  0. -1.]
[  2.  -5. -11.  -4.]
[0. 0. 0. 0.]

Problem 5

A Pythagorean triplet is a set of three positive integers \((a, b, c)\) satisfying \( a^2 + b^2 = c^2. \) For example, \(3^2 + 4^2 = 5^2\), so \((3, 4, 5)\) is a Pythagorean triplet.

Write a function named pythagorean_triplet() that accepts a positive integer \(n\) and finds a Pythagorean triplet \((a, b, c)\) such that \( a + b + c = n. \) Return the three values \(a\), \(b\), and \(c\); if there are no such values, the function should return None. Only return values forming a single triplet, even if there are multiple possible triplets for a given \(n\).

Your function should be able to complete the test cases within a few seconds.

Hint: Once \(a\) and \(b\) are chosen, do you need another loop for \(c\)?

Test Cases

print(pythagorean_triplet(12))
print(pythagorean_triplet(13))
print(pythagorean_triplet(150))
print(pythagorean_triplet(10050))

(3, 4, 5)
None
(25, 60, 65)
(1072, 4425, 4553)

Problem 6

Consider the sequence of numbers defined through the following iteration:

\[\begin{split} x_{k+1} = \begin{cases} \frac{1}{2}x_k &\text{if}~x_k~\text{is even,} \\ 1 + 3x_k &\text{if}~x_k~\text{is odd.} \end{cases} \end{split}\]

For example, if \(x_0 = 3\), then the sequence is \((3, 10, 5, 16, 8, 4, 2, 1)\). In this case, the sequence reaches \(x_n = 1\) in \(n = 7\) steps.

The Collatz conjecture is the claim that no matter which positive integer is chosen as the starting point \(x_0\), the sequence will always reach \(1\) eventually. No one has proven that this is always the case, but a counterexample has yet to be discovered.

Write a function named collatz_steps() that accepts a positive integer \(x_0\) and counts the steps needed to reach \(x_n = 1\) by repeatedly applying the rule above. Return the number of steps \(n\).

Hint 1: An integer is even if, when divided by 2, the remainder is zero.
Hint 2: In the even case, use integer division //, not float division /.

Test Cases

print(collatz_steps(1))
print(collatz_steps(3))
print(collatz_steps(27))

0
7
111

Problem 7

In the famous wheat and chessboard problem, one grain of wheat is placed on the first square of a chessboard, then two grains are placed on the next square, then four, then eight, and so on, with each square containing twice as many grains as the square before it. The standard version of the problem is to find out the total number of grains placed on the 64 chessboard squares, which turns out to be about eighteen quintillion (\(1.84 \times 10^{19}\)).

Write a function named wheat_squares() that accepts a positive integer \(n\) and finds the least number of squares needed for the running total of grains to reach or surpass \(n\). Return the number of squares used, counting the square that first makes the total reach or exceed the threshold.

Test Cases

print(wheat_squares(1))
print(wheat_squares(10))
print(wheat_squares(1_000_000_000_000))  # One trillion.

1
4
40

Problem 8

The bisection method estimates a root of a function \(f\) by repeatedly shrinking an interval \([a_{k}, b_{k}]\) that contains one. Since \(\sqrt{z}\) is the positive root of \(f(x) = x^2 - z\), the method can be used to estimate square roots. For a given positive number \(z\), the iteration is

\[\begin{split} \begin{aligned} x_{k} &= \frac{1}{2}(a_{k} + b_{k}) \\[.75em] a_{k+1} &= \begin{cases} x_{k} &\text{if}~x_{k}^2 - z < 0 \\ a_{k} &\text{if}~x_{k}^2 - z \ge 0, \end{cases} \qquad a_{0} = 0, \\[.75em] b_{k+1} &= \begin{cases} b_{k} &\text{if}~x_{k}^2 - z < 0 \\ x_{k} &\text{if}~x_{k}^2 - z \ge 0, \end{cases} \qquad b_{0} = \max\{1, z\}. \end{aligned} \end{split}\]

Write a function named sqrt_bisection() that accepts a positive number \(z\) and a positive stopping tolerance \(\epsilon\), then applies the iteration above until the current iterate \(x_k\) satisfies

\[ |x_k^2 - z| < \epsilon. \]

Return the final iterate \(x_k\).

Hint: consider using the following outline.

Set the initial values \(a = a_0\) and \(b = b_0\).
Set \(x = \frac{1}{2}(a + b)\).
Enter a loop that ends when \(|x^2 - z| < \epsilon\).
In the loop, if \(x^2 - z < 0\), set \(a = x\), leaving \(b\) unchanged.
Otherwise, if \(x^2 - z \ge 0\), set \(b = x\), leaving \(a\) unchanged.
Update \(x = \frac{1}{2}(a + b)\).
After the loop, return \(x\).

Test Cases

print(sqrt_bisection(2, 1e-2))
print(sqrt_bisection(2, 1e-5))
print(sqrt_bisection(2, 1e-12))

4140625
414215087890625
4142135623733338