Python 3.2.5 (default, May 15 2013, 23:07:10) [MSC v.1500 64 bit (AMD64)] on win32 Type "copyright", "credits" or "license()" for more information. >>> ================================ RESTART ================================ >>> # The recursive factorial function >>> def factorial(n): if n == 1: return 1 return n*factorial(n-1) # Computing the probability for a worst-case behaviour for quicksort, for a list of length 10 # The probability is close to 1 >>> n = 10 >>> (2**(n-1) )/ factorial (n) 0.00014109347442680775 >>> n = 20 >>> (2**(n-1) )/ factorial (n) 2.1549902060910883e-13 >>> # Recursive binom: # C(n,k) = C(n-1, k-1) + C(n-2, k) # Naive implementation is exponential >>> >>> binom(4,2) 6 # We interrupted the computation since it takes too much time >>> binom(50,25) Traceback (most recent call last): File "", line 1, in binom(50,25) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) File "C:\Personal\Teaching\CS-intro\2015b\Recitations\6\binom.py", line 9, in binom return binom(n-1,k) + binom(n-1,k-1) KeyboardInterrupt # Running the implementation with memoization - Much faster! - the complexity is O(nk) >>> ================================ RESTART ================================ >>> >>> binom_fast(4,2) 6 >>> binom_fast(50,25) 126410606437752 >>> ================================ RESTART ================================ >>> # printing the contents of the dictionary when the function ended >>> binom_fast(4,2) {(4, 2): 6, (3, 2): 3, (3, 1): 3, (2, 1): 2} 6 >>> ================================ RESTART ================================ # tracing - with memoization >>> >>> binom_fast_trace(4,2) >>(4,2) >>>>(3,2) >>>>>>(2,2) <<<<<<(2,2) >>>>>>(2,1) >>>>>>>>(1,1) <<<<<<<<(1,1) >>>>>>>>(1,0) <<<<<<<<(1,0) <<<<<<(2,1) <<<<(3,2) >>>>(3,1) >>>>>>(2,1) <<<<<<(2,1) >>>>>>(2,0) <<<<<<(2,0) <<<<(3,1) <<(4,2) 6 # tracing - without memoization >>> ================================ RESTART ================================ >>> >>> binom_fast_trace(4,2) >>(4,2) >>>>(3,2) >>>>>>(2,2) <<<<<<(2,2) >>>>>>(2,1) >>>>>>>>(1,1) <<<<<<<<(1,1) >>>>>>>>(1,0) <<<<<<<<(1,0) <<<<<<(2,1) <<<<(3,2) >>>>(3,1) >>>>>>(2,1) >>>>>>>>(1,1) <<<<<<<<(1,1) >>>>>>>>(1,0) <<<<<<<<(1,0) <<<<<<(2,1) >>>>>>(2,0) <<<<<<(2,0) <<<<(3,1) <<(4,2) 6 >>>