A document from MCS 275 Spring 2021, instructor Emily Dumas. You can also get the notebook file.

Quiz 6

MCS 275 Spring 2021 - Emily Dumas

Instructions:

Deadline

This quiz must be submitted in Gradescope by 12:00pm CST on Tuesday, Februrary 23, 2021.

Topic

This quiz is about recursion.

Resources you are allowed to consult

Quizzes are INDIVIDUAL, closed book, and only allow access to specified resources. For this quiz you can access:

Point distribution

This quiz has 2 problems (numbered 2 and 3), each worth 4 points. Therefore, the final grading breakdown is:

Points Item
3 autograder
4 problem 2
4 problem 3
11 total

(No problem number 1, as usual)

The 3 points assigned by the autograder based on syntax and docstring checking will be listed as problem 1 in Gradescope.

Problem 2 deleted

Everyone gets 4 points for this problem, because the original problem given here was both more difficult than I intended, and less instructive. I apologize for this mistake.

Problem 3: abbc sequence

Define a sequence $Q$ of integers as follows: The first three values are

  • $Q_0 = 0$
  • $Q_1 = 1$
  • $Q_2 = 2$

All subsequent terms are calculated by the following rule:

  • $Q_n = Q_{n-1} + 2 Q_{n-2} + Q_{n-3}$

In other words, if the last three terms of the sequence you've computed are a, b, and c, then the next term is a+b+b+c.

The sequence therefore begins:

0, 1, 2, 4, 9, 19, 41, 88, 189, 406, 872, 1873, 4023, 8641, 18560, 39865

Write a recursive function called abbc(n) that takes a nonnegative integer n and returns the value of $Q_n$. Save it in a file called quiz6prob3.py and include this file in your quiz submission.

Revision history

  • 2021-02-23 Delete problem 2 after realizing pentafactorial(n) is not equal to n*pentafactorial(n-5) if you use the definition given
  • 2021-02-21 3:00pm CST - Corrected two typos in factor lists
  • 2021-02-21 12:00pm CST - Initial publication