{VERSION 4 0 "IBM INTEL NT" "4.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 1" -1 3 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 4 1 0 1 0 2 2 0 1 }{PSTYLE "Warning" -1 7 1 {CSTYLE "" -1 -1 "Courier " 1 10 0 0 255 1 2 2 2 2 2 1 1 1 3 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 } {PSTYLE "Maple Output" -1 11 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 3 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Outpu t" -1 12 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 } 1 3 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Title" -1 18 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 1 2 2 2 1 1 1 1 }3 1 0 0 12 12 1 0 1 0 2 2 19 1 }{PSTYLE "Author" -1 19 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 8 8 1 0 1 0 2 2 0 1 }{PSTYLE "Normal" -1 256 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 0 0 1 0 1 0 2 2 0 1 }} {SECT 0 {PARA 18 "" 0 "" {TEXT -1 12 "Midterm Exam" }}{PARA 19 "" 0 " " {TEXT -1 50 "Applied Symbolic Computation (CS 480/680 sec. 504)" }} {PARA 256 "" 0 "" {TEXT -1 9 "Fall 2001" }}{PARA 256 "" 0 "" {TEXT -1 14 "Jeremy Johnson" }}{PARA 0 "" 0 "" {TEXT -1 5 "Name:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 13 "Instructions:" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 594 "This is \+ a takehome exam that is intended to be done using Maple. Solutions to the exam must be provided in this worksheet. All work must be done a lone. Students are allowed to consult course notes, assignment soluti ons, and worksheets, and Maple's online help facility. No additional \+ resources may be used. All exams must be completed individually. If \+ you have a question, you mail send me email. The exam must be turned \+ in by 10 AM on Tuesday Oct. 30, 2001. No late exams will be accepted. The exam must be submitted by email or using submit. I will confir m submission of all exams." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 164 "The exam has five questions, each worth 20 point s. Do as many of the questions as you can. Partial credit will be aw arded. Don't forget to write your name above." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{SECT 1 {PARA 3 "" 0 " " {TEXT -1 38 "Question 1 (Cartesian Product of Sets)" }}{PARA 0 "" 0 "" {TEXT -1 110 "Let A and B be finite sets. The Cartesian product of A and B is the set of pairs (a,b) for a in A and b in B." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 71 "a) Write a Maple f unction to compute the Cartesian product of two sets." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 164 "b) Maple has a function (cartprod) in the combinat package. Look up this func tion using Maple's help facility. Provide an example to show how this function works." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 52 "Ques tion 2 (A Program to Compute n Digits of sin(x))" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 46 "Write a Maple procedure that computes sin(x), " } {XPPEDIT 18 0 "0 <= x;" "6#1\"\"!%\"xG" }{TEXT -1 5 " and " }{XPPEDIT 18 0 "x <= Pi/2;" "6#1%\"xG*&%#PiG\"\"\"\"\"#!\"\"" }{TEXT -1 244 "to \+ n digits of accuracy. Your procedure should take as input the numbers x and n and should return an n-digit approximation of sin(x). You ne ed to use Taylor's theorem to determine the number of terms necessary \+ to obtain the desired accuracy." }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 54 "Question 3 (Fast Computation of the Fibonacci Numbers)" }}{PARA 0 "" 0 "" {TEXT -1 141 "The following matrix can be used to compute the \+ Fibonacci numbers. Recall that the Fibonacci numbers are defined by t he following recurrence" }}{PARA 0 "" 0 "" {TEXT -1 11 "relation: " } {XPPEDIT 18 0 "\{f[0] = 0, f[1] = 1, f[n] = f[n-1]+f[n-2], 1 < n\};" " 6#<&/&%\"fG6#\"\"!F(/&%\"fG6#\"\"\"F-/&%\"fG6#%\"nG,&&%\"fG6#,&F2F-F-! \"\"F-&%\"fG6#,&F2F-\"\"#F8F-2F-F2" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "with(linalg):" }}{PARA 7 "" 1 "" {TEXT -1 80 "Warning , the protected names norm and trace have been redefined and unprotect ed\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "F := matrix([[0,1], [1,1]]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"FG-%'matrixG6#7$7$\"\" !\"\"\"7$F+F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "evalm(F &* [f[n-2],f[n-1]]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'vectorG6#7$&% \"fG6#,&%\"nG\"\"\"F,!\"\",&F'F,&F(6#,&F+F,\"\"#F-F," }}}{PARA 0 "" 0 "" {TEXT -1 6 "Since " }{XPPEDIT 18 0 "f[n] = f[n-1]+f[n-2];" "6#/&%\" fG6#%\"nG,&&F%6#,&F'\"\"\"F,!\"\"F,&F%6#,&F'F,\"\"#F-F," }{TEXT -1 35 " , the previous vector is equal to " }{XPPEDIT 18 0 " [f[n-1],f[n]]" "6#7$&%\"fG6#,&%\"nG\"\"\"F)!\"\"&F%6#F(" }{TEXT -1 2 ". " }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 74 "a) Use Maple to c ompute powers of the F matrix. What are the entries of " }{XPPEDIT 18 0 "F^n" "6#)%\"FG%\"nG" }{TEXT -1 10 " equal to?" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 65 "b) Recall the b inary powering algorithm presented in Lecture 4. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "Powerrec := \+ proc(M,e)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 29 " if e = 0 then RETURN (1) fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 47 " RETURN(Powerrec(M,floo r(e/2))^2*M^(e mod 2));" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%)PowerrecGR6$%\"MG%\"eG6\"F)F)C$@$/9 %\"\"!-%'RETURNG6#\"\"\"-F06#*&)-F$6$9$-%&floorG6#,$F-#F2\"\"#F?F2)F9- %$modG6$F-F?F2F)F)F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }} }{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 27 "This alg orithm can compute " }{XPPEDIT 18 0 "x^n" "6#)%\"xG%\"nG" }{TEXT -1 7 " using " }{XPPEDIT 18 0 "O(log(n))" "6#-%\"OG6#-%$logG6#%\"nG" } {TEXT -1 308 " multiplications. Write a Maple procedure based on this algorithm and the properties of the F matrix (care of part (1)) to co mpute the n-th Fibonacci number. What is the asymptotic computing tim e of your function as a function of n (you may assume that all integer arithmetic operations take constant time." }}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 64 "Question \+ 4 (Number of Division Steps in the Euclidean Algorithm)" }}{PARA 0 "" 0 "" {TEXT -1 249 "In Lecture 4, I presented two versions (iterative a nd recursive) of the Euclidean algorithm for computing the greatest co mmon divisor of two integers. In this question you will investigate t he number of divisons required by the Euclidean algorithm." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 209 "I am restarting \+ Maple here so that we can use the original trace function. The linear algebra package redefines trace to the matrix trace function. In thi s question you will trace the gcd functions provides." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "# A recursive procedure f or computing the gcd of two integers." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "mygcd := proc(a::nonnegint,b::nonnegint)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "# assume a >= b." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 29 " if b = 0 then RETURN(a) fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 " RETURN(mygcd(b, a mod b));" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 " end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&mygcdGR6$'%\"aG%*nonnegint G'%\"bGF)6\"F,F,C$@$/9%\"\"!-%'RETURNG6#9$-F36#-F$6$F0-%$modG6$F5F0F,F ,F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "mygcdit := proc(a,b) " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 " local a1,a2,a3,q;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 " a1 := a; a2 := b;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 " while (a2 <> 0) do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 " a3 := a1 mod a2;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 " q := floor(a1/a2);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 " a1 := a2; \+ a2 := a3;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 " od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 " RETURN(a1);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%(mygcditGR6$%\"aG%\"bG6&% #a1G%#a2G%#a3G%\"qG6\"F.C&>8$9$>8%9%?(F.\"\"\"F7F.0F4\"\"!C&>8&-%$modG 6$F1F4>8'-%&floorG6#*&F1F7F4!\"\">F1F4>F4F<-%'RETURNG6#F1F.F.F." }}} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 202 "a) Use \+ Maple's trace function to trace the execution of mygcd and mygcdit wit h inputs equal to consecutive Fibonacci numbers. From your examples, \+ determine the number of divisions required to compute " }{XPPEDIT 18 0 "gcd(f[n],f[n-1])" "6#-%$gcdG6$&%\"fG6#%\"nG&F'6#,&F)\"\"\"F-!\"\"" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 236 "b) Generate random pairs of integers (a,b) between 1 and N for different values of N and for each N, determine the avera ge number of division steps required by mygcdit. You will have to mod ify mygcdit to count the number of divisions." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 221 "Make a conjectur e based on the data obtained part (b) as to what function of n (asymp totically) the average number of divisions in the Euclidean algorithm \+ is equal to. Use a Maple computation to support your conjecture." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 " " {TEXT -1 28 "Question 5 (Newton's Method)" }}{PARA 0 "" 0 "" {TEXT -1 329 "In class we reviewed Newton's method for approximating a root \+ of a function of one variable. The Newton iteration is given by x' = \+ x - f(x)/f'(x). Newton's method can be generalized to find intersecti ons of curves. Let f(x,y) and g(x,y) be two functions of two variable s. The Jacobian of f(x,y) and g(x,y) is the 2 X 2 matrix" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "with(linalg);" }}{PARA 7 "" 1 "" {TEXT -1 80 "Warning, the protected names norm and trace have been red efined and unprotected\n" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7^r%.Block DiagonalG%,GramSchmidtG%,JordanBlockG%)LUdecompG%)QRdecompG%*Wronskian G%'addcolG%'addrowG%$adjG%(adjointG%&angleG%(augmentG%(backsubG%%bandG %&basisG%'bezoutG%,blockmatrixG%(charmatG%)charpolyG%)choleskyG%$colG% 'coldimG%)colspaceG%(colspanG%*companionG%'concatG%%condG%)copyintoG%* crossprodG%%curlG%)definiteG%(delcolsG%(delrowsG%$detG%%diagG%(diverge G%(dotprodG%*eigenvalsG%,eigenvaluesG%-eigenvectorsG%+eigenvectsG%,ent ermatrixG%&equalG%,exponentialG%'extendG%,ffgausselimG%*fibonacciG%+fo rwardsubG%*frobeniusG%*gausselimG%*gaussjordG%(geneqnsG%*genmatrixG%%g radG%)hadamardG%(hermiteG%(hessianG%(hilbertG%+htransposeG%)ihermiteG% *indexfuncG%*innerprodG%)intbasisG%(inverseG%'ismithG%*issimilarG%'isz eroG%)jacobianG%'jordanG%'kernelG%*laplacianG%*leastsqrsG%)linsolveG%' mataddG%'matrixG%&minorG%(minpolyG%'mulcolG%'mulrowG%)multiplyG%%normG %*normalizeG%*nullspaceG%'orthogG%*permanentG%&pivotG%*potentialG%+ran dmatrixG%+randvectorG%%rankG%(ratformG%$rowG%'rowdimG%)rowspaceG%(rows panG%%rrefG%*scalarmulG%-singularvalsG%&smithG%,stackmatrixG%*submatri xG%*subvectorG%)sumbasisG%(swapcolG%(swaprowG%*sylvesterG%)toeplitzG%& traceG%*transposeG%,vandermondeG%*vecpotentG%(vectdimG%'vectorG%*wrons kianG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 79 "J := matrix([[diff (f(x,y),x),diff(f(x,y),y)],[diff(g(x,y),x),diff(g(x,y),y)]]);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"JG-%'matrixG6#7$7$-%%diffG6$-%\"fG 6$%\"xG%\"yGF0-F+6$F-F17$-F+6$-%\"gGF/F0-F+6$F7F1" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 119 "Let v = [x,y] be a point in the plane. The two-dimensional version of Newton's method is give n by the matrix equation:" }}{PARA 0 "" 0 "" {TEXT -1 209 "v' = v - J ^(-1)(x,y) * [f(x,y),g(x,y)], where J^(-1)(x,y) is the inverse of the \+ Jacobian matrix evaluated at [x,y], and * is the matrix vector product of the matrix J^(-1)(x,y) and the vector [f(x,y),g(x,y)]." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 141 "In this question you will explore the use of Newton's method to find the intersection \+ points of C(x,y) = x^2 + y^2 - 4 and H(x,y) = x*y - 1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 213 "Part 1) Plot the c urves C(x,y) = 0 and H(x,y) = 0. Make sure to include all intersectio n points. Use Maple's solve, allvalues, and evalf to find exact and n umeric solutions to the intersections of these curves." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 249 "Part 2) Compute th e Jacobian of C(x,y) and H(x,y). Compute the determinant of the Jaco bian and find the solution to the equation that sets the determinant e qual to zero. Invert the Jacobian. For what values of x and y is thi s matrix invertible?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 131 "Part 3) Initially set v = [2.0,1.0]. Show that Newto n's method converges to the intersection point closest to this initial value." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 577 "Part 4) Write a Maple procedure that applies 10 iterations of Ne wton's method to C(x,y) and H(x,y) given an initial value [x,y]. Your procedure must check to see of the Jacobian is invertible. If not, t hen it should return 0, otherwise if Newton's method converges you sho uld return the intersection point that it converges to. You should la bel the points 1, 2, 3, and 4 and return one of these four numbers. Y ou can consider convergence by checking to see if the distance between the last step in Newton's method and one of the 4 intersection points is less than 10^(-8)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 328 "Call your procedure for the point on the grid -3 <= x <= 3 and -3 <= y <= 3 in steps of .25. Put all of the points that \+ have a non-invertible Jacobian in one set, all of the points that conv erge to point 1 in a set, all of the points that converge to point 2 i n a set, and so on through point 4. Use Maple's pointplot to plot" } }{PARA 0 "" 0 "" {TEXT -1 94 "the points in the grid. Use a different color for the points in each of the 5 different sets." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 24 "Extra Credit (10 points)" }}{PARA 0 "" 0 "" {TEXT -1 37 "Find a n integral polynomial that has " }{XPPEDIT 18 0 "sqrt(3) + sqrt(5)" "6 #,&-%%sqrtG6#\"\"$\"\"\"-F%6#\"\"&F(" }{TEXT -1 11 " as a root." }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{MARK "8 0" 555 } {VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }