{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# MCS 275 Spring 2022 Worksheet 6\n",
"\n",
"* Course instructor: David Dumas"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Topics\n",
"\n",
"The main topics of this worksheet is **recursion**.\n",
"\n",
"The other worksheet from this course that focuses on recursion is [here](https://www.dumas.io/teaching/2022/spring/mcs275/nbview/worksheets/worksheet6.html).\n",
"\n",
"## Resources\n",
"\n",
"These things might be helpful while working on the problems. Remember that for worksheets, we don't strictly limit what resources you can consult, so these are only suggestions.\n",
"\n",
"* [Lecture 12 - Recursion](https://www.dumas.io/teaching/2022/spring/mcs275/slides/lecture12.html)\n",
"* [Lecture 13 - Recursion vs iteration](https://www.dumas.io/teaching/2022/spring/mcs275/slides/lecture13.html)\n",
"* [Lecture 14 - Recursion vs iteration and backtracking](https://www.dumas.io/teaching/2022/spring/mcs275/slides/lecture14.html)\n",
"* [MCS 275 Python Tour](https://www.dumas.io/teaching/2022/spring/mcs275/nbview/samplecode/python_tour.html)\n",
"* [Downey's book](https://greenteapress.com/thinkpython2/html/)\n",
"* MCS 260 course materials from Fall 2021:\n",
" * [Slides, homework, worksheets, and projects](https://www.dumas.io/teaching/2021/fall/mcs260/)\n",
" * [Sample programs](https://github.com/daviddumas/mcs260fall2021/tree/main/samplecode)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 1. Order three Fibonacci\n",
"\n",
"There is a sequence of integers $T_n$ defined by the conditions\n",
"\n",
"$$\\begin{split}\n",
"T_0 &= 0\\\\\n",
"T_1 &= 1\\\\\n",
"T_2 &= 2\\\\\n",
"T_{n} &= T_{n-1} + T_{n-2} + T_{n-3} \\text{ if } n \\geq 3\\end{split}$$\n",
"\n",
"This sequence begins $0, 1, 2, 3, 6, 11, 20, 37, 68, 125, 230, 423, 778, 1431, 2632, \\ldots$.\n",
"\n",
"Write a recursive function that calculates $T_n$.\n",
"\n",
"Then, determine the rule that describes the sequence whose $n^{\\text{th}}$ term is the number of function calls that occur in calculating $T_n$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 2. Prime factorization\n",
"\n",
"An integer greater than 1 is called **prime** if its only divisors are 1 and itself.\n",
"\n",
"The Fundamental Theorem of Algebra states that every positive integer other than 1 is a product of primes, and that the description as a product of primes is unique up to reordering the factors. For example, $275$ can be expressed as $5\\times5\\times11$.\n",
"\n",
"Write a recursive function `factor(n)` that takes an integer `n` greater than 1 and returns a list of primes whose product is equal to `n`. That is, `factor(n)` returns the *prime factorization* of `n`.\n",
"\n",
"I recommend the following strategy: Try to find a way to express `n` as a product of two other integers greater than 1. If you fail, you know that `n` is prime. If you succeed, you the have `n = k * m` and so it would be enough to know the prime factorization of `k` and of `m`.\n",
"\n",
"Hint: One way to check whether `k` divides `n`, is to check whether the remainder `n%k` is zero.\n",
"\n",
"*Acknowledgement: This problem is based in part on a problem on a 2021 MCS 275 worksheet by Jennifer Vaccaro.*\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 3. Parentheses\n",
"\n",
"There are lots of ways to put parentheses in the algebraic expression `a+b+c+d` so that every application of `+` becomes a binary operation. For example:\n",
"* `((a+b)+(c+d))`\n",
"* `(a+(b+(c+d)))`\n",
"* and more\n",
"\n",
"Write a Python function that takes a list of variables or numbers to be summed, and returns all possible ways of parenthesizing the sum fully.\n",
"\n",
"This requires a choice of how to represent the input sum and output parenthesized sums. Instead of using strings, make your function so it expects a list of summands as input and returns a list of possible parenthesized versions that use nested Python lists to represent the parentheses."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[[2, [1, [5, 8]]],\n",
" [2, [[1, 5], 8]],\n",
" [[2, 1], [5, 8]],\n",
" [[2, [1, 5]], 8],\n",
" [[[2, 1], 5], 8]]"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"put_parens([2,1,5,8]) # find all ways to put parentheses in the expression 2+1+5+8"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The return value is a list of length 5, which means there are five ways, described by the nested list structure of one of the items in the return value. These represent:\n",
"```\n",
"(2+(1+(5+8)))\n",
"(2+((1+5)+8))\n",
"(2+1)+(5+8)\n",
"((2+(1+5))+8)\n",
"(((2+1)+5)+8)\n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 4. Rote memoization \n",
"\n",
"Make versions of the recursive functions from problems 1 and 2 that use memoization to attempt to improve their efficiency.\n",
"\n",
"Do they benefit significantly from this modification? Does one benefit more than the other?"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.10"
}
},
"nbformat": 4,
"nbformat_minor": 4
}