#OK to post homework #TianHao Zhang(RUID:193008459),02/02/19 ############################Help########################################### Help := proc():print(`MomsAM(f,t,K) ScaledMomsAM(f,t,K) PQs(n,t)` ):end: ########################################################################### #################################Part1##################################### ########################################################################### #Integration #int(f,x=a..b)//int(f,x) #>int(sin(x), x); # -cos(x) #>int(sin(x), x = 1 .. 2); # cos(1) - cos(2) #Int(f,x=a..b)//Int(f,x) #which is unevaluated #Techniques of integration #Load with command with(student) #Do substitution: 'changevar(f(u)=h(u),integral,u)' #>with(student); #>G := Int(x^4/sqrt(-x^10+1), x); #>G2 := changevar(u = x^4, G, u); #>value(G2); # arcsin(u^(5/4))/5 #>subs(u = x^4, %); # arcsin((x^4)^(5/4))/5 #Integration by parts: 'intparts(integral, x)' #>Int(x*cos(x), x); #>intparts(%, x); #Partial fraction 'ratfunc' #>rat := (4*x^7+6*x^5+3*x+2)/(3*x^4*(x+1)*(x+4)); #>convert(rat, parfrac, x); # 4x/3-20/3-11/9/(x+1)+1/6/x^4+35845/1152/(x+4)-3/32/x^2+41/384x+1/24x^3 #Taylor and series expansions #>y := 1/(x-1); #>taylor(y, x = 1.5): #Solving differential equation #>f := f; #>y := f(x); #>dy := diff(y, x); #>ddy := diff(%, x); #>dsolve(ddy+5*dy+6*y = sin(x)*exp(-3*x), y); # f(x) = exp(-3*x)*C2 + exp(-2*x)*C1 - (sin(x)-cos(x))*e^(-3x)/2 #Asymptotic expansions #>z:='z': asympt(Psi(z),z,3); # ln(z)-1/(2*z)-1/(12*z^2)+O(1/z^4) #Graphics #>plot(f(x),x=a..b) #Parametric plot: #>plot([f(t),g(t),t=a..b]) #Multiple plots #>plot([sqrt(x),3*log(x)],x=0..400); #To get a more accurate function: #>plot([sqrt(x),3*log(x)],x=0..400,numpoints=1000) #Polar plots: plot polar curve r=f(c) #>with(plots): #>polarplot(cos(5*t),t=0..2*Pi); #Plot points: #>L:=[[0,0],[1,1],[2,3]]: #>plot(L); #To plot nothing but point: #>plot(L, style = point) #3d-dimensional plotting #>plot3d(exp(-(x^2 + y^2 -1)^2), x=-2..2,y=-2..2); #Multiply plots: #>plot3d({exp(-x^2-y^2),x+y+1},x=-2..2,y=-1..1); #Space curve #withcurve(plots): #>spacecurve([f(t),g(t),h(t)],t=a..b,numpoints=200); #Contour plots #>with(plots): #>contourplot(exp(-(x^2+y^2-1)^2),x=-(1.3)..(1.3),y=-(1.3)..(1.3),filled=true,coloring=[blie,red]); #>contourplot3d... #Linear Algebra #>with(linalg): #>v:=vector([1,2,3,4]); # v:=[1,2,3,4] #>A:=matrix(2,3,[a,b,c,d,e,f]): #>print(A): #Enter matrix #>with(linalg): #>B:=matrix(2,2): #>entermatrix(B); #Use function f(x,y) to create matrix: #>f:=(i,j)->x^(i+j); #>A:=matrix(5,5,f); #Elementary row operations #>with(linalg): #'addrow(A,i,j,c)':c*Ri+Rj #'swaprow(A,i,j)' #'mulrow(A,i,c)' #Gaussian elimination #>with(linalg): #>gausselim(A); #>gaussjord(A); #Inverses and determinants #>det(A); #>inverse(A); ########################################################################### #################################Part3##################################### ########################################################################### #MomsAM(f,t,K): inputs a prob. gen. function and outputs the first K moments about the mean MomsAM:=proc(f,t,K) local L,i,F,ave: if subs(t=1,f)<>1 then printf(`Not prob. dist.`): return(FAIL): fi: F:=f: L:=[]: F:=t*diff(F,t): ave:=subs(t=1,F); F:=f/t^ave: for i from 1 to K do F:=t*diff(F,t): L:=[op(L),subs(t=1,F)]: od: [ave,op(2..nops(L),L)]: end: #ScaledMomsAM(f,t,K): inputs a prob. gen. function and outputs the first K scaled moments about the mean ScaledMomsAM:=proc(f,t,K) local F,L,LM,i,m2: if subs(t=1,f)<>1 then printf(`Not prob. dist.`): return(FAIL): fi: F:=f: L:=[]: LM:=MomsAM(f,t,K): m2:=LM[2]: for i from 3 to K do L:=[op(L),LM[i]/m2^(i/2)]: od: [LM[1],m2,op(L)]: end: ########################################################################### #################################Part4##################################### ########################################################################### #First I have calculated some values: #>subs(n = 1, S); # [1 1 ] # [-, -, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1] # [2 4 ] #>subs(n = 2, S); # [ 1 ] # [1, -, 0, 2, 0, 4, 0, 8, 0, 16, 0, 32, 0, 64] # [ 2 ] #>subs(n = 3, S); # [3 3 7 61 547 4921 44287 398581] # [-, -, 0, -, 0, --, 0, ---, 0, ----, 0, -----, 0, ------] # [2 4 3 9 27 81 243 729 ] #>ScaledMomsAM(((t+1)*(1/2))^n, t, 14); #[ /3 2 1 \ / 15 2 1 15 3\ #[ 16 |-- n - - n| 64 |- -- n + - n + -- n | #[1 1 \16 8 / \ 32 4 64 / #[- n, - n, 0, ----------------, 0, --------------------------, 0, #[2 4 2 3 #[ n n # # /147 2 17 105 3 105 4\ # 256 |--- n - -- n - --- n + --- n | # \64 16 64 256 / # -------------------------------------, 0, # 4 # n # # /31 1185 2 945 5 1575 4 4095 3\ # 1024 |-- n - ---- n + ---- n - ---- n + ---- n | # \4 64 1024 256 256 / 1 / # ---------------------------------------------------, 0, -- |4096 # 5 6 \ # n n # # / 691 28479 2 10395 6 51975 5 107415 4 # |- --- n + ----- n + ----- n - ----- n + ------ n # \ 8 128 4096 2048 1024 # # 111705 3\\ 1 / /5461 238875 2 945945 6 # - ------ n ||, 0, -- |16384 |---- n - ------ n - ------ n # 512 // 7 \ \ 4 64 8192 # n # # ] # ] # 135135 7 2837835 5 4579575 4 2057055 3\\] # + ------ n + ------- n - ------- n + ------- n ||] # 16384 4096 2048 512 //] # ] #With the representation of each element, we can easily calculate the limit, which is(from 3rd to 14th): # [0,3,0,15,0,105,0,945,0,10395,0,135135] ########################################################################### #################################Part5##################################### ########################################################################### #PQs(n,t):the prob. generating function of the running time of Quicksort PQs:=proc(n,t) local k: option remember: if n=0 or n=1 then RETURN(1): else: RETURN(expand(t^(n-1)*add(1/n*PQs(k-1,t)*PQs(n-k,t),k=1..n))): fi: end: #Here are the answers corresponding to each 'n': #n=10: #3rd: 1.050731309 #4th: 4.078984255 #n=20: #3rd: 1.070790342 #4th: 4.478253102 #n=30 #3rd: 1.046086443 #4th: 4.500448684 #n=40 #3rd: 1.024580901 #4th: 4.482789451 #n=50 #3rd: 1.007591274 #4th: 4.460496096 #n=60 #3rd: .9940500268 #4th: 4.439700480 #n=70 #3rd: .9830305181 #4th: 4.421410263 #n=80 #3rd: .9738804886 #4th: 4.405517724 #n=90 #3rd: .9661484404 #4th: 4.391689671 #n=100 #3rd: .9595165948 #4th: 4.379588738 #n=110 #3rd: .9537560146 #4th: 4.368924823 #n=120 #3rd: .9486978885 #4th: 4.359460270 #n=130 #3rd: .9442150423 #4th: 4.351003149 #n=140 #3rd: .9402098117 #4th: 4.343398645 #n=150 #3rd: .9366058987 #4th: 4.336521345 #n=160 #3rd: .9333427857 #4th: 4.330268967 #n=170 #3rd: .9303718158 #4th: 4.324557461 #In this estimation, I find these data are monotone decreasing without an obvious limitation. #Observing the difference between two adjacent Numbers, I find these difference is decreasing as while. And #probably have some regular in my opinion but not confident about it. #Based on these "Guess", I also input all the data above and get an approximate curve. I speculate the limit are: #3rd: at around 0.91 #4th: at around 4.2