Questions

1.  This problem concerns the Padovan sequence. The first few elements of the sequence are 1 1 1 2 2 3 4 5 7 9 12 16 21, . . . . The sequence is defined as

PAD(n + 1) = PAD(n − 1) + PAD(n − 2)

with

PAD(0) = PAD(1) = PAD(2) = 1.

Write a single Python function, called PAD, that takes a single integer argument N, and returns the Nth Padovan number. For example PAD(5) returns 3, PAD(3) returns 2, and PAD(4) returns 2.

Test your program on at least the first 10 Padovan numbers. Also test your program for larger values of N. What happens? Explain why in your hw1.txt file.

2. Write a single Python function, called SUMS, that takes a single numeric argument N, and returns the number of additions required by your PAD function to compute the Nth Padovan number. SUMS should not call PAD, but rather you should design the recursion for SUMS by examining your PAD code.

Test your program on at least the first 10 values. What is the relationship between the values returned by PAD and SUMS? Explain why in you hw1.txt file.

3.  A tree can be represented in tuples in Python as follows:

(a)  if the tree contains a single leaf node L, it can be represented by an non-tuple object L

(b)  if the tree has more than one node and is rooted at N, then it can be represented by a tuple

(S1,  S2,  . . .  Sk) where Si represents the ith subtree of N .

Consider for example the following five trees.

Their representations in tuples are respectively

((("l",  "e"),  "f"),  "t"),

(5,  "foo",  3 .1,  -0 .2),

(1,  ("foo",  3 .1),  -0 .2),

(((1,  2),  ("foo",  3 .1)),  ("bar",  -0 .2))

("r",  ("i",  ("g",  ("h",  "t")))) .

Write a single Python function, called ANON. It takes a single argument TREE that represents a tree, and returns an anonymized tree with the same structure, but where all symbols and numbers in the tree are replaced by a question mark. The anonymized versions of the trees above are as follows.

?

? ?

?     ?     ?     ?

?     ?

?     ?

?     ?     ?     ?

?

?

?

?

Test your program on at least these inputs:

>>>  ANON(42)

?

>>>  ANON("FOO")

?

>>>  ANON(((("L",  "E"),  "F"),  "T"))

(((’?’,  ’?’),  ’?’),  ’?’)

>>>  ANON((5,  "FOO",  3 .1,  -0 .2))

(’?’,  ’?’,  ’?’,  ’?’)

>>>  ANON((1,  ("FOO",  3 .1),  -0 .2))

(’?’,  (’?’,  ’?’),  ’?’)

>>>  ANON((((1,  2),  ("FOO",  3 .1)),  ("BAR",  -0 .2)))

(((’?’,  ’?’),  (’?’,  ’?’)),  (’?’,  ’?’))

>>>  ANON(("R",  ("I",  ("G",  ("H",  "T")))))

(’?’,  (’?’,  (’?’,  (’?’,  ’?’))))

Hint : use type(X)  is  tuple to check if the input X is a tuple or not