#OK to post homework
#Soham Palande, 9/8/2020, Assignment 1



#Part 1 - Maple Random Lines
5+6;
11
diff(x^2 + x^3*y^5 + x*y^2*z^2, x);
3*x^2*y^5+y^2*z^2+2*x
factor (x^2 + x^3*y^5 + x*y^2*z^2);
x*(x^2*y^5+y^2*z^2+x)

while not S[finished] do
      S[nextvalue]() 
      end do
{}
{1}
{2}
{3}
{4}
{1, 2}
{1, 3}
{1, 4}
{2, 3}
{2, 4}
{3, 4}
{1, 2, 3}
{1, 2, 4}
{1, 3, 4}
{2, 3, 4}
{1, 2, 3, 4}



#Part 2- Human Problem
#F(n) is the set of lists using {1,2} that add-up to n. 
#Write down F(6)
#F(6);
#{[2, 2, 2], [1, 1, 2, 2], [1, 2, 1, 2], [1, 2, 2, 1], [2, 1, 1, 2], [2, 1, 2, 1], [2, 2, 1, 1], [1, 1, 1, 1, 2], [1, 1, # 1, 2, 1], [1, 1, 2, 1, 1], [1, 2, 1, 1, 1], [2, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]}







#Part 3- Understanding Maple Code

L1:= [Mercury, Venus, Earth];
L1 := [Mercury, Venus, Earth]
L2:=[op(L1), Mars];
L2 := [Mercury, Venus, Earth, Mars]



# We initialize Walks(m,n) to be the empty set when either m or n or both are negative because 
# we define the set of steps taken from the origin (0,0) to (m.n) to be elements from the set {E,N} where
# E and N denote a unit step in the positive direction of each coordinate. Thus it is impossible to go 
# from (0,0) to (m.n) when either m or n or both are negative. Hence we define this as the empty set {}.


# We initialize Walks(m,n) to the the singleton set comprising the empty walk [] when n=0 and m =0 because there is only  # one way to go from the origin to the origin and that is the empty walk [], which is still a walk. Thus we return the 
# set comprising the empty walk




#Part 4 -Maple Procedure
#F(n): inputs a non-negative integer n
#and outputs the set of lists using {1,2} that add up to n
F:=proc(n) local X,Y,x,y:
option remember:

if n<0 then
 RETURN({}):
fi:


if n=0 then
 #every set has the empty set as a subset
 RETURN({[]}):
fi:

X:=F(n-1):
Y:=F(n-2):

{seq([op(x),1],x in X),seq([op(y),2],y in Y)}:

end:

F(6);
{[2, 2, 2], [1, 1, 2, 2], [1, 2, 1, 2], [1, 2, 2, 1], [2, 1, 1, 2], [2, 1, 2, 1], [2, 2, 1, 1], [1, 1, 1, 1, 2], [1, 1, 1, 2, 1], [1, 1, 2, 1, 1], [1, 2, 1, 1, 1], [2, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]}
#This output matches the one I computed above by hand.




#Part 5- Maple Procedure

#Checking that F(n)=NuF(n) for n=1...10

evalb(seq(nops(F(n)),n=0..10)=seq(NuF(n),n=0..10));
true


#Compute NuF(1000)
NuF(1000);
70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501


#Maple would complain if we tried to do nops(F(1000)) because the function F(n) is an exponential time 
#recursive algorithm and so it would take a long time to compute the answer.