{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Module 2, Practical 10\n", "\n", "In this practical we will experiment with **programming paradigms**. \n", "In particular, we will briefly introduce the **dynamic programming** technique. \n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Dynamic programming\n", "\n", "Dynamic programming is a strategy to optimize recursive algorithms. \n", "Every time we find an algorithm solving a bigger problem by *repetitive recursive calls* on smaller subproblems, we can optimize it by using **dynamic programming**. \n", "The key idea is simply to *store* in a table the solution of the subproblems and obtain the result of these subproblems by performing a table lookup. \n", "\n", "Two approaches exist:\n", "\n", "1. **Top-down**: solve the problem by breaking it down in smaller subproblems. If the subproblem has already been solved, then the answer has already been saved somewhere. If it has not already been solved, compute a solution and store it. This method is called **memoization**;\n", "\n", "\n", "2. **Bottom-up**: solve the problem by starting from the most trivial subproblems, going up until the complete problem has been solved. Smaller subproblems are guaranteed to be solved before bigger ones. This method is called **dynamic programming**.\n", "\n", "\n", "Consider the classic example of the computation of Fibonacci numbers:\n", "\n", "$$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...$$\n", "\n", "which can be computed by the following recursive formula:\n", "\n", "$$\n", "F(n)=\\left\\{\n", " \\begin{array}{ll}\n", " n & if\\ n == 0\\ or\\ n\\ == 1\\\\\n", " F(n-1)+ F(n-2) & if\\ n > 1\n", " \\end{array}\n", " \\right.\n", "$$\n", "\n", "This problem can be solved with the following recursive code:" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Fib(0)= 0\n", "Fib(1)= 1\n", "Fib(2)= 1\n", "Fib(3)= 2\n", "Fib(4)= 3\n", "Fib(5)= 5\n", "Fib(6)= 8\n", "Fib(7)= 13\n", "Fib(8)= 21\n", "Fib(9)= 34\n", "Fib(10)= 55\n", "Fib(11)= 89\n", "Fib(12)= 144\n", "Fib(13)= 233\n", "Fib(14)= 377\n", "Fib(15)= 610\n", "Fib(16)= 987\n", "Fib(17)= 1597\n", "Fib(18)= 2584\n", "Fib(19)= 4181\n", "\n", "Fib(35)= 9227465\n", "It took 1.74s\n", "\n", "Fib(36)= 14930352\n", "It took 2.77s\n", "\n", "Fib(37)= 24157817\n", "It took 4.48s\n", "\n", "Fib(38)= 39088169\n", "It took 7.26s\n", "\n", "Fib(39)= 63245986\n", "It took 11.67s\n" ] } ], "source": [ "import time\n", "\n", "def fib(n):\n", " if n <= 1:\n", " return n\n", " else:\n", " return fib(n - 1) + fib(n - 2)\n", " \n", " \n", "for i in range(20):\n", " print(\"Fib({})= {}\".format(i, fib(i)))\n", "\n", "\n", "for i in range(35,40):\n", " start_t = time.time()\n", " print(\"\\nFib({})= {}\".format(i, fib(i)))\n", " end_t = time.time()\n", " print(\"It took {:.2f}s\".format(end_t-start_t))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Although simple to code, the recursive solution performs some steps multiple times, as shown by the following recursion tree (for example f(3) is computed 5 times):\n", "\n", "![](images/tree.png)\n", "\n", "We can use dynamic programming to avoid computing over and over again the same values:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Fib(0)= 0\n", "Fib(1)= 0\n", "Fib(2)= 1\n", "Fib(3)= 2\n", "Fib(4)= 3\n", "Fib(5)= 5\n", "Fib(6)= 8\n", "Fib(7)= 13\n", "Fib(8)= 21\n", "Fib(9)= 34\n", "Fib(10)= 55\n", "Fib(11)= 89\n", "Fib(12)= 144\n", "Fib(13)= 233\n", "Fib(14)= 377\n", "Fib(15)= 610\n", "Fib(16)= 987\n", "Fib(17)= 1597\n", "Fib(18)= 2584\n", "Fib(19)= 4181\n", "\n", "Fib(35)= 9227465\n", "It took 0.00s\n", "\n", "Fib(36)= 14930352\n", "It took 0.00s\n", "\n", "Fib(37)= 24157817\n", "It took 0.00s\n", "\n", "Fib(1000)= 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875\n", "It took 0.00s\n", "\n", "Fib(1001)= 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501\n", "It took 0.00s\n", "\n", "Fib(1002)= 113796925398360272257523782552224175572745930353730513145086634176691092536145985470146129334641866902783673042322088625863396052888690096969577173696370562180400527049497109023054114771394568040040412172632376\n", "It took 0.00s\n" ] } ], "source": [ "import time\n", "\n", "def fib_dp(n):\n", " fib = [0]* (n+1)\n", " if n > 1:\n", " fib[1] = 1\n", " \n", " for i in range(2, n + 1):\n", " fib[i] = fib[i - 2] + fib[i - 1]\n", " \n", " return fib[n]\n", " \n", "for i in range(20):\n", " print(\"Fib({})= {}\".format(i, fib_dp(i)))\n", "\n", "\n", "for i in range(35,38):\n", " start_t = time.time()\n", " print(\"\\nFib({})= {}\".format(i, fib_dp(i)))\n", " end_t = time.time()\n", " print(\"It took {:.2f}s\".format(end_t - start_t))\n", "\n", "#we can even do:\n", "for i in range(1000,1003):\n", " start_t = time.time()\n", " print(\"\\nFib({})= {}\".format(i, fib_dp(i)))\n", " end_t = time.time()\n", " print(\"It took {:.2f}s\".format(end_t - start_t))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In the latter case we accumulated partial results in a list and re-used them when needed. Consider the following code:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "It took 18.39s\n" ] } ], "source": [ "import time\n", "\n", "def fib_dp(n):\n", " fib = [0]* (n+1)\n", " if n > 1:\n", " fib[1] = 1\n", " \n", " for i in range(2,n + 1):\n", " fib[i] = fib[i - 2] + fib[i - 1]\n", " \n", " return fib[n]\n", " \n", "\n", "start_t = time.time()\n", "for i in range(1,15000):\n", " r = fib_dp(i)\n", "end_t = time.time()\n", "print(\"It took {:.2f}s\".format(end_t-start_t))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In this case we repeated the computations several times anyway and had to recompute the solution all the time, which is a little bit of a waste of time. If we are not concerned about using more space we could modify the code in such a way to update a list and return the whole list, ready for a next iteration: " ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Fibonacci(15000) : 180356212817232358527136269558393274270479577287959770214783776455882580176808282935116449287253001675278567205597341664270703993136851989859494809191272208168671602010135312495296553662790352582033423080689757992520655785610316941531173588408998619812807392167094455165363355259485592278979388870298110870050912172411703995878726547708126588747557108886477742159519675726841476567233617069303168933729769224839193682942110633367322841686836744207977400786184404283243942571683714924012584054120950619420879245008334171878098209414559267738476048405512373264705915648256421029922854826089454770481653365776765021018110912210918296748113016817314353185049893148191072970004722127877580853512230597663125482412037507790122452840808247238862266940374952733301348535189028427982115508256085629078838285854519748549211253115363900979738960948772589014559911367102564396479380119671836661458473444680552841046388920629103926658110037230386547506816712866616340383491227279709660200771238944743897531289959511150305531873160607872566720751381188951153762201432960669039121243742888978686571778654570582578356003787537920689451735958244288072349086881269456351988300299442324421142440230312335818179554507414851349917896307630882698214864014344956780348499120670367075038565963319741348415248138037342603113034434198363994519415494026021710622105031596662576344941382709460665227123428132640271682951472209368453748754510035741638613590279538796566181871895713339174456728394471357415996934436202565485732749272347348991793493320243181956465786389970599533658454386144770652584880176519203467064567384636418219255416950945755037995377546451320680325530900980211314010182766809827492194845387482751225482662997765661866262382112219008183345652570682633899549560294736097218086788785294700336993482784319083980440026327099112563241621005721911339313568395785607613027063516725870186041444932874242502339316433484868302535616417673857358757000197098734066555060275659441540730179880840068680711039092402469979537402038522869532858210224421954879125281803617171486680299882175622463954938841161683824017764172124148438928242788323301450705633955505182591808014745581257657569980476219657313856171171041106956687416108450931365450698373196534957320986723454445945232416845732305494189207716358085853199984634824143123729540264742981573020172237026058046740201545250287662018382140146169998065636288937211877886621661690578651489040221004254744005525689460483194423394923570500857169107685204978377809144999120496376447004389621794981767672901579794816635242858841182877011991980777649470507584848234893126914722042071134658473351945026030226538176505680011883028482299815999170838410236573499975247752075137709072936793331605370102620992579010729955042839150039536988476316814658001111401786786920802580057225089821741914525126541381743907218686111921778056456742847181643346546263899570276608898254139702386798819800561168979805761661085945938400171610214159378775050985949240013649311708619468421748433514761538254173535727874452760668054213182096783214642043675647412439936425441952983174011449159555969819986536279264099966926245798558475510001\n", "It took 0.01s\n", "Fibonacci 0..20: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]\n" ] } ], "source": [ "import time\n", "\n", "def fib_dpV2(n,fibList):\n", " if n < len(fibList):\n", " return fibList[n]\n", " else:\n", " if n == 0:\n", " fibList.append(0)\n", " return 0\n", " if n == 1:\n", " fibList.extend([0,1])\n", " return 1\n", " L = n - len(fibList)\n", " for i in range(L):\n", " # compute all the fibonacci values required to reach fib(n) and store them in the list...\n", " fibList.append(fibList[-2] + fibList[-1])\n", " return fibList[-1]\n", " \n", "\n", "start_t = time.time()\n", "myFibL = []\n", "for i in range(1,15001):\n", " r = fib_dpV2(i, myFibL)\n", "end_t = time.time()\n", "print(\"Fibonacci(15000) : {}\".format(myFibL[-1]))\n", "print(\"It took {:.2f}s\".format(end_t-start_t))\n", "print(\"Fibonacci 0..20: {}\".format(myFibL[0:20]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Excercise\n", "\n", "1. Catalan numbers (info [here](https://en.wikipedia.org/wiki/Catalan_number)) are defined by the following recurrence equation:\n", "\n", "$$\n", "C(n)=\\left\\{\n", " \\begin{array}{ll}\n", " 1 & if\\ n <=1 \\\\\n", " \\sum_{i=0}^{n-1} C(i) C(n-1 -i)& if\\ n > 1\n", " \\end{array}\n", " \\right.\n", "$$\n", "\n", "the first few values are reported below:\n", "\n", "$1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786,$\n", "$208012, 742900, 2674440, 9694845, 35357670, 129644790,$ \n", "$477638700, 1767263190, 6564120420, 24466267020, 91482563640, ...$\n", "\n", "\n", "a. Write a recursive function ```recCatalan(n)``` to compute the n-th catalan number;\n", "\n", "b. Write a dynamic programming function ```dpCatalan(n)``` to compute the n-th catalan number.\n", "\n", "Test your code with:\n", "\n", "```\n", "catN = []\n", "for i in range(0,15):\n", " catN.append(recCatalan(i))\n", " \n", "print(\"First 15 catalan numbers:\")\n", "print(catN)\n", "```\n", "\n", "Finally, check how long it takes to compute the 20th catalan number with the recursive algorithm and with the dynamic programming one.\n", "\n", "
Show/Hide Solution\n" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "First 15 catalan numbers:\n", "[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440]\n", "20th catalan number:\n", "6564120420\n", "It took 463.08s\n", "First 15 catalan numbers (dyn.p):\n", "[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440]\n", "First 30 catalan numbers (dyn.p):\n", "[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, 18367353072152, 69533550916004, 263747951750360, 1002242216651368]\n", "It took 0.00s\n" ] } ], "source": [ "import time\n", "\n", "def recCatalan(n):\n", " if n <= 1:\n", " return 1\n", " else:\n", " cat = 0\n", " for i in range(0, n):\n", " cat += recCatalan(i) * recCatalan(n - 1 - i)\n", " return cat\n", "\n", "def dpCatalan(n):\n", " if n <= 1:\n", " return 1\n", " else:\n", " catNums = [1,1]\n", " for i in range(2,n+1):\n", " catNums.append(0)\n", " for j in range(0,i):\n", " catNums[i] += catNums[j] * catNums[i - j - 1]\n", " return catNums[-1]\n", " \n", "\n", "catN = []\n", "for i in range(0,15):\n", " catN.append(recCatalan(i))\n", " \n", "print(\"First 15 catalan numbers:\")\n", "print(catN)\n", "\n", "catN = []\n", "start_t = time.time()\n", "#for i in range(0,19):\n", "# catN.append(recCatalan(i))\n", "catN = recCatalan(20)\n", "end_t = time.time()\n", "print(\"20th catalan number:\")\n", "print(catN)\n", "print(\"It took {:.2f}s\".format(end_t-start_t))\n", "\n", "\n", "catN = []\n", "start_t = time.time()\n", "print(\"First 15 catalan numbers (dyn.p):\")\n", "for i in range(0,15):\n", " catN.append(dpCatalan(i))\n", "print(catN)\n", "end_t = time.time()\n", "print(\"It took {:.2f}s\".format(end_t-start_t))\n", "\n", "catN = []\n", "start_t = time.time()\n", "for i in range(0,30):\n", " catN.append(dpCatalan(i))\n", "end_t = time.time()\n", "print(\"First 30 catalan numbers (dyn.p):\")\n", "print(catN)\n", "print(\"It took {:.2f}s\".format(end_t-start_t))" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [catalan.py](programming_paradigms/catalan.py)\n", "
" ] } ], "metadata": { "celltoolbar": "Edit Metadata", "kernelspec": { "display_name": "3.10.14", "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.10.14" } }, "nbformat": 4, "nbformat_minor": 2 }