#Tim Naumovitz
#hw17.txt
#I give permission to post this

########################Problem 1###################

#I don't think the problem lies in the representation
#as a set of edges, but in the fact that under option 2
#we give the verifier the entire graph instead of just
#the subgraph induced by the hamiltonian cycle.  As such
#I believe that options is right, but one step should
#be changed when we pick option 2.

#tomas[1] intersect tomas[3] will just be tomas[3],
#but the point is that we fix tomas[1] before flipping
#the coin, only opening the tomas[3] boxes in option 2.
OneStep:=proc(G,pi) local n,coin,sig,tomas,boxes,e:
n:=nops(pi):
sig:=randperm(n):
tomas:=Options(G,pi,sig):

boxes:={tomas[3][n],tomas[3][1]}:

coin:=rand(1..2)():

for e from 1 to n-1 do
 boxes:=boxes union {{tomas[3][e],tomas[3][e+1]}}:
od:

if coin=1 then
 RETURN(1,[op(1..2,tomas)]):
else
 RETURN(2,[tomas[1] intersect boxes,tomas[3]]):
fi:
end:

############################Problem 2################

VerifyManySteps:=proc(G,i,MrNakamura,NumberOfSteps) local j:

for j from 1 to NumberOfSteps do
if VerifyOneStep(G,i,MrNakamura)=false then
 RETURN(false):
fi:
od:

true:

end:

####################Problem 4########################

#> B := blackscholes(50.00, 49.00, 0.7e-1, 199/365, sqrt(0.9e-1));

#> evalf(B);

#                          5.849179520

#> evalf(C(50, 0, 0.7e-1, sqrt(0.9e-1), 49, 199/365));

#                          5.849179522

#> B := blackscholes(50.00, 60.00, 0.7e-1, 30*(1/365), sqrt(0.9e-1));

#> evalf(B);

#                           0.03454339

#> evalf(C(50, 0, 0.7e-1, sqrt(0.9e-1), 60, 30*(1/365)));

#			    0.03454338

#These (unsurprisingly) seem to give very similar values.

##################Old Stuff##########################

#March 28, 12:00noon-1:20pm 2013 Zero-Knowledge proofs

Help:=proc(): print(`RandHG(n,p) , OneStep(G,pi) `):
print(`VerifyOneStep(G,i,MrNakamura) `):

end:

with(combinat):

#RandHG(n,p), inputs a pos. integer n and a rational number
#p and outputs a graph on n vertices that has a Hamiltionian
#cycle, and the remaining edges are chosen independently
#with prob. p
RandHG:=proc(n,p) local pi,G, roullete,i,j, justin:
pi:=randperm(n):

roullete:=rand(1..denom(p)):
G:={seq({pi[i],pi[i+1]},i=1..n-1), {pi[n],pi[1]}}:

for i from 1 to n do
 for j from i+1 to n do
   justin:=roullete():
     if justin<=numer(p) then
        G:=G union { {i,j}}:
     fi:
  od:
od:

G,pi:
end:


#Options(G,pi,sig): Given a Hamil. graph G
#and a proof of its Ham. pi (n=nops(pi)) and
#a permutation sig, prepare both options
#either show your enemy the image of the graph
#under sig, OR, show the Hamiltonian cycle
Options:=proc(G,pi,sig) local G1,pi1,i,n,H:
n:=nops(pi):
G1:=subs({seq(i=sig[i],i=1..n)},G):
H:=subs({seq(i=sig[i],i=1..n)},pi):
[G1,sig,H]:
end:



OneStepWrong:=proc(G,pi) local n,coin,sig,tomas:
n:=nops(pi):
sig:=randperm(n):
tomas:=Options(G,pi,sig):

coin:=rand(1..2)():

if coin=1 then
 RETURN(1,[op(1..2,tomas)]):
else
 RETURN(2,[tomas[1],tomas[3]]):
fi:
end:



VerifyOneStep:=proc(G,i,MrNakamura)  local G1,sig,G1a,H,t,n:
n:=nops(MrNakamura[2]):
if i=1 then
 G1:=MrNakamura[1]:
 sig:=MrNakamura[2]:
 G1a:=subs({seq(i=sig[i],i=1..n)},G):

  RETURN(evalb(G1=G1a)):
else
 G1:=MrNakamura[1]:
 H:=MrNakamura[2]:
 n:=nops(H):
evalb({seq({H[t],H[t+1]},t=1..n-1),{H[n],H[1]}} minus G1 ={}):
fi:

end: