Comp 110 Final Exam:  Spring 2009.  Due at Noon on Wednesday, April 29.  Send Your Mathematica Notebook by E-mail to:  rng@rice.edu

All work must be entirely your own.  You are not allowed to work with a partner or to consult on these problems with anyone except the instructor or the labbie.

This exam is closed book and closed notes.  You are not permitted to look at your work on previous modules or previous homeworks while taking this exam, but you are encouraged to make extensive use of the Documentation Center.  

Caution:  Although we expect you to make extensive use of the Documentation Center to assist you with these problems, when you are asked to explain concepts or notation, you should not copy your answers verbatim from the Documentation Center.  Present the answers in your own words.  Avoid jargon and special notation;  use standard English and classical Mathematical notation.  When you are asked to present examples, provide your own examples;  do not copy examples from the Documentation Center.

All proofs and computations must be done using Mathematica;  no other proofs or computations will be accepted.  

Please format your solutions appropriately.  Use text format, not input format, when you are typing text.  Write coherent sentences and paragraphs;  part of your grade will depend on how clearly you present your ideas.

There is a 4 hour time limit for this exam.  If you get stuck on a problem, go on to the next problem and come back later to the problem that is giving you trouble.  Do not waste time.

The exam is due at noon on May 5.  For graduating seniors the exam is due at noon on May 2.

Geometry:  Volume of a Cone  (20 Points)

In this problem you will use Monte Carlo methods to compute the volume of a right circular cone.

Problems

1.  Display the right circular cone of height 1, whose vertex is at the origin, whose axis is the z-axis, and whose cross section with the plane z=1 is a unit circle.

2.  Write a function ptinCone that given a point in 3-space determines whether the point lies inside the cone in Problem 1.  The function ptinCone should return 1 if the point lies inside the cone and 0 if the point lies outside the cone.

3.  Write a function randomPt that generates a random point inside a rectangular box that contains the cone in Problem 1.

4.  Write a function dartlist that generates a list of n random points inside the rectangular box that contains the cone in Problem 1.  (Hint:  Use the helper function in Problem 3.)

5.  Use Monte Carlo methods to determine the ratio of the volume of the cone in Problem 1 to the volume of the box that contains the cone by applying the functions in Problems 2 and 4.

6.  Using the results of Problems 5, determine numerically the volume of the cone in Problem 1.

7.  Using the result of Problems 6 and the known formula for the volume of a right circular cone, determine numerically the value of π.

Quaternion Algebra  (20 Points)

In this problem you will investigate identities for quaternions.

A quaternion is a pair (c,v), where c is a scalar (a real number) and v is a vector in 3-dimensions.  Quaternion addition and quaternion multiplication are defined in the following fashion:  Let p=(c,v) and q=(d,w) be quaternions.
Quaternion Addition:  	
	p+q = (c+d, v+w)
Quaternion Multiplication:
	pq = (cd - v·w, cw + dv + v×w)
where × denotes cross product, · denotes dot product, and juxtaposition (i.e. cw or dv) denotes the product of a scalar with a vector.

Problems

Using Mathematica, either prove or provide a counterexample for each of the following four identities:
i.	p+q = q+p
ii.	pq = qp
iii.	(pq)r = p(qr)
iv.	p(q+r) = pq + pr

Note that numerical examples are fine as counterexamples.  But a numerical example is NOT a proof.  NO CREDIT will be given if you present a numerical example in place of a proof.

Polygons, Circles, Wheels, and Rosettes  (20 Points)

The vertices of a regular polygon lie on a circle.  If the circle is centered at the origin and the polygon has n sides, then the vertices can be placed at the points:

(Subscript[P, k])=(r cos(2πk/n), r sin(2πk/n)) 		k=0,...,n

where r is the radius of the circle.

Problems

In the following problems you must write your own functions.  You may NOT use the built in Mathematica functions for circles and polygons.

1.  Write a function polyverts that takes as input a positive integer n and a positive real number r, and generates a list of vertices for a polygon with n sides lying on a circle of radius r.  (You may want to use the function N to speed up the calculations of sines and cosines.)

