Although I generally try to find problems for which I can motivate the mathematics, here at the beginning of the course I need to ask you to look at an integral for its own sake. (This may also force you to dig your calculus book out early, so it is readily available for your use in the rest of the course.)

We are going to consider calculating the integral T_n = ò₀^g [(xⁿ)/(x+b)]dx for values like g = 0.5 and 0 < b £ 6.

a)

Recall that an integral measures the area under the graph of its function. Sketch a rough graph with f(x) = xⁿ/(x+b) for n = 2,4,8 (and, say, b = 3) and predict what happens to the value of the integral as n increases.

b)

Using your knowledge of calculus, determine the exact values of T₀, T₁, and T₂. (Remember integration by parts. Don't use numerical integration; if can use a symbolic algebra package to check yourself on T₂, then use it to do a couple more as well.)

c)

Give a one-line demonstration that bT_n-1 + T_n = gⁿ/n.

d)

Use c) to calculate T₂, T₃, ¼, T₃₅ from the value of T₀ in part b). Try this for g = 0.5 and b Î {0.3,0.8, 1.5, 3.0}. Hand in only the first and last values of b.

e)

From the rough prediction that T₃₅ = 0, use c) to calculate T₃₄, T₃₃, ¼, T₀. Try this for g = 0.5 and b Î {0.3, 0.8, 1.5, 3.0}. Hand in only the runs on b = 0.3 and b = 3.0.

f)

Compare the results of d) and e) and explain them for all four values of b; (Especially how you can start with a wrong value of T₃₅ = 0 for b = 3.0 and get the right value of T₀, while the other recurrence blows up...)

I expect that you should be able to hand in only about 5 pages: a graph for a), a page each for b) and f), a short derivation for c), and a two-sided page each of output for d) and e). Recall that collaboration is allowed, but must be acknowledged. Anything handed in, or any code used to generate results, must be your own writing or typing. Using someone else's code to produce results that you hand in as your own is NOT acceptable. You must type it yourself (and debug the typos you introduce) to help you understand it.

The convex hull algorithms are based on the CCW(p,q,r) determinant, which tests the sign of

a)

Suppose that each point is moving with a different (but fixed) velocity vector, so that p(t) = p+t[u\vec] = (p_x+t u_x, p_y+t u_y), q(t) = q+t[v\vec], and r(t) = r+t[w\vec]. Express the CCW(p,q,r) test as a polynomial in t.

b)

Given a time t₀, how would you calculate the next time t > t₀ at which the sign would change?

c)

What is the polynomial in t for the InCircle(p,q,r,s) determinant, where s(t) = s+t [(s)\vec]:

Let W be a set of n windows-vertical line segments in the plane with above and below endpoints a_i = (x_i, ay_i) and b_i = (x_i, by_i) with ay_i > by_i, for 1 £ i £ n. We can look through W if some line intersects every window in W. Find an efficient algorithm to determine if we can look through W. (A linear time algorithm is not difficult if the windows are sorted by x-coordinate. Is there an W(nlogn) lower bound or can linear time be attained without sorting?)

Problem Set #3: assigned Feb 8, due Thurs, Feb 22

Implement a program that takes as input a set of n points P and velocity vectors V, and maintains a triangulation as the points move from t = 0 to t = 1. That is, maintain a decomposition of the convex hull (or of the entire plane) into ccw-oriented triangles whose vertices are the moving points. You will need to use the determinant calculations from the last problem set.

We will be modifying this program later to allow more complicated motions than fixed linear motion, so keep this in mind.

Trace the intersection curve of two cylinders by interpolation.

The intersection is the set of all points that satisfy both equations. We'd like to be able to trace this curve as a parametric vector-valued function f(t) = ( x(t), y(t), z(t)). Here is a table with values of the three coordinate functions if we parameterize with t Î [0,1].

t	x(t)	y(t)	z(t)
0	1	0	1/2
1/8	Ö3/2	Ö3/2	0
1/4	0	1	-1/2
3/8	-Ö3/2	Ö3/2	0
1/2	-1	0	1/2
5/8	-Ö3/2	-Ö3/2	0
3/4	0	-1	-1/2
7/8	Ö3/2	-Ö3/2	0
1	1	0	1/2

Interpolate functions for x(t), y(t), z(t). The interpolation methods you should use are:

a)

Lagrange interpolation (Hamming 14.5)

b)

Cubic spline interpolation with the standard end conditions that the second derivatives are zero. (Hamming 20.9)

c)

Cubic spline interpolation without end conditions-use the fact that the intersection is a closed curve.