# Please do not post homework
# Hari Amoor, 09/13/2020, Assignment 1

1. Print out some random lines.

The output of `diff(x^3, x)` is "3x^2".

2. Write down F(6) for F defined as given.

We compute that F(6) is as follows:

[[1, 2, 1, 2], [1, 2, 2, 1], [1, 1, 2, 1, 1], [2, 2, 1, 1], [2, 2, 2], [2, 1, 1, 2], [2, 1, 2, 1], [2, 1, 1, 1, 1], [1, 1, 2, 2], [1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1], [1, 2, 1, 1, 1], [1, 1, 1, 2, 1]]

3. Go over the Maple code [given in lecture] and try to understand it.

- What Maple line converts L1 := [Mercury, Venus, Earth] to L2 := [Mercury, Venus, Earth, Mars]?

Assuming that L1 is already defined in the given instance of the Maple runtime, the following code would define L2 as specified:

L2 := [op(L1), Mars]

- Explain, in plain English, why we initialize WALKS(m, n) with m < 0 or n < 0 to be the empty set.

Intuitively, a 2D Manhattan lattice with dimensions m and n for m < 0 or n < 0 does not exist. Therefore, it would be mathematically correct for the program to output the empty set for such arguments; there cannot be any paths in the lattice if there is no lattice, so the set of paths in the lattice must be empty.

- Explain, in plain English, why we initialize WALKS(0, 0) to include the singleton set {[]}.

Intuitively, in the 2D Manhattan lattice with dimensions m = n = 0, there is a unique path from the [0, 0] to [m, n] -- the empty path, i.e. the sequence of edges in the lattice that is empty. Therefore, it would be correct for the program to output the singleton set described.

4. Write a Maple procedure, F(n), that inputs a non-negative integer n and outputs the set of lists in {1, 2} that add up to n. Compare the output of F(6) in (2) with the output of your program.

The code is as follows:

# F produces the behavior described above, returning the
# singleton set containing the empty list when argued with
# n = 0 and returning the empty set when argued with n < 0.

# The function is written naively, i.e. with two recursive
# substates, so in order to compute values in linear time-
# complexity, we use the remember option to memoize
# function calls.
F := proc(n) local L1, L2, l1, l2:
option remember:

if n < 0 then
  RETURN({}):
elif n = 0 then
  RETURN({[]}):
elif n = 1 then
  RETURN({[1]}):
fi:

L1 := F(n-1):
L2 := F(n-2):

{seq([op(l1), 1], l1 in L1), seq([1, op(l1)], l1 in L1), seq([op(l2), 2], l2 in L2), seq([2, op(l2)], l2 in L2)}:

end:

The output of this program, when argued with n = 6, matches the result
I supplied in (2).

5. Write a Maple procedure, NuF(n), that inputs a non-negative integer n and outputs the NUMBERS of lists in {1,2} that add-up to n. What is NuF(1000)? Why would Maple complain if you tried to do nops(F(1000))?

The Maple procedure NuF is as follows:

# In the following implementation of NuF, we consider NuF(n)
# for n <= 0 to equal 0.
NuF := proc(n) local P1, P2:
option remember:

if n <= 2 then
  RETURN(max(n, 0)):
fi:

P1 := NuF(n-1)
P2 := NuF(n-2)

P1 + P2:
end:

Observe that we cannot compute this the naive way, i.e. by using nops(F(n)), because for arbitrarily large n, that would lead to unsatisfactory time and space constraints. Case in point, running nops(F(1000)), as desired, would lead to over 2GB of memory consumed and still not complete even after several minutes.

Thus, it is better in this case to use numeric data types, i.e. integers, as opposed to sets and lists to compute NuF results, especially for large n.