{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 "Diagnostic" -1 9 1 {CSTYLE "" -1 -1 "Courier" 1 10 64 128 64 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 Out put" -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 Output" -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 "Maple Plot" -1 13 1 {CSTYLE "" -1 -1 "Time s" 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 } {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 20 "Name: Jeremy Johnso n" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 13 "Inst ructions:" }}{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 m ust be done alone. Students are allowed to consult course notes, assi gnment solutions, and worksheets, and Maple's online help facility. N o additional resources may be used. All exams must be completed indiv idually. If you have a question, you mail send me email. The exam mu st 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 confirm submission of all exams." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 164 "The exam has five questions, each w orth 20 points. Do as many of the questions as you can. Partial cred it will be awarded. 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 Cartes ian 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) W rite a Maple function to compute the Cartesian product of two sets." } }{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "Cart := proc(A::set, B::set)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "local x, y, S;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "S := \{\};" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "for x in A do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 " for y in B do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 25 " S := S union \{[x,y]\};" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 " od ;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "RETURN(S);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end; " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%CartGR6$'%\"AG%$setG'%\"BGF)6%% \"xG%\"yG%\"SG6\"F0C%>8&<\"?&8$9$%%trueG?&8%9%F8>F3-%&unionG6$F3<#7$F6 F:-%'RETURNG6#F3F0F0F0" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "A := \{a,b,c\}; B := \{d,e,f\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% \"AG<%%\"aG%\"bG%\"cG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"BG<%%\"fG %\"dG%\"eG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "Cart(A,B);" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#<+7$%\"aG%\"fG7$F%%\"dG7$F%%\"eG7$%\" bGF&7$F,F(7$F,F*7$%\"cGF&7$F0F(7$F0F*" }}}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 65 "Here is another approach using a func tional style of programming." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "map((x)->map((y)->[x,y],B),A );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<%<%7$%\"bG%\"fG7$F&%\"dG7$F&%\" eG<%7$%\"cGF'7$F.F)7$F.F+<%7$%\"aGF'7$F3F)7$F3F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "foldl(`union`,\{\},op(%));" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#<+7$%\"aG%\"fG7$F%%\"dG7$F%%\"eG7$%\"bGF&7$F,F(7$F,F* 7$%\"cGF&7$F0F(7$F0F*" }}}{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 function using Maple's help facility. Provide \+ an example to show how this function works." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 97 "Maple's cartprod function uses \+ yet another approach. This approach returns an iterator function." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "with(combinat,cartprod);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7#%)ca rtprodG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 67 "T:=cartprod([A,B ]):\nwhile not T[finished] do T[nextvalue]() end do;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$%\"aG%\"fG " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$%\"aG%\"dG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$%\"aG%\"eG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$%\"bG %\"fG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$%\"bG%\"dG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$%\"bG%\"eG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$ %\"cG%\"fG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$%\"cG%\"dG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$%\"cG%\"eG" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 92 "To see how this is done, look at the worksheet from lecture 5 on Advanced Maple Programming." }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 52 "Question 2 (A Program to Compute n Digits of sin(x))" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 46 "Write a Maple proce dure 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 sh ould take as input the numbers x and n and should return an n-digit ap proximation of sin(x). You need to use Taylor's theorem to determine \+ the number of terms necessary to obtain the desired accuracy." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "series(sin(x),x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#++%\"xG\"\"\"F%#!\"\"\"\"'\"\"$#F%\"$?\"\"\" &-%\"OG6#F%F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "diff(sin(x ),x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%$cosG6#%\"xG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "diff(sin(x),x,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,$-%$sinG6#%\"xG!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "diff(sin(x),x,x,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#,$-%$cosG6#%\"xG!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 " diff(sin(x),x$4);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%$sinG6#%\"xG" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "sin(0);" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "co s(0);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 23 "plot(sin(x),x=0..Pi/2);" }}{PARA 13 "" 1 "" {GLPLOT2D 400 300 300 {PLOTDATA 2 "6%-%'CURVESG6$7S7$$\"\"!F)F(7$$\"3N GK5j*))QU$!#>$\"3QsLeI+ABMF-7$$\"3DXXYUk*HS'F-$\"3]DS+L@i)R'F-7$$\"3=N 68yVJ`(*F-$\"3_b&ehJeyt*F-7$$\"3%3h%eRSe78!#=$\"3<&Q%f]#=)38F=7$$\"3k+ ,hQPB[;F=$\"3V-yj65yS;F=7$$\"3'H#*ed(RUf>F=$\"3q)*)ys&)4p%>F=7$$\"3kHX [TMk\"G#F=$\"3G3RBS#)*=E#F=7$$\"3Saq%HF=$\"3=7dd?+e/HF=7$$\"3)pq'4OKt)G$F=$\"3c0jx$Rp(HKF=7$$\"3#f/ N#RTo*e$F=$\"3ML>uye38NF=7$$\"3Ut79wN[GRF=$\"3V3zj5M@GQF=7$$\"3/VrOc6q%F=7$$\"31\\,oR/A[_F=$\"3SMGBr+f5]F=7$$\"3uvW/X(*RG,:eF=7$$\"3.n3p46^WlF=$\"33g0zi&Qs3'F=7$$\"3oHyF.C6noF=$\"3h +)=j,t*RjF=7$$\"3(*zx.5Ir.sF=$\"3Qz3MFxj'f'F=7$$\"3'pz!QUu\"G^(F=$\"3$ [8q$y.wDoF=7$$\"3A\"3@7LGi%yF=$\"3wm47uKelqF=7$$\"3)3\"HIT&[D>)F=$\"3M (RvZssjI(F=7$$\"3gv)\\AI@S\\)F=$\"3C>#p\"po&)3vF=7$$\"3vn()=V,i>))F=$ \"3%4zeG%\\()>xF=7$$\"3'G:[dg&*f:*F=$\"31()\\)y]!GHzF=7$$\"3sSt6rL2&[* F=$\"3g&H%*=Uja7)F=7$$\"3mka(*HIZ.)*F=$\"3%3R7+w2pI)F=7$$\"3Em\"[l:+d, \"!#<$\"3Q?Zs+w\\)\\)F=7$$\"3c!3XyEmu/\"F_u$\"3Ih!)R3tfh')F=7$$\"3sJ_* >P$Q\"3\"F_u$\"3VZPF_)*3E))F=7$$\"3.M\"G%4t676F_u$\"3kW#3Hj\"Qm*)F=7$$ \"3co*Q4iq'*z.@\"F_u$\"3Y(Q,up+vN*F=7$$\"34Q$[)>&*oU7F_u$\"3OZ!)zP7am%* F=7$$\"3I^lOFY^w7F_u$\"3-w%)pSt5q&*F=7$$\"3`!)f6EA448F_u$\"3-KPDS[]f'* F=7$$\"3=;T7EvSU8F_u$\"3B\"='y#[C.u*F=7$$\"3a_wiepWv8F_u$\"3$oY$>Q\"*z 4)*F=7$$\"3U$obdw1eS\"F_u$\"3#4Wi\"*p+U')*F=7$$\"3s$)o#3`-1W\"F_u$\"3a Z!3__n`\"**F=7$$\"3-#*)4zFC " 0 " " {MPLTEXT 1 0 15 "sn := proc(n,a)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "local s,k,x,f;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "k := 0;" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "while (a^(2*k+3)/(2*k+3)! > 1/2*10^ (-n)) do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 " k := k + 1;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 46 " f := convert(series(sin(x),x,2*k+3), polynom);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "RETURN(evalf(subs(x=a,f),n));" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#snGR6$%\"nG %\"aG6&%\"sG%\"kG%\"xG%\"fG6\"F.C&>8%\"\"!?(F.\"\"\"F4F.2,$)\"#5,$9$! \"\"#F4\"\"#*&)9%,&F1F=\"\"$F4F4-%*factorialG6#FAF;>F1,&F1F4F4F4>8'-%( convertG6$-%'seriesG6%-%$sinG6#8&FSFA%(polynomG-%'RETURNG6#-%&evalfG6$ -%%subsG6$/FSF@FIF:F.F.F." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "sn(20,1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"5l1l*y![)4ZT)!#?" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "evalf(sin(1),20);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"5l1l*y![)4ZT)!#?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "sn(50,1/2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$ \"SgSzO.=3)Qrb@NzGt-+.UgQbUz%!#]" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "evalf(sin(1/2),50);" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#$\"SgSzO.=3)Qrb@NzGt-+.UgQbUz%!#]" }}}}{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 com pute the Fibonacci numbers. Recall that the Fibonacci numbers are def ined by the following recurrence" }}{PARA 0 "" 0 "" {TEXT -1 11 "relat ion: " }{XPPEDIT 18 0 "\{f[0] = 0, f[1] = 1, f[n] = f[n-1]+f[n-2], 1 \+ < n\};" "6#<&/&%\"fG6#\"\"!F(/&F&6#\"\"\"F,/&F&6#%\"nG,&&F&6#,&F0F,F,! \"\"F,&F&6#,&F0F,\"\"#F5F,2F,F0" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "fib := proc(n) option remember;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "if (n = 0) then RETURN(0); fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "if (n = 1) then RETURN(1); fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "RETURN(fib(n-1) + fib(n-2));" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$fibGR6#%\"nG6\"6#%)rem emberGF(C%@$/9$\"\"!-%'RETURNG6#F/@$/F.\"\"\"-F16#F5-F16#,&-F$6#,&F.F5 F5!\"\"F5-F$6#,&F.F5\"\"#F>F5F(F(F(" }}}{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(6#,&F+F,\"\"#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 24 "seq(evalm( F^n),n=1..10);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6,-%'matrixG6#7$7$\"\" !\"\"\"7$F)F)-F$6#7$F*7$F)\"\"#-F$6#7$F.7$F/\"\"$-F$6#7$F37$F4\"\"&-F$ 6#7$F87$F9\"\")-F$6#7$F=7$F>\"#8-F$6#7$FB7$FC\"#@-F$6#7$FG7$FH\"#M-F$6 #7$FL7$FM\"#b-F$6#7$FQ7$FR\"#*)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "seq(fib(n),n=1..11);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6-\"\"\" F#\"\"#\"\"$\"\"&\"\")\"#8\"#@\"#M\"#b\"#*)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "F^n = matrix([[f[n-1],f[n]],[f[n],f[n+1]]]);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#/)%\"FG%\"nG-%'matrixG6#7$7$&%\"fG6#,& F&\"\"\"F0!\"\"&F-6#F&7$F2&F-6#,&F&F0F0F0" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 69 "This can be proved by induction , using the property of F shown above." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 65 "b) Recall the binary powering algorit hm 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,floor(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%\"\"!-%'RET URNG6#\"\"\"-F06#*&)-F$6$9$-%&floorG6#,$F-#F2\"\"#F?F2)F9-%$modG6$F-F? F2F)F)F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "MatPower := pro c(M::matrix,e::nonnegint)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 38 " loca l n,M2; n := linalg[rowdim](M);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 55 " if e = 0 then RETURN(Matrix(n,n,shape=identity)); fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 40 " M2 := evalm(MatPower(M,floor(e/2))^2);" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 71 " if type(e,odd) then RETURN(evalm( M2 &* M)) else RETURN(evalm(M2)) fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%)MatPowerGR6$'%\"MG%'ma trixG'%\"eG%*nonnegintG6$%\"nG%#M2G6\"F0C&>8$-&%'linalgG6#%'rowdimG6#9 $@$/9%\"\"!-%'RETURNG6#-%'MatrixG6%F3F3/%&shapeG%)identityG>8%-%&evalm G6#*$)-F$6$F:-%&floorG6#,$F=#\"\"\"\"\"#FWFV@%-%%typeG6$F=%$oddG-F@6#- FK6#-%#&*G6$FIF:-F@6#-FK6#FIF0F0F0" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "seq(MatPower(F,n),n=0..10);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6--%'RTABLEG6$\"))=*eD-%'MATRIXG6#7$7$\"\"\"\"\"!7$F-F,-% 'matrixG6#7$F.7$F,F,-F06#7$F37$F,\"\"#-F06#7$F77$F8\"\"$-F06#7$F<7$F= \"\"&-F06#7$FA7$FB\"\")-F06#7$FF7$FG\"#8-F06#7$FK7$FL\"#@-F06#7$FP7$FQ \"#M-F06#7$FU7$FV\"#b-F06#7$FZ7$Fen\"#*)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "FastFib := proc(n)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 " local F,Fn;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 " if (n = 0) t hen RETURN(0); fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 " if (n = 1) \+ then RETURN(1); fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 37 " F := linal g[matrix]([[0,1],[1,1]]);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 " Fn : = MatPower(F,n-1);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 18 " RETURN(Fn[2 ,2]);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%(FastFibGR6#%\"nG6$%\"FG%#FnG6\"F+C'@$/9$\"\"!-%'RETU RNG6#F0@$/F/\"\"\"-F26#F6>8$-&%'linalgG6#%'matrixG6#7$7$F0F67$F6F6>8%- %)MatPowerG6$F:,&F/F6F6!\"\"-F26#&FE6$\"\"#FOF+F+F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "seq(FastFib(n),n=0..10);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6-\"\"!\"\"\"F$\"\"#\"\"$\"\"&\"\")\"#8\"#@\"#M\"#b " }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 27 "This algorithm 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." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 219 "The number of matrix multiplic ations is O(log(n)). If we assume constant time for integer arithmeti c operations [not a valid assumption], then the time to multiply 2 X 2 matrics is O(1) and the total time is O(log(n))." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "seq(time(Fas tFib(1000*n)),n=1..100);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6`q$\"$@#!\" $$\"$S#F%$\"$z\"F%$\"$h#F%$\"$]#F%$\"$q#F%F.$\"$!GF%F.$\"$p#F%$\"$!HF% $\"$,$F%$\"$z#F%F6F8$\"$@$F%F8$\"$*HF%$\"$5$F%$\"$>$F%F>$\"$I$F%$\"$T$ F%$\"$\\$F%FB$\"$R$F%$\"$J%F%$\"$f$F%FDFL$\"$^$F%$\"$z$F%FJ$\"$q$F%FR$ \"$\"QF%$\"$p$F%$\"$6%F%$\"$!\\F%$\"$I%F%$\"$^%F%$\"$?%F%$\"$?&F%$\"$h %F%$\"$\\%F%$\"$g%F%$\"$J&F%$\"$![F%$\"$]&F%F^o$\"$r%F%FboFhoFZFZ$\"$! eF%$\"$5&F%$\"$r&F%F^p$\"$>&F%$\"$\"fF%$\"$@&F%$\"$+'F%FhoFhoFhpFho$\" $J'F%$\"$T&F%$\"$S'F%$\"$q&F%F`q$\"$\"pF%Fhp$\"$@(F%$\"$g'F%$\"$h(F%Fb q$\"$r(F%$\"$?(F%$\"$#zF%$\"$,(F%$\"$!zF%Fdq$\"$+)F%$\"$J)F%$\"$](F%$ \"$T)F%Fjq$\"$])F%$\"$^)F%FbrF\\s$\"$r)F%$\"$,)F%$\"$+*F%$\"$\"*)F%$\" $I)F%$\"$#*)F%$\"$!*)F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "T := [%];" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"TG7`q$\"$@#!\"$$\"$S#F ($\"$z\"F($\"$h#F($\"$]#F($\"$q#F(F1$\"$!GF(F1$\"$p#F($\"$!HF($\"$,$F( $\"$z#F(F9F;$\"$@$F(F;$\"$*HF($\"$5$F($\"$>$F(FA$\"$I$F($\"$T$F($\"$\\ $F(FE$\"$R$F($\"$J%F($\"$f$F(FGFO$\"$^$F($\"$z$F(FM$\"$q$F(FU$\"$\"QF( $\"$p$F($\"$6%F($\"$!\\F($\"$I%F($\"$^%F($\"$?%F($\"$?&F($\"$h%F($\"$ \\%F($\"$g%F($\"$J&F($\"$![F($\"$]&F(Fao$\"$r%F(FeoF[pFgnFgn$\"$!eF($ \"$5&F($\"$r&F(Fap$\"$>&F($\"$\"fF($\"$@&F($\"$+'F(F[pF[pF[qF[p$\"$J'F ($\"$T&F($\"$S'F($\"$q&F(Fcq$\"$\"pF(F[q$\"$@(F($\"$g'F($\"$h(F(Feq$\" $r(F($\"$?(F($\"$#zF($\"$,(F($\"$!zF(Fgq$\"$+)F($\"$J)F($\"$](F($\"$T) F(F]r$\"$])F($\"$^)F(FerF_s$\"$r)F($\"$,)F($\"$+*F($\"$\"*)F($\"$I)F($ \"$#*)F($\"$!*)F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "seq(ev alf(T[n]/(1000*n)),n=1..100);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6`q$\"+ +++5A!#8$\"+++++7F%$\"+nmmmf!#9$\"++++DlF*$\"+++++]F*$\"+++++XF*$\"+dG 9dQF*$\"+++++NF*$\"+++++IF*$\"++++!p#F*$\"+OOOOEF*$\"+LLL3DF*$\"+YQ:Y@ F*$\"++++]@F*$\"++++g=F*$\"+++D1?F*$\"+rkw9F*$\"+++++:F*$\"+'p3E[\"F*$\"+nm;a9F*$\"++++?8F* $\"+ah%QI\"F*$\"+'H'H'f\"F*$\"+dG9#G\"F*$\"+p?'e<\"F*$\"+nmm'>\"F*$\"+ l!eA8\"F*$\"++]P%=\"F*$\"+11118F*$\"+%HN#)3\"F*$\"+dG9d5F*$\"+LLLe5F*$ \"+tH(H(**!#:$\"+Z*y:3\"F*$\"+c-Tc7F*$\"++++v5F*$\"+++++6F*$\"+++++5F* $\"+EBI47F*$\"+tssZ5F*$\"+yxxx**FioFbp$\"+MsyH6F*Fbp$\"+!)*[C7\"F*$\"+ +++?#*Fio$\"+=THN#*Fio$\"+YQ:Y))Fio$\"+\\etP5F*$\"+uS2u!*Fio$\"+4444*) Fio$\"+'G9d.\"F*$\"+@%ot%*)Fio$\"+'eF[%)*Fio$\"+'znSk)Fio$\"++++]')Fio $\"+!fC&)o*Fio$\"+1eA.%)Fio$\"+C&4Q_*Fio$\"+++v$f)Fio$\"+i%Q:Y)Fio$\"+ \"4444*Fio$\"+C_&*3#)Fio$\"+l " 0 "" {MPLTEXT 1 0 41 "seq(evalf(T[n]/log[2](1000*n)),n=1..100);" }} {PARA 12 "" 1 "" {XPPMATH 20 "6`q$\"+Nwe7=#F%$\"+JGbM?F%$\"+6kE^@F%$\"+J3\"Q6#F%$\"+*)*H&f@F%$\"+5dYb?F% $\"+@nUC?F%$\"+OU6g@F%$\"+\"zz7A#F%$\"+S&H:/#F%$\"+%=8a=#F%$\"+Jy96?F% $\"+nXZ)H#F%$\"+(H1`)>F%$\"+^/@:@F%$\"+#e#*4=#F%$\"+AxoKAF%$\"+(yf!f@F %$\"+L2m(G#F%$\"+?LX`BF%$\"+EB])R#F%$\"+&[#yeAF%$\"+)RL9J#F%$\"+6b&y#H F%$\"+%3'3ICF%$\"+B-O+BF%$\"+%oAQT#F%$\"+x*\\DN#F%$\"+\"HVC`#F%$\"+E\\ QrGF%$\"+Y9%zX#F%$\"+M=8^CF%$\"+PfARjPF%$\"+(ym[W$F%$\"+Mt/SMF%$\"+`fhZPF%$\"+(zl1V$F%$\"+]*o1$RF%$\"+ p!>cO$F%$\"+cNPwRF%$\"+A1'p`$F%$\"+:w`KNF%$\"+IB:xUF%$\"+JOP4PF%$\"+,0 5_WF%$\"+l'G12%F%$\"+>_5)o%F%$\"+Hs*>D%F%$\"+H(4*QZF%$\"+\"G50U%F%$\"+ `n@d[F%$\"+@_Y%H%F%$\"+2w^M[F%$\"+*)=g2WF%$\"+0RW&)[F%$\"+_4`p]F%$\"+o #Q2d%F%$\"+Hi " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "# A recursiv e procedure for 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%*nonnegintG'%\"bGF)6\"F,F,C$@$/9%\"\"!-%'RETURNG6#9$-F36#-F$6$F0 -%$modG6$F5F0F,F,F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "mygc dit := proc(a,b)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 " local a1,a2,a 3,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#>%(my gcditGR6$%\"aG%\"bG6&%#a1G%#a2G%#a3G%\"qG6\"F.C&>8$9$>8%9%?(F.\"\"\"F7 F.0F4\"\"!C&>8&-%$modG6$F1F4>8'-%&floorG6#*&F1F7F4!\"\">F1F4>F4F<-%'RE TURNG6#F1F.F.F." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "fib := p roc(n) option remember;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "if (n = \+ 0) then RETURN(0); fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "if (n = 1 ) then RETURN(1); fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "RETURN(fib (n-1) + fib(n-2));" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$fibGR6#%\"nG6\"6#%)rememberGF(C%@$/9$\"\" !-%'RETURNG6#F/@$/F.\"\"\"-F16#F5-F16#,&-F$6#,&F.F5F5!\"\"F5-F$6#,&F.F 5\"\"#F>F5F(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 with inputs equal to consecutive Fibonacci numbers. From your examples, determine the number of divisions required to co mpute " }{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 20 "seq(fib(n),n=0..10);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6-\"\"!\"\"\"F$\"\"#\"\"$\"\"&\"\")\"#8 \"#@\"#M\"#b" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "trace(mygcd );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&mygcdG" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 22 "mygcd(fib(10),fib(9));" }}{PARA 9 "" 1 "" {TEXT -1 31 "\{--> enter mygcd, args = 55, 34" }}{PARA 9 "" 1 "" {TEXT -1 31 "\{--> enter mygcd, args = 34, 21" }}{PARA 9 "" 1 "" {TEXT -1 31 "\{--> enter mygcd, args = 21, 13" }}{PARA 9 "" 1 "" {TEXT -1 30 "\{--> enter mygcd, args = 13, 8" }}{PARA 9 "" 1 "" {TEXT -1 29 "\{--> enter mygcd, args = 8, 5" }}{PARA 9 "" 1 "" {TEXT -1 29 " \{--> enter mygcd, args = 5, 3" }}{PARA 9 "" 1 "" {TEXT -1 29 "\{--> e nter mygcd, args = 3, 2" }}{PARA 9 "" 1 "" {TEXT -1 29 "\{--> enter my gcd, args = 2, 1" }}{PARA 9 "" 1 "" {TEXT -1 29 "\{--> enter mygcd, ar gs = 1, 0" }}{PARA 9 "" 1 "" {TEXT -1 34 "<-- exit mygcd (now in mygcd ) = 1\}" }}{PARA 9 "" 1 "" {TEXT -1 34 "<-- exit mygcd (now in mygcd) \+ = 1\}" }}{PARA 9 "" 1 "" {TEXT -1 34 "<-- exit mygcd (now in mygcd) = \+ 1\}" }}{PARA 9 "" 1 "" {TEXT -1 34 "<-- exit mygcd (now in mygcd) = 1 \}" }}{PARA 9 "" 1 "" {TEXT -1 34 "<-- exit mygcd (now in mygcd) = 1\} " }}{PARA 9 "" 1 "" {TEXT -1 34 "<-- exit mygcd (now in mygcd) = 1\}" }}{PARA 9 "" 1 "" {TEXT -1 34 "<-- exit mygcd (now in mygcd) = 1\}" }} {PARA 9 "" 1 "" {TEXT -1 34 "<-- exit mygcd (now in mygcd) = 1\}" }} {PARA 9 "" 1 "" {TEXT -1 38 "<-- exit mygcd (now at top level) = 1\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "trace(mygcdit);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%( mygcditG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "mygcdit(fib(10) ,fib(9));" }}{PARA 9 "" 1 "" {TEXT -1 33 "\{--> enter mygcdit, args = \+ 55, 34" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#a1G\"#b" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#a2G\"#M" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#a3G \"#@" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"qG\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#a1G\"#M" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#a2G \"#@" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#a3G\"#8" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%\"qG\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#a1 G\"#@" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#a2G\"#8" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%#a3G\"\")" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"qG \"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#a1G\"#8" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#a2G\"\")" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#a3 G\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"qG\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#a1G\"\")" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%# a2G\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#a3G\"\"$" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%\"qG\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# >%#a1G\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#a2G\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#a3G\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"qG\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#a1G\"\"$" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#a2G\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#a3G\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"qG \"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#a1G\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#a2G\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% #a3G\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"qG\"\"#" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%#a1G\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# >%#a2G\"\"!" }}{PARA 9 "" 1 "" {TEXT -1 40 "<-- exit mygcdit (now at t op level) = 1\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 86 "Number of division steps to compute gcd(f ib(n), fib(n-1)) is n-2 [prove by induction]." }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 236 "b) Generate random pair s of integers (a,b) between 1 and N for different values of N and for \+ each N, determine the average number of division steps required by myg cdit. You will have to modify mygcdit to count the number of division s." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "mygcdit := proc(a,b,count::evaln)" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 27 " local a1,a2,a3,q, numdiv;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 34 " a1 := a; a2 := b; numdiv := 0;" }}{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 25 " \+ numdiv := numdiv + 1;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 " a1 := a2; a2 := a3;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 " od; count := \+ numdiv;" }}{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%\"bG'%&countG%&evalnG6'%#a1G%#a2G%#a3G%\"qG%'numdivG 6\"F2C(>8$9$>8%9%>8(\"\"!?(F2\"\"\"F>F20F8F8&-%$modG6$F5F8>8'-%&fl oorG6#*&F5F>F8!\"\">F;,&F;F>F>F>>F5F8>F8FB>9&F;-%'RETURNG6#F5F2F2F2" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "mygcdit(fib(10),fib(9),cou nt);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 6 "count;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\") " }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 221 "Mak e a conjecture based on the data obtained part (b) as to what functio n of n (asymptotically) the average number of divisions in the Euclide an algorithm is equal to. Use a Maple computation to support your con jecture." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "count := evaln(count) ;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&countGF$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "Samples := 10000;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "for n from 1 to 20 do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 48 " N := 100*n: count[n] := 0: print(\"N = \", N):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 " myrand := rand(1..N):" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 28 " for i from 1 to Samples do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 34 " a := myrand(): b := myrand():" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 29 " c := mygcdit(a,b,numdiv):" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 34 " count[n] := count[n] + numdiv:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 " od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 89 " avg [n] := count[n]/Samples: print(\"The average number of divisions = \" ,evalf(avg[n])):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(SamplesG\"&++\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$Q%N~=~6\"\"$+\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$QCTh e~average~number~of~divisions~=~6\"$\"+++?*)R!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$Q%N~=~6\"\"$+#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$QCThe ~average~number~of~divisions~=~6\"$\"+++giX!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$Q%N~=~6\"\"$+$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$QCThe ~average~number~of~divisions~=~6\"$\"+++!)*)[!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$Q%N~=~6\"\"$+%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$QCThe ~average~number~of~divisions~=~6\"$\"+++]$3&!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$Q%N~=~6\"\"$+&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$QCThe ~average~number~of~divisions~=~6\"$\"+++5B`!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$Q%N~=~6\"\"$+'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$QCThe ~average~number~of~divisions~=~6\"$\"+++I_a!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$Q%N~=~6\"\"$+(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$QCThe ~average~number~of~divisions~=~6\"$\"++++6c!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$Q%N~=~6\"\"$+)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$QCThe ~average~number~of~divisions~=~6\"$\"+++gLd!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$Q%N~=~6\"\"$+*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$QCThe ~average~number~of~divisions~=~6\"$\"+++!4!e!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$Q%N~=~6\"\"%+5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$QCThe ~average~number~of~divisions~=~6\"$\"+++qBf!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$Q%N~=~6\"\"%+6" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$QCThe ~average~number~of~divisions~=~6\"$\"+++5tf!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$Q%N~=~6\"\"%+7" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$QCThe ~average~number~of~divisions~=~6\"$\"+++!=-'!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$Q%N~=~6\"\"%+8" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$QCThe ~average~number~of~divisions~=~6\"$\"+++I0h!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$Q%N~=~6\"\"%+9" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$QCThe ~average~number~of~divisions~=~6\"$\"+++q)>'!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$Q%N~=~6\"\"%+:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$QCThe ~average~number~of~divisions~=~6\"$\"+++IGi!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$Q%N~=~6\"\"%+;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$QCThe ~average~number~of~divisions~=~6\"$\"+++?(G'!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$Q%N~=~6\"\"%+<" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$QCThe ~average~number~of~divisions~=~6\"$\"+++qJj!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$Q%N~=~6\"\"%+=" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$QCThe ~average~number~of~divisions~=~6\"$\"+++?ij!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$Q%N~=~6\"\"%+>" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$QCThe ~average~number~of~divisions~=~6\"$\"+++gLk!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$Q%N~=~6\"\"%+?" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$QCThe ~average~number~of~divisions~=~6\"$\"++++#\\'!\"*" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 37 "seq(evalf(count[n]/(100*n)),n=1..20);" }} {PARA 12 "" 1 "" {XPPMATH 20 "66$\"+++?*)R!\"($\"+++I\"G#F%$\"+LL$*H;F %$\"++](3F\"F%$\"+++ik5F%$\"+nm;(3*!\")$\"+'G9d,)F0$\"++++nrF0$\"+WWWX kF0$\"+++qBfF0$\"+444IaF0$\"+nm;=]F0$\"+:YQ'p%F0$\"+dGkFWF0$\"+++?_TF0 $\"+++]HRF0$\"+7%HXs$F0$\"+cbbMNF0$\"+j_5'Q$F0$\"++++YKF0" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "seq(evalf(count[n]/log(100*n)),n=1. .20);" }}{PARA 12 "" 1 "" {XPPMATH 20 "66$\"+QxVi')!\"'$\"+zJT6')F%$\" +wv!Hd)F%$\"+W*pX[)F%$\"+)ojac)F%$\"+NxIB&)F%$\"+J&**\\c)F%$\"+S>Jx&)F %$\"+u?tF&)F%$\"+vSVv&)F%$\"+W[EH&)F%$\"+**)yK\\)F%$\"+#z?\\^)F%$\"+_R uc&)F%$\"+MV\\;&)F%$\"+A!H=_)F%$\"+&)))>7&)F%$\"+^'yz[)F%$\"+Tcw@&)F%$ \"+`54T&)F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "with(plots): " }}{PARA 7 "" 1 "" {TEXT -1 50 "Warning, the name changecoords has be en redefined\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 71 "points := zip((x,y)->[x,y],[seq(n,n=1..20)],convert(eval(count),list));" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%'pointsG767$\"\"\"\"&#*)R7$\"\"#\"&E c%7$\"\"$\"&)*)[7$\"\"%\"&N3&7$\"\"&\"&JK&7$\"\"'\"&BX&7$\"\"(\"&5h&7$ \"\")\"&Ot&7$\"\"*\"&4!e7$\"#5\"&P#f7$\"#6\"&J(f7$\"#7\"&=-'7$\"#8\"&` 5'7$\"#9\"&()>'7$\"#:\"&$Gi7$\"#;\"&sG'7$\"#<\"& \"&OV'7$\"#?\"&?\\'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "poin tplot(points);" }}{PARA 13 "" 1 "" {GLPLOT2D 400 300 300 {PLOTDATA 2 " 6#-%'POINTSG667$$\"\"\"\"\"!$\"&#*)RF)7$$\"\"#F)$\"&Ec%F)7$$\"\"$F)$\" &)*)[F)7$$\"\"%F)$\"&N3&F)7$$\"\"&F)$\"&JK&F)7$$\"\"'F)$\"&BX&F)7$$\" \"(F)$\"&5h&F)7$$\"\")F)$\"&Ot&F)7$$\"\"*F)$\"&4!eF)7$$\"#5F)$\"&P#fF) 7$$\"#6F)$\"&J(fF)7$$\"#7F)$\"&=-'F)7$$\"#8F)$\"&`5'F)7$$\"#9F)$\"&()> 'F)7$$\"#:F)$\"&$GiF)7$$\"#;F)$\"&sG'F)7$$\"#F)$\"&OV'F)7$$\"#?F)$\"&?\\'F)" 1 2 0 1 10 0 2 9 1 4 2 1.000000 45.000000 45.000000 0 0 "Curve 1" }}}}}{SECT 1 {PARA 3 "" 0 " " {TEXT -1 28 "Question 5 (Newton's Method)" }}{PARA 0 "" 0 "" {TEXT -1 448 "Newton's method can be generalized to functions of more than o ne variable. The generalized Newton's method can be used to find the \+ intersection points of curves in 2-space. In this question you explor e the use of Newton's method to find the intersection of a circle and \+ an hyperbola. There are four intersection points and depending on the initial point used, Newton's method may converge to any of the four p oints or it may not converge at all." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "with(linalg): with(plots):" }}{PARA 7 " " 1 "" {TEXT -1 80 "Warning, the protected names norm and trace have b een redefined and unprotected\n" }}{PARA 7 "" 1 "" {TEXT -1 50 "Warnin g, the name changecoords has been redefined\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "x := 'x';" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\" xGF$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "y := 'y';" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"yGF$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "C := x^2 + y^2 - 4;" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#>%\"CG,(*$)%\"xG\"\"#\"\"\"F**$)%\"yGF)F*F*\"\"%!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "H := x*y-1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"HG,&*&%\"xG\"\"\"%\"yGF(F(F(!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "x := 'x';" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"xGF$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "implicitplot (\{H,C\},x=-3..3,y=-3..3);" }}{PARA 13 "" 1 "" {GLPLOT2D 400 300 300 {PLOTDATA 2 "6%-%'CURVESG6[r7$7$$!3#*)************z\"!#<$!3MZLLLLL$o)! #=7$$!3$pmmmmmT\"=F*$!3#>************R)F-7$F.7$$!3bnmmmmmA=F*$!3-3LLLL Lt\")F-7$7$$!3zmmmmm;/>F*$!3+#*************fF-F47$F:7$$!3b*))))))))))) Q>F*$!32)366666h%F-7$7$$!3%ommmmmT'>F*$!33#************f$F-F@7$7$$!31n mmmm;k>F*FI7$$!3iZ!>w/>w)>F*$!3\"e]4Q_4Qs\"F-7$7$$!3kmmmmm;%*>F*$!3=#* ***********>\"F-FO7$7$$!3'ommmmmT*>F*$!3K#************>\"F-7$FV$\"3RKo mmmm;u!#>7$7$FV$\"3s2++++++7F-Fjn7$F_o7$$!3Y#f#f#f#fs>F*$\"39Sf#f#f#f# HF-7$7$$!3immmmm;k>F*$\"3i2++++++OF-Fco7$Fio7$$!3!HLLLLL8$>F*$\"3@YLLL LL8\\F-7$7$$!3Mmmmmm;/>F*$\"3a2++++++gF-F_p7$Fep7$$!3]vvvvvvv=F*$\"3!* oddddddnF-7$7$$!3Emmmmm;9=F*$\"3c3++++++%)F-F[q7$7$Fbq$\"3Y2++++++%)F- 7$$!3(RWWWWW%4=F*$\"3cbWWWWW%\\)F-7$7$$!3;*************z\"F*$\"3W[LLLL L$o)F-Fjq7$7$$!3;************f:F*$!3#zmmmmmmC\"F*7$$!3c>w/>w/z;F*$!3=* ***********z5F*7$F[s7$FarF+7$7$Far$\"3MZLLLLL$o)F-7$$!3Z-.....Bw/z;F*$\"3u++++++!3\"F*Ffs7$F\\t7$$!3\"QWWWWW%H ;F*$\"3QXWWWWW\\6F*7$7$Fgr$\"3qnmmmmmY7F*Fbt7$7$$!3<************>8F*$! 3#)*))))))))))))\\\"F*7$F_uF]u7$7$$!3g*))))))))))))\\\"F*F]uFfr7$Fht7$ $!3&fmmmmmm_\"F*$\"3_nmmmmm'G\"F*7$7$$!3E)))))))))))))\\\"F*$\"3t+++++ +?8F*Fgu7$F]v7$$!3hVWWWWW49F*$\"3w/>w/z;F*F^x7$7$F1F/7$F+F(7$7$F+FarF]w7$Fdx7$ $!30-......5F*$\"3e......BLLLLL$o)F-$\"3q+++++++=F*F]y7$Fc y7$$!3YMWWWWW%\\)F-$\"33XWWWWW4=F*7$7$F1$\"3$pmmmmmT\"=F*Fiy7$Fhx7$F7F 57$7$F=F;Fcz7$7$F1$\"3:nmmmm;9=F*7$$!3oYddddddnF-$\"3=wvvvvvv=F*7$7$F= $\"3,nmmmm;/>F*Fjz7$Fez7$FCFA7$7$FIFGFd[l7$7$F=$\"3zmmmmm;/>F*7$$!37?L LLLL8\\F-$\"3dLLLLLLJ>F*7$7$FI$\"3%ommmmmT'>F*F[\\l7$7$FIFM7$FRFP7$7$F XFVFf\\l7$Fa\\l7$$!3R7f#f#f#f#HF-$\"3!Hf#f#f#fs>F*7$7$FX$\"3'ommmmmT*> F*Fj\\l7$7$FhnFfn7$$\"3+Jommmm;uF]oFfn7$7$F`oFVFe]l7$7$FX$\"3kmmmmm;%* >F*7$$!3$z\\mmmmmT(F]oF\\^l7$7$F`oF\\^lF^^l7$Fi]l7$FfoFdo7$7$F\\pFjoFd ^l7$Fb^l7$$\"3*=a4Q_4Qs\"F-$\"3SZ!>w/>w)>F*7$7$F\\p$\"3Smmmmm;k>F*Fh^l 7$Ff^l7$$\"3lXLLLLL8\\F-F`p7$7$FhpFfpFb_l7$F^_l7$$\"3[K666666YF-$\"3A) )))))))))))Q>F*7$7$Fhp$\"3cmmmmm;/>F*Fh_l7$Ff_l7$F^qF\\q7$7$FdqFbqFb`l 7$F^`l7$$\"3)oNLLLLL<)F-$\"3blmmmmmA=F*7$7$Fhq$\"3[mmmmm;9=F*Ff`l7$7$F hqFbq7$$\"3WaWWWWW%\\)F-F[r7$7$FcrFarFaal7$7$FdsFar7$$\"3$QIIIIII+\"F* $!3D-.....Bw/z;F*7$$\"3o?LLLLL$o)F-Ff y7$7$$\"3!=KLLLLLo)F-$\"3#4++++++!=F*F\\al7$F^bl7$FetFct7$7$FitFgrF]cl 7$F_cl7$FjuFhu7$7$F`vF^vFacl7$7$F`v$\"3/)))))))))))))\\\"F*7$$\"3qlmmm mmY7F*$\"3%4++++++c\"F*7$FhclF`bl7$Fccl7$FfvFdv7$7$FjvF]uF_dl7$Fadl7$F ewFcw7$7$F[xFiwFcdl7$7$F[dlFicl7$FfclF`v7$FhdlFecl7$Fedl7$FaxF_x7$7$Fe xF^sF[el7$F]el7$F`yF^y7$7$FfyFdyF_el7$7$FfyFdbl7$FablF_t7$FdelFgdl7$Fa el7$F\\z$!3OLWWWWW%\\)F-7$7$F`zF1Fgel7$7$FhzF17$$\"3Swvvvvvv=F*F[[l7$7 $Fa[lF=F^fl7$7$Fi[lF=7$F^\\lF\\\\l7$7$Fb\\lFIFefl7$Fgfl7$F]]lF[]l7$7$F a]lFXFifl7$7$F\\^lFX7$F\\^lF_^l7$7$F\\^lF`oF^gl7$F`gl7$F[_lFi^l7$7$F__ lF\\pFbgl7$Fdgl7$$\"3W))))))))))))Q>F*Fi_l7$7$F_`lFhpFfgl7$Fjgl7$$\"3x lmmmmmA=F*Fg`l7$7$F]alFhqF\\hl7$F`hl7$FjblFhbl-%'COLOURG6&%$RGBG\"\"\" \"\"!Fhhl-F$6_o7$7$$!3!)************fFF*$!3W,rz0%)=BOF-7$$!3!Ryxxxxxx# F*$!3_\"************f$F-7$7$FbilFI7$$!\"$Fhhl$!3qLLLLLLLLF-7$F\\il7$$! 3iNq.Pq.dFF*$!34K'H'H'H'HOF-7$7$$!3d************>DF*$!39pRDoRDoRF-F^jl 7$7$Fejl$!3eoRDoRDoRF-7$$!3OlmmmmmrCF*$!3gOLLLLL$3%F-7$7$$!3O********* ***zAF*$!3=.2G7\\'fQ%F-F][m7$Fc[m7$$!37JLLLLLt@F*$!3=rmmmmmmYF-7$7$$!3 :************R?F*$!3]FPJ%yg>!\\F-Fi[m7$F_\\m7$$!3S`bbbbbb=F*$!3`\\WWWW WWaF-7$7$Far$!3-ebbbbbbbF-Fe\\m7$7$Fgr$!389kD5kD5kF-7$$!3uommmmmm;F*F= 7$Fb]mF[]m7$F_]m7$$!3%z566666Z\"F*$!3Q/*)))))))))))oF-7$7$F]u$!3C\"edd dddd(F-Fg]m7$7$F^s$!3'[Ef#f#f#f#*F-7$$!3c\">w/>w/>\"F*F17$Fd^mF]^m7$7$ F1Fe^m7$Fb^mF^s7$Fj^mFa^m7$7$F=Fc]m7$F`]mFgr7$F^_m7$Fj]mFh]m7$7$F^^mF] uF`_m7$Fb_mFi^m7$7$FdilFbil7$F_ilF]il7$Ff_m7$FajlF_jl7$7$FgjlFejlFh_m7 $7$F[[mFejl7$$!3/OLLLLL$3%F-$!3!\\mmmmm;Z#F*7$7$Ff[mFd[mF]`m7$Fc`m7$F \\\\mFj[m7$7$Fb\\mF`\\mFe`m7$Fg`m7$Fh\\mFf\\m7$7$F\\]mFarFi`m7$F[amF]_ m7$7$F[jlFiil7$FIFbil7$7$F\\p$\"3!>xxxxxxx#F*7$$\"3[JLLLLLLLF-$\"3y,++ ++++IF*7$7$Fhp$\"3_kmmmmmm;F*7$$\"3e`bbbbbbbF-Ffy7$7$$\"3[_bbbbbbbF-Ff y7$$\"3UQWWWWWWaF-$\"3Sdbbbbbb=F*7$7$$\"3^APJ%yg>!\\F-$\"3#4++++++/#F* Fdbm7$Fjbm7$$\"3=hmmmmmmYF-$\"3cNLLLLLt@F*7$7$$\"3%)*p!G7\\'fQ%F-$\"39 ,+++++!G#F*F`cm7$7$$\"3G*p!G7\\'fQ%F-Ficm7$$\"3#)GLLLLL$3%F-$\"3Mpmmmm mrCF*7$7$$\"3#e'RDoRDoRF-$\"3N,+++++?DF*F_dm7$7$$\"3OmRDoRDoRF-Fhdm7$$ \"3)[iH'H'H'HOF-$\"31Sq.Pq.dFF*7$7$$\"3A*4(z0%)=BOF-$\"3c,+++++gFF*F^e m7$Fdem7$$\"3=3++++++OF-Fbam7$7$Fhq$\"3M*=w/>w/>\"F*7$$\"3CrvvvvvvvF-F `v7$7$$\"3OsvvvvvvvF-F`v7$$\"3Su))))))))))))oF-$\"3;966666r9F*7$7$$\"3 Z2kD5kD5kF-F[xFhfm7$F^gmFjam7$7$F_t$\"3k_#f#f#f#f#*F-7$FdgmF_t7$7$$\"3 u`#f#f#f#f#*F-F_tF^fm7$7$F`vFbfm7$F_fmFhq7$F]hm7$F_tFigm7$7$F`vFffm7$F [gmFifm7$7$F[xF_gmFbhm7$7$FfyF^bm7$F[bmFhp7$FghmFdhm7$7$FfyFbbm7$$\"3i dbbbbbb=F*$\"3`RWWWWWWaF-7$7$F]cmF[cmF[im7$Faim7$FccmFacm7$7$FicmFgcmF cim7$7$FicmF]dm7$FbdmF`dm7$7$FhdmFfdmFhim7$7$FhdmF\\em7$$\"3iRq.Pq.dFF *F_em7$7$FgemFeemF]jm7$7$FgamFeam7$FbamF\\p7$7$FbamF[fmFajmFchl-%+AXES LABELSG6$%\"xG%\"yG" 1 2 0 1 10 0 2 9 1 4 2 1.000000 45.000000 45.000000 0 0 "Curve 1" "Curve 2" }}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "solve(\{H=0,C=0\});" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#<$/%\"xG,&*$)-%'RootOfG6#,(\"\"\"F-*$)%#_ZG\"\"%F-F-*&F1F-)F0\"\"#F- !\"\"\"\"$F-F5*&F1F-F)F-F-/%\"yGF)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "allvalues(%);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6&<$/% \"xG,(*$),&*$-%%sqrtG6#\"\"'\"\"\"#!\"\"\"\"#*&#F/F2F/*$-F,6#F2F/F/F1 \"\"$F/F1*&F2F/F+F/F1*&F2F/F6F/F1/%\"yGF)<$/F%,(*$),&F*#F/F2*&FCF/F6F/ F/F8F/F1*&F2F/F+F/F/*&F2F/F6F/F//F " 0 "" {MPLTEXT 1 0 9 "evalf(%);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6&<$/%\"xG$!*&3Qw^!\"*/% \"yG$!+`;&=$>F(<$/F%$\"*&3Qw^F(/F*$\"+`;&=$>F(<$/F%F+/F*$!+54Qw^!#5<$/ F%F2/F*$\"+54Qw^F9" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "J := \+ matrix([[diff(C,x),diff(C,y)],[diff(H,x),diff(H,y)]]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"JG-%'matrixG6#7$7$,$%\"xG\"\"#,$%\"yGF,7$F.F+ " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "det(J);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&*$)%\"xG\"\"#\"\"\"F'*&F'F()%\"yGF'F(!\"\"" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "solve(%);" }}{PARA 11 "" 1 " " {XPPMATH 20 "6$<$/%\"xG,$%\"yG!\"\"/F'F'<$F)/F%F'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "Js := inverse(J);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#JsG-%'matrixG6#7$7$,$*&%\"xG\"\"\",&*$)F,\"\"#F-!\" \"*$)%\"yGF1F-F-F2#F2F1*&F5F-F.F27$,$F7#F-F1,$F+F2" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "x0 := 0.0; y0 := -2.0;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x0G$\"\"!F&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#y0 G$!#?!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 160 "for i from 1 to 10 do v := matadd([x0,y0], scalarmul(multiply(subs(\{x=x0,y=y0\},o p(Js)),[subs(\{x=x0,y=y0\},C),subs(\{x=x0,y=y0\},H)]),-1)); x0 := v[1] ; y0 := v[2];" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od;" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%\"vG-%'vectorG6#7$$!+++++]!#5$!#?!\"\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x0G$!+++++]!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#y0G$!#?!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\" vG-%'vectorG6#7$$!+nmmm^!#5$!+LLLL>!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x0G$!+nmmm^!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#y0G$!+LL LL>!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"vG-%'vectorG6#7$$!+Z0Pw ^!#5$!+TF&=$>!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x0G$!+Z0Pw^!#5 " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#y0G$!+TF&=$>!\"*" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%\"vG-%'vectorG6#7$$!+-4Qw^!#5$!+`;&=$>!\"*" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x0G$!+-4Qw^!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#y0G$!+`;&=$>!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# >%\"vG-%'vectorG6#7$$!+.4Qw^!#5$!+`;&=$>!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x0G$!+.4Qw^!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% #y0G$!+`;&=$>!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"vG-%'vectorG6 #7$$!+/4Qw^!#5$!+_;&=$>!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x0G$ !+/4Qw^!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#y0G$!+_;&=$>!\"*" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"vG-%'vectorG6#7$$!+.4Qw^!#5$!+`;&= $>!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x0G$!+.4Qw^!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#y0G$!+`;&=$>!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"vG-%'vectorG6#7$$!+/4Qw^!#5$!+_;&=$>!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x0G$!+/4Qw^!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#y0G$!+_;&=$>!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# >%\"vG-%'vectorG6#7$$!+.4Qw^!#5$!+`;&=$>!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x0G$!+.4Qw^!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% #y0G$!+`;&=$>!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"vG-%'vectorG6 #7$$!+/4Qw^!#5$!+_;&=$>!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x0G$ !+/4Qw^!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#y0G$!+_;&=$>!\"*" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "# Apply Newton's method for \+ C and H using the initial point p." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 76 "# Check to see if the Jacobian is invertible. If not, return 0. \+ Otherwise," }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 77 "# check to see if the method converges to one of the four intersection points" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 76 "# p1, p2, p3, p4. If so, return the appropri ate 1 <= i <= 4, else return 5." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 1 "# " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "N := proc(p)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "local C, H, J, Js, p1,p2,p3,p4, v, x0,y0, i, j;" } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "C := x^2+y^2-4;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "H := x*y-1;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 59 " J := matrix([[diff(C,x),diff(C,y)],[diff(H,x),diff(H,y)]]);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "Js := inverse(J);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "p1 := [0.517638085, 1.931851653];" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 32 "p2 := [1.931851653,0.517638085];" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "p3 := [-0.517638085, -1.931851653];" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 34 "p4 := [-1.931851653,-0.517638085];" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "if det(subs(\{x=p[1],y=p[2]\},eval(J))) = 0 then RETURN(0); fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "v := p; " } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 86 "for i from 1 to 10 do x0 := v[1]; \+ y0 := v[2]; v := matadd([x0,y0]," }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 95 "scalarmul(multiply(subs(\{x=x0,y=y0\},eval(Js)), [subs(\{x=x0,y=y0\},C),subs(\{x=x0,y=y0\},H)]),-1)); " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "if norm (v-p1,2) <= 10^(-8) then RETURN(1); " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "elif norm(v-p2) <= 10^(-8) then RETURN(2);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "elif norm(v-p3) <= 10^(-8) then RETURN(3);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "elif norm(v-p4) <= 10^(-8) then RETURN(4) ;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "else RETURN(5);" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 3 "fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"NGR6#%\"pG6/%\"CG%\"HG%\"JG%#JsG %#p1G%#p2G%#p3G%#p4G%\"vG%#x0G%#y0G%\"iG%\"jG6\"F6C.>8$,(*$)%\"xG\"\"# \"\"\"F?*$)%\"yGF>F?F?\"\"%!\"\">8%,&*&F=F?FBF?F?F?FD>8&-%'matrixG6#7$ 7$-%%diffG6$F9F=-FQ6$F9FB7$-FQ6$FFF=-FQ6$FFFB>8'-%(inverseG6#FJ>8(7$$ \"*&3Qw^!\"*$\"+`;&=$>F^o>8)7$F_oF\\o>8*7$$!*&3Qw^F^o$!+`;&=$>F^o>8+7$ FioFgo@$/-%$detG6#-%%subsG6$<$/F=&9$6#F?/FB&Fip6#F>-%%evalGFhn\"\"!-%' RETURNG6#F`q>8,Fip?(8/F?F?\"#5%%trueGC%>8-&FeqFjp>8.&FeqF]q>Feq-%'mata ddG6$7$F\\rF_r-%*scalarmulG6$-%)multiplyG6$-Fdp6$<$/F=F\\r/FBF_r-F_q6# Fen7$-Fdp6$F^sF9-Fdp6$F^sFFFD@+1-%%normG6$,&FeqF?FjnFDF>#F?\"*++++\"-F bqFjp1-F[t6#,&FeqF?FboFDF^t-FbqF]q1-F[t6#,&FeqF?FeoFDF^t-Fbq6#\"\"$1-F [t6#,&FeqF?F\\pFDF^t-Fbq6#FC-Fbq6#\"\"&F6F6F6" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "N([0.0,-2.0]);" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#\"\"$" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 100 "Determine which points in the grid -3 <= x <= 3, -3 <= y <= 3 con verge to which intersection points." }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "P0 := []; P1 := []; P2 := \+ []; P3 := []; P4 := [];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#P0G7\" " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#P1G7\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#P2G7\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#P3G7\" " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#P4G7\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "for i from -3 by .25 to 3 do" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 28 "for j from -3 by .25 to 3 do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 16 " n := N([i,j]):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 39 " if n = 0 then P0 := [[i,j],op(P0)]:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 39 " elif n = 1 then P1 := [[i,j],op(P1)]:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 39 " elif n = 2 then P2 := [[i,j],op(P2)]:" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 " elif n = 3 then P3 := [[i,j],op(P 3)]:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 39 " elif n = 4 then P4 := [[i ,j],op(P4)]:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 34 " else ERROR(\"does not converge\"):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 " fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "o d:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "P3;" }}{PARA 12 "" 1 " " {XPPMATH 20 "6#7\\t7$$\"$v#!\"#!\"$7$$\"$]#F'$!$v#F'7$F*F(7$$\"$D#F' $!$]#F'7$F0F,7$F0F(7$$\"$+#F'$!$D#F'7$F7F27$F7F,7$F7F(7$$\"$v\"F'$!$+# F'7$F?F97$F?F27$F?F,7$F?F(7$$\"$]\"F'$!$v\"F'7$FHFA7$FHF97$FHF27$FHF,7 $FHF(7$$\"$D\"F'$!$]\"F'7$FRFJ7$FRFA7$FRF97$FRF27$FRF,7$FRF(7$$\"$+\"F '$!$D\"F'7$FgnFT7$FgnFJ7$FgnFA7$FgnF97$FgnF27$FgnF,7$FgnF(7$$\"#vF'$!$ +\"F'7$FcoFin7$FcoFT7$FcoFJ7$FcoFA7$FcoF97$FcoF27$FcoF,7$FcoF(7$$\"#]F '$!#vF'7$F`pFeo7$F`pFin7$F`pFT7$F`pFJ7$F`pFA7$F`pF97$F`pF27$F`pF,7$F`p F(7$$\"#DF'$!#]F'7$F^qFbp7$F^qFeo7$F^qFin7$F^qFT7$F^qFJ7$F^qFA7$F^qF97 $F^qF27$F^qF,7$F^qF(7$$\"\"!F^r$!#DF'7$F]rF`q7$F]rFbp7$F]rFeo7$F]rFin7 $F]rFT7$F]rFJ7$F]rFA7$F]rF97$F]rF27$F]rF,7$F]rF(7$F_rF`q7$F_rFbp7$F_rF eo7$F_rFin7$F_rFT7$F_rFJ7$F_rFA7$F_rF97$F_rF27$F_rF,7$F_rF(7$F`qFbp7$F `qFeo7$F`qFin7$F`qFT7$F`qFJ7$F`qFA7$F`qF97$F`qF27$F`qF,7$F`qF(7$FbpFeo 7$FbpFin7$FbpFT7$FbpFJ7$FbpFA7$FbpF97$FbpF27$FbpF,7$FbpF(7$FeoFin7$Feo FT7$FeoFJ7$FeoFA7$FeoF97$FeoF27$FeoF,7$FeoF(7$FinFT7$FinFJ7$FinFA7$Fin F97$FinF27$FinF,7$FinF(7$FTFJ7$FTFA7$FTF97$FTF27$FTF,7$FTF(7$FJFA7$FJF 97$FJF27$FJF,7$FJF(7$FAF97$FAF27$FAF,7$FAF(7$F9F27$F9F,7$F9F(7$F2F,7$F 2F(7$F,F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "p0 := pointplo t(P0,color=black):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "p1 := pointplot(P1,color=blue):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "p2 := pointplot(P2,color=yellow):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "p3 := pointplot(P3,color=green):" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 30 "p4 := pointplot(P4,color=red):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "display(\{p0,p1,p2,p3,p4\});" }} {PARA 13 "" 1 "" {GLPLOT2D 400 300 300 {PLOTDATA 2 "6'-%'POINTSG6T7$$ \"$+$!\"#F'7$F'$!\"$\"\"!7$$\"$v#F)F/7$F/$!$v#F)7$$\"$]#F)F57$F5$!$]#F )7$$\"$D#F)F;7$F;$!$D#F)7$$\"$+#F)FA7$FA$!$+#F)7$$\"$v\"F)FG7$FG$!$v\" F)7$$\"$]\"F)FM7$FM$!$]\"F)7$$\"$D\"F)FS7$FS$!$D\"F)7$$\"$+\"F)FY7$FY$ !$+\"F)7$$\"#vF)Fin7$Fin$!#vF)7$$\"#]F)F_o7$F_o$!#]F)7$$\"#DF)Feo7$Feo $!#DF)7$$F-F-F[p7$FhoFeo7$FhoFho7$FboF_o7$FboFbo7$F\\oFin7$F\\oF\\o7$F fnFY7$FfnFfn7$FVFS7$FVFV7$FPFM7$FPFP7$FJFG7$FJFJ7$FDFA7$FDFD7$F>F;7$F> F>7$F8F57$F8F87$F2F/7$F2F27$F+F'7$F+F+-%'COLOURG6&%$RGBGF-F-F--F$6]t7$ F/F'7$F5F'7$F5F/7$F;F'7$F;F/7$F;F57$FAF'7$FAF/7$FAF57$FAF;7$FGF'7$FGF/ 7$FGF57$FGF;7$FGFA7$FMF'7$FMF/7$FMF57$FMF;7$FMFA7$FMFG7$FSF'7$FSF/7$FS F57$FSF;7$FSFA7$FSFG7$FSFM7$FYF'7$FYF/7$FYF57$FYF;7$FYFA7$FYFG7$FYFM7$ FYFS7$FinF'7$FinF/7$FinF57$FinF;7$FinFA7$FinFG7$FinFM7$FinFS7$FinFY7$F _oF'7$F_oF/7$F_oF57$F_oF;7$F_oFA7$F_oFG7$F_oFM7$F_oFS7$F_oFY7$F_oFin7$ FeoF'7$FeoF/7$FeoF57$FeoF;7$FeoFA7$FeoFG7$FeoFM7$FeoFS7$FeoFY7$FeoFin7 $FeoF_o7$F[pF'7$F[pF/7$F[pF57$F[pF;7$F[pFA7$F[pFG7$F[pFM7$F[pFS7$F[pFY 7$F[pFin7$F[pF_o7$F[pFeo7$FhoF'7$FhoF/7$FhoF57$FhoF;7$FhoFA7$FhoFG7$Fh oFM7$FhoFS7$FhoFY7$FhoFin7$FhoF_o7$FboF'7$FboF/7$FboF57$FboF;7$FboFA7$ FboFG7$FboFM7$FboFS7$FboFY7$FboFin7$F\\oF'7$F\\oF/7$F\\oF57$F\\oF;7$F \\oFA7$F\\oFG7$F\\oFM7$F\\oFS7$F\\oFY7$FfnF'7$FfnF/7$FfnF57$FfnF;7$Ffn FA7$FfnFG7$FfnFM7$FfnFS7$FVF'7$FVF/7$FVF57$FVF;7$FVFA7$FVFG7$FVFM7$FPF '7$FPF/7$FPF57$FPF;7$FPFA7$FPFG7$FJF'7$FJF/7$FJF57$FJF;7$FJFA7$FDF'7$F DF/7$FDF57$FDF;7$F>F'7$F>F/7$F>F57$F8F'7$F8F/7$F2F'-Feq6&FgqF[pF[p$\"* ++++\"!\")-F$6]t7$F/F+7$F5F27$F5F+7$F;F87$F;F27$F;F+7$FAF>7$FAF87$FAF2 7$FAF+7$FGFD7$FGF>7$FGF87$FGF27$FGF+7$FMFJ7$FMFD7$FMF>7$FMF87$FMF27$FM F+7$FSFP7$FSFJ7$FSFD7$FSF>7$FSF87$FSF27$FSF+7$FYFV7$FYFP7$FYFJ7$FYFD7$ FYF>7$FYF87$FYF27$FYF+7$FinFfn7$FinFV7$FinFP7$FinFJ7$FinFD7$FinF>7$Fin F87$FinF27$FinF+7$F_oF\\o7$F_oFfn7$F_oFV7$F_oFP7$F_oFJ7$F_oFD7$F_oF>7$ F_oF87$F_oF27$F_oF+7$FeoFbo7$FeoF\\o7$FeoFfn7$FeoFV7$FeoFP7$FeoFJ7$Feo FD7$FeoF>7$FeoF87$FeoF27$FeoF+7$F[pFho7$F[pFbo7$F[pF\\o7$F[pFfn7$F[pFV 7$F[pFP7$F[pFJ7$F[pFD7$F[pF>7$F[pF87$F[pF27$F[pF+7$FhoFbo7$FhoF\\o7$Fh oFfn7$FhoFV7$FhoFP7$FhoFJ7$FhoFD7$FhoF>7$FhoF87$FhoF27$FhoF+7$FboF\\o7 $FboFfn7$FboFV7$FboFP7$FboFJ7$FboFD7$FboF>7$FboF87$FboF27$FboF+7$F\\oF fn7$F\\oFV7$F\\oFP7$F\\oFJ7$F\\oFD7$F\\oF>7$F\\oF87$F\\oF27$F\\oF+7$Ff nFV7$FfnFP7$FfnFJ7$FfnFD7$FfnF>7$FfnF87$FfnF27$FfnF+7$FVFP7$FVFJ7$FVFD 7$FVF>7$FVF87$FVF27$FVF+7$FPFJ7$FPFD7$FPF>7$FPF87$FPF27$FPF+7$FJFD7$FJ F>7$FJF87$FJF27$FJF+7$FDF>7$FDF87$FDF27$FDF+7$F>F87$F>F27$F>F+7$F8F27$ F8F+7$F2F+-Feq6&FgqF[pF\\[lF[p-F$6]t7$F'F/7$F'F57$F'F;7$F'FA7$F'FG7$F' FM7$F'FS7$F'FY7$F'Fin7$F'F_o7$F'Feo7$F'F[p7$F'Fho7$F'Fbo7$F'F\\o7$F'Ff n7$F'FV7$F'FP7$F'FJ7$F'FD7$F'F>7$F'F87$F'F27$F/F57$F/F;7$F/FA7$F/FG7$F /FM7$F/FS7$F/FY7$F/Fin7$F/F_o7$F/Feo7$F/F[p7$F/Fho7$F/Fbo7$F/F\\o7$F/F fn7$F/FV7$F/FP7$F/FJ7$F/FD7$F/F>7$F/F87$F5F;7$F5FA7$F5FG7$F5FM7$F5FS7$ F5FY7$F5Fin7$F5F_o7$F5Feo7$F5F[p7$F5Fho7$F5Fbo7$F5F\\o7$F5Ffn7$F5FV7$F 5FP7$F5FJ7$F5FD7$F5F>7$F;FA7$F;FG7$F;FM7$F;FS7$F;FY7$F;Fin7$F;F_o7$F;F eo7$F;F[p7$F;Fho7$F;Fbo7$F;F\\o7$F;Ffn7$F;FV7$F;FP7$F;FJ7$F;FD7$FAFG7$ FAFM7$FAFS7$FAFY7$FAFin7$FAF_o7$FAFeo7$FAF[p7$FAFho7$FAFbo7$FAF\\o7$FA Ffn7$FAFV7$FAFP7$FAFJ7$FGFM7$FGFS7$FGFY7$FGFin7$FGF_o7$FGFeo7$FGF[p7$F GFho7$FGFbo7$FGF\\o7$FGFfn7$FGFV7$FGFP7$FMFS7$FMFY7$FMFin7$FMF_o7$FMFe o7$FMF[p7$FMFho7$FMFbo7$FMF\\o7$FMFfn7$FMFV7$FSFY7$FSFin7$FSF_o7$FSFeo 7$FSF[p7$FSFho7$FSFbo7$FSF\\o7$FSFfn7$FYFin7$FYF_o7$FYFeo7$FYF[p7$FYFh o7$FYFbo7$FYF\\o7$FinF_o7$FinFeo7$FinF[p7$FinFho7$FinFbo7$F_oFeo7$F_oF [p7$F_oFho7$FeoF[p-Feq6&FgqF\\[lF\\[lF[p-F$6]t7$FhoF[p7$FboFeo7$FboF[p 7$FboFho7$F\\oF_o7$F\\oFeo7$F\\oF[p7$F\\oFho7$F\\oFbo7$FfnFin7$FfnF_o7 $FfnFeo7$FfnF[p7$FfnFho7$FfnFbo7$FfnF\\o7$FVFY7$FVFin7$FVF_o7$FVFeo7$F VF[p7$FVFho7$FVFbo7$FVF\\o7$FVFfn7$FPFS7$FPFY7$FPFin7$FPF_o7$FPFeo7$FP F[p7$FPFho7$FPFbo7$FPF\\o7$FPFfn7$FPFV7$FJFM7$FJFS7$FJFY7$FJFin7$FJF_o 7$FJFeo7$FJF[p7$FJFho7$FJFbo7$FJF\\o7$FJFfn7$FJFV7$FJFP7$FDFG7$FDFM7$F DFS7$FDFY7$FDFin7$FDF_o7$FDFeo7$FDF[p7$FDFho7$FDFbo7$FDF\\o7$FDFfn7$FD FV7$FDFP7$FDFJ7$F>FA7$F>FG7$F>FM7$F>FS7$F>FY7$F>Fin7$F>F_o7$F>Feo7$F>F [p7$F>Fho7$F>Fbo7$F>F\\o7$F>Ffn7$F>FV7$F>FP7$F>FJ7$F>FD7$F8F;7$F8FA7$F 8FG7$F8FM7$F8FS7$F8FY7$F8Fin7$F8F_o7$F8Feo7$F8F[p7$F8Fho7$F8Fbo7$F8F\\ o7$F8Ffn7$F8FV7$F8FP7$F8FJ7$F8FD7$F8F>7$F2F57$F2F;7$F2FA7$F2FG7$F2FM7$ F2FS7$F2FY7$F2Fin7$F2F_o7$F2Feo7$F2F[p7$F2Fho7$F2Fbo7$F2F\\o7$F2Ffn7$F 2FV7$F2FP7$F2FJ7$F2FD7$F2F>7$F2F87$F+F/7$F+F57$F+F;7$F+FA7$F+FG7$F+FM7 $F+FS7$F+FY7$F+Fin7$F+F_o7$F+Feo7$F+F[p7$F+Fho7$F+Fbo7$F+F\\o7$F+Ffn7$ F+FV7$F+FP7$F+FJ7$F+FD7$F+F>7$F+F87$F+F2-Feq6&FgqF\\[lF[pF[p" 1 2 0 1 10 0 2 9 1 4 2 1.000000 45.000000 45.000000 0 0 "Curve 1" "Curve 2" "C urve 3" "Curve 4" "Curve 5" }}}}{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 an integral polynomial that has \+ " }{XPPEDIT 18 0 "sqrt(3) + sqrt(5)" "6#,&-%%sqrtG6#\"\"$\"\"\"-F%6#\" \"&F(" }{TEXT -1 11 " as a root." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 32 "Generalize the observation that " } {XPPEDIT 18 0 "x^2 - 3 = (x-sqrt(3))*(x+sqrt(3))" "6#/,&*$%\"xG\"\"#\" \"\"\"\"$!\"\"*&,&F&F(-%%sqrtG6#F)F*F(,&F&F(-F.6#F)F(F(" }{TEXT -1 1 " ." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "(x - (sqrt(3) + sqrt(5) )) * (x - (sqrt(3) - sqrt(5))) *" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "(x - (-sqrt(3) + sqrt(5))) * (x - (-sqrt(3) - sqrt(5)));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#**,(%\"xG\"\"\"*$-%%sqrtG6#\"\"$F&!\"\"*$-F)6# \"\"&F&F,F&,(F%F&F'F,F-F&F&,(F%F&F'F&F-F,F&,(F%F&F'F&F-F&F&" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "expand(%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,(*$)%\"xG\"\"%\"\"\"F(*&\"#;F()F&\"\"#F(!\"\"F'F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "solve(%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&,&*$-%%sqrtG6#\"\"&\"\"\"!\"\"*$-F&6#\"\"$F)F*,&F$ F)F+F),&F$F*F+F),&F$F)F+F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{MARK "17" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 } {PAGENUMBERS 0 1 2 33 1 1 }