2.  Using the function polyverts in Problem 1, write a function displaypoly that takes as input a positive integer n and a positive real number r, and displays the corresponding polygon with n sides.  Turn off the axes so that only the polygon is displayed.  Generate some examples to illustrate that your program works.

3.  Write a function circle that takes as input a positive integer r and displays the corresponding circle of radius r.  Turn off the axes so that only the circle is displayed.  (Hint:  A circle is just a polygon with lots of sides.)  Generate some examples to illustrate that your program works.   Use your circle program together with your displaypoly program to display polygons with n sides inscribed in circles of radius r.

4.  A wheel is a polygon with all its vertices joined to its center (see below).  Using the function polyverts in Problem 1, write a function wheel that takes as input a positive real number r, and displays a wheel inscribed in a circle of radius r.  Use a slider to control the number of sides of the wheel.  Turn off the axes so that only the wheel is displayed.  Generate some examples to illustrate that your program works.  (Hint:  You may want to write a helper function spokes that takes as input a fixed point together with a list of points, and generates a list of lines joining the fixed point to each of the points in the list of points.)

5.  A rosette is a polygon with all its diagonals connected by straight lines (see below).  Using the function polyverts in Problem 1, write a function rosette that takes as input a positive real number r, and displays a rosette inscribed in a circle of radius r.  Use a slider to control the number of sides of the rosette.  Turn off the axes so that only the rosette is displayed.  Generate some examples to illustrate that your program works.  (Hint:  You may want to write a helper function joinpts that takes as input a list of points, and generates a list of lines that join every point in the list of points to every other point in the list.)

Geometry:  Heron's Formula  (20 Points)

The formula for the area of a triangle in terms of the lengths of its three sides and its semiperimeter (half the perimeter) is called Heron's formula.  In this problem you will use Mathematica to derive Heron's formula.

Problems

1.  Use Mathematica to derive a formula for the area of a triangle in terms the lengths of its sides, based upon simple geometry and trigonometry.  [Hint:  Use the standard formula for the area of a triangle:  Area = 1/2 Base ⋆ Height, and apply the Pythagorean Theorem to obtain two additional equations involving h and x.  Then invoke Mathematica to eliminate the variables h and x.]

2.  Use Mathematica to derive a symmetric version of this area formula in terms of the semiperimeter  s=(1/2)(a+b+c), where a, b, c are the lengths of the sides of the triangle.  [Hint:  Factor the expression for the area you generated in part 1, and then use replacment rules.]

Fractal Tennis (20 Points)

The fractals you generated in class were constructed by a deterministic algorithm.  Here you will generate fractals using a non-deterministic or random algorithm.  In this random algorithm, you will start with an arbitrary set of transformation W={(Subscript[w, 1]),…,(Subscript[w, p])}.  These transformations are usually represented by 3x3 matrices, and points in the plane are typically represented using 3 coordinates, where the first two coordinates are the standard rectangular coordinates and the third coordinate is always 1.  If you select any point (Subscript[P, 0])=((Subscript[x, 0]), (Subscript[y, 0]),1) in the fractal and compute
	 (Subscript[P, 1])= (Subscript[P, 0])*(Subscript[w, (Subscript[i, 1])])
	 ⋮
	 (Subscript[P, n])=(Subscript[P, n-1])*(Subscript[w, (Subscript[i, n])])
where the transformation matrices (Subscript[w, (Subscript[i, 1])]),…,(Subscript[w, (Subscript[i, n])]) are chosen at random from the set W, then it turns out that the points (Subscript[P, 0]),…,(Subscript[P, n]),… form a dense subset of the fractal determined by the the functions W, so if you display enough of these points you will get a good idea of the shape of the fractal.  Your code will be written so that you will first display (Subscript[P, 0]),then (Subscript[P, 0]),(Subscript[P, 1]),then (Subscript[P, 0]),(Subscript[P, 1]),(Subscript[P, 2]),and so on.  You will stop when the number of points is sufficiently large that you get a good idea of the shape of the fractal.  Note that when we apply a transformation matrix to a point, we multiply by placing the point on the left and the matrix on the right.

The functions below build transformation matrices.  In particular
	trans[v] generates the 3x3 matrix that translate points by the vector v;
	rotQ(θ, Q) generates the 3x3 matrix that rotates points about the point Q by the angle θ;
	scl(s,Q) generates the 3x3 matrix that scales the distance of arbitrary points to the fixed point Q by the scale factor s.
The transformations you need to build fractals will be given to you, so you will not need to define these functions.  Nevertheless you must enable these functions so that you can use them later in the problem.

rot[angle_]:=N[(({{Cos[angle Degree], Sin[angle Degree], 0}, {-Sin[angle Degree], Cos[angle Degree], 0}, {0, 0, 1}}))];

scl[scalefactor_]:=(({{scalefactor, 0, 0}, {0, scalefactor, 0}, {0, 0, 1}}));

trans[vector_]:=(({{1, 0, 0}, {0, 1, 0}, {vector[[1]], vector[[2]], 1}}))


rotQ[angle_,Q_]:=rot[angle].trans[Q-Q.rot[angle]]

sclQ[scalefactor_,Q_]:=scl[scalefactor].trans[Q-Q.scl[scalefactor]]

Problems

In the following problems you will generate code that builds a fractal point by point from a set of matrices by repeatedly multiplying a point in the fractal by a matrix chosen at random from a fixed set of matrices.  When performing the matrix multiplication, the point should be on the left of the multiplication sign and the matrix on the right.  The points will be stored in a global variable called ptlist.  I will give you the matrices;  you will write the code to generate points on the corresponding fractal.

1. Write a function buildnewpts that takes as input a list of 3x3 matrices, and appends one new point to the global variable ptlist by selecting at random a matrix from the list of matrices and applying this matrix to the last point in ptlist.  (Hint:  Remember to represent your points with 3 coordinates, where the third coordinate is always 1.)

2. Modify your function buildnewpts so that it takes as input a list of 3x3 matrices and an integer n, and appends n new points to ptlist by repeating the function buildnewpts in Problem 1 a total of n times.

3.  To get started, you need to find a single point on the fractal.  To find a point on the fractal, you can select a random point in the plane and apply many times (10 is usually enough) a random a matrix from the list of matrices.  Write a function startpt that takes as input a list of matrices and produces as output a single point on the associated fractal.

4.  Modify your function startpt so that it takes as input a list of matrices and initializes ptlist to a list consisting of a single point on the fractal.  (Hint:  Remember that ptlist must contain a list of points, and that a point is a list of numbers, so a point is not a list of points.)

5.  Write a function displayptlist that displays the points in the global variable ptlist.  Remember that the points in ptlist are represented by three coordinates, where the third coordinate is always one.  You may want to get rid of this third coordinate before you try to display your points in the plane.  Turn off the axes so that only the points are displayed.

6.  Using your functions buildnewpts, startpt, and displayptlist, display the four fractals generated by the following four sets of transformation matrices W.  You should continue to display about 1000 additional points at a time until you get a good feel for the shape of the fractal.

First Fractal

Clear[W];

origin={0,0,1};
ivec={1,0,0};

W={scl[.5],sclQ[.5,origin.trans[ivec]],sclQ[.5,origin.trans[ivec].rot[60]]};

Second Fractal

Clear[W];

origin={0,0,1};
jvec={0,1,0};

W={sclQ[.5,origin],trans[jvec].sclQ[.5,origin.trans[jvec]],trans[jvec].sclQ[.5,origin.trans[jvec]].rotQ[30,origin.trans[jvec]],trans[jvec].sclQ[.5,origin.trans[jvec]].rotQ[-30,origin.trans[jvec]]};

Third Fractal

Clear[W];

W=Table[scl[1/3].trans[{2/3,0,1}].rot[60 i],{i,6}];

Fourth Fractal

Clear[W];

ivec={1,0,0};

W={scl[.5],scl[.5].trans[ivec],rot[90].scl[.5].trans[2ivec].trans[ivec.rot[90]]};