>>> ================================ RESTART ================================ # computing binomial coefficient recursively >>> binom(4,2) >>> binom(50,25) # killed it; takes too long Traceback (most recent call last): File "", line 1, in binom(50,25) File "/Users/Yael/Google Drive/cs1001/week6/4class/2a_binom.py", line 8, in binom return binom(n-1,k) + binom(n-1,k-1) File "/Users/Yael/Google Drive/cs1001/week6/4class/2a_binom.py", line 8, in binom return binom(n-1,k) + binom(n-1,k-1) File "/Users/Yael/Google Drive/cs1001/week6/4class/2a_binom.py", line 8, in binom KeyboardInterrupt # we need memoization # memoization uses a dictionary # a reminder of some basic dictionary operations: >>> d = dict() >>> type(d) >>> d[1] = 3 >>> d {1: 3} >>> d[1] 3 >>> d[1] = 4 >>> d {1: 4} >>> 1 in d True >>> "yael" in d False >>> d["adf"] = 9 >>> d {1: 4, 'adf': 9} >>> ================================ RESTART ================================ # computing binomial coefficient with memoization; added printing of the dictionary's content >>> binom_fast(4,2) {(4, 2): 6, (3, 2): 3, (3, 1): 3, (2, 1): 2} 6 >>> binom_fast(50,25) {(7, 3): 35, (31, 6): 736281, (16, 6): 8008, (16, 9): 11440, (31, 19): 141120525, (46, 25): 6943526580276, (30, 6): 593775, (19, 4): 3876, (18, 4): 3060, (42, 25): 254661927156, (41, 23): 202112640600, (22, 19): 1540, (21, 9): 293930, (20, 7): 77520, (43, 20): 960566918220, (42, 20): 513791607420, (29, 25): 23751, (21, 6): 54264, (44, 23): 2012616400080, (43, 25): 608359048206, (8, 5): 56, (23, 7): 245157, (45, 22): 4116715363800, (10, 8): 45, (11, 5): 462, (10, 7): 120, (17, 7): 19448, (12, 6): 924, (35, 21): 2319959400, (15, 11): 1365, (14, 1): 14, (13, 7): 1716, (36, 22): 3796297200, (26, 17): 3124550, (25, 15): 3268760, (15, 4): 1365, (38, 17): 28781143380, (37, 23): 6107086800, (26, 12): 9657700, (39, 20): 68923264410, (29, 17): 51895935, (3, 2): 3, (30, 14): 145422675, (28, 10): 13123110, (31, 15): 300540195, (36, 15): 5567902560, (29, 11): 34597290, (32, 23): 28048800, (7, 5): 21, (31, 24): 2629575, (30, 16): 145422675, (20, 19): 20, (19, 13): 27132, (17, 13): 2380, (41, 24): 151584480450, (31, 21): 44352165, (21, 18): 1330, (20, 14): 38760, (18, 10): 43758, (32, 22): 64512240, (47, 22): 14833897694226, (21, 15): 54264, (33, 23): 92561040, (32, 25): 3365856, (22, 12): 646646, (44, 25): 1408831480056, (34, 20): 1391975640, (23, 9): 817190, (35, 14): 2319959400, (34, 14): 1391975640, (24, 21): 2024, (14, 8): 3003, (12, 8): 495, (26, 24): 325, (25, 16): 2042975, (15, 13): 105, (37, 16): 12875774670, (27, 21): 296010, (26, 23): 2600, (40, 21): 131282408400, (22, 6): 74613, (28, 22): 376740, (2, 1): 2, (26, 2): 325, (29, 23): 475020, (27, 11): 13037895, (5, 1): 5, (29, 4): 23751, (28, 12): 30421755, (7, 2): 21, (37, 14): 6107086800, (19, 18): 19, (17, 6): 12376, (16, 10): 8008, (31, 18): 206253075, (19, 7): 50388, (18, 5): 8568, (17, 11): 12376, (41, 22): 244662670200, (22, 16): 74613, (21, 8): 203490, (18, 16): 153, (42, 21): 538257874440, (23, 21): 253, (22, 7): 170544, (21, 5): 20349, (25, 2): 300, (43, 24): 800472431850, (8, 6): 28, (23, 6): 100947, (22, 10): 646646, (45, 21): 3773655750150, (10, 9): 10, (9, 7): 36, (11, 4): 330, (10, 4): 210, (34, 9): 52451256, (35, 15): 3247943160, (12, 7): 792, (11, 9): 55, (35, 20): 3247943160, (24, 15): 1307504, (14, 6): 3003, (13, 6): 1716, (37, 25): 1852482996, (36, 23): 2310789600, (25, 14): 4457400, (15, 10): 3003, (38, 22): 22239974430, (37, 22): 9364199760, (26, 13): 10400600, (40, 20): 137846528820, (39, 23): 37711260990, (29, 16): 67863915, (28, 24): 20475, (30, 15): 155117520, (28, 11): 21474180, (6, 1): 6, (29, 10): 20030010, (24, 1): 24, (27, 3): 2925, (7, 4): 35, (30, 17): 119759850, (19, 12): 50388, (17, 12): 6188, (31, 20): 84672315, (21, 17): 5985, (20, 15): 15504, (19, 1): 19, (18, 11): 31824, (16, 3): 560, (23, 18): 33649, (15, 7): 6435, (21, 14): 116280, (33, 22): 193536720, (22, 13): 497420, (34, 21): 927983760, (47, 23): 16123801841550, (23, 8): 490314, (37, 13): 3562467300, (32, 17): 565722720, (33, 8): 13884156, (43, 23): 960566918220, (34, 15): 1855967520, (24, 22): 276, (14, 9): 2002, (12, 9): 220, (43, 18): 608359048206, (26, 25): 26, (25, 23): 300, (15, 12): 455, (13, 12): 13, (25, 3): 2300, (27, 20): 888030, (26, 20): 230230, (25, 4): 12650, (24, 14): 1961256, (28, 23): 98280, (27, 25): 351, (26, 3): 2600, (40, 19): 131282408400, (39, 25): 15084504396, (29, 22): 1560780, (27, 10): 8436285, (49, 25): 63205303218876, (30, 5): 142506, (28, 13): 37442160, (31, 11): 84672315, (30, 24): 593775, (17, 5): 6188, (16, 11): 4368, (40, 24): 62852101650, (19, 6): 27132, (18, 2): 153, (17, 10): 19448, (41, 21): 269128937220, (22, 17): 26334, (20, 1): 20, (33, 24): 38567100, (18, 17): 18, (42, 18): 353697121050, (23, 20): 1771, (22, 4): 7315, (21, 4): 5985, (8, 7): 8, (23, 1): 23, (22, 11): 705432, (45, 20): 3169870830126, (9, 6): 84, (11, 7): 330, (10, 5): 252, (37, 12): 1852482996, (11, 8): 165, (35, 23): 834451800, (25, 24): 25, (24, 16): 735471, (14, 7): 3432, (13, 5): 1287, (37, 24): 3562467300, (36, 16): 7307872110, (25, 13): 5200300, (15, 6): 5005, (38, 23): 15471286560, (37, 21): 12875774670, (26, 10): 5311735, (9, 1): 9, (15, 8): 6435, (39, 22): 51021117810, (28, 25): 3276, (31, 14): 265182525, (40, 18): 113380261800, (30, 12): 86493225, (28, 4): 20475, (38, 13): 5414950296, (50, 25): 126410606437752, (31, 9): 20160075, (29, 9): 10015005, (16, 2): 120, (30, 22): 5852925, (19, 15): 3876, (17, 3): 680, (31, 23): 7888725, (21, 16): 20349, (20, 8): 125970, (18, 8): 43758, (17, 16): 17, (41, 19): 244662670200, (21, 13): 203490, (33, 25): 13884156, (33, 21): 354817320, (22, 2): 231, (32, 15): 565722720, (34, 18): 2203961430, (8, 1): 8, (23, 11): 1352078, (35, 11): 417225900, (33, 15): 1037158320, (11, 1): 11, (34, 12): 548354040, (24, 23): 24, (45, 25): 3169870830126, (12, 10): 66, (35, 17): 4537567650, (25, 22): 2300, (24, 10): 1961256, (32, 11): 129024480, (13, 11): 78, (27, 23): 17550, (26, 21): 65780, (25, 11): 4457400, (24, 2): 276, (28, 16): 30421755, (27, 24): 2925, (24, 12): 2704156, (39, 24): 25140840660, (29, 21): 4292145, (28, 3): 3276, (27, 13): 20058300, (46, 23): 8233430727600, (40, 17): 88732378800, (49, 24): 63205303218876, (30, 10): 30045015, (28, 14): 40116600, (30, 25): 142506, (29, 15): 77558760, (32, 7): 3365856, (17, 4): 2380, (16, 12): 1820, (40, 25): 40225345056, (19, 9): 92378, (18, 3): 816, (17, 9): 24310, (41, 20): 269128937220, (47, 25): 14833897694226, (20, 2): 190, (18, 14): 3060, (42, 19): 446775310800, (32, 18): 471435600, (22, 5): 26334, (21, 3): 1330, (33, 19): 818809200, (22, 8): 319770, (32, 14): 471435600, (34, 24): 131128140, (23, 13): 1144066, (11, 6): 462, (10, 2): 45, (12, 1): 12, (35, 22): 1476337800, (24, 17): 346104, (14, 4): 1001, (13, 4): 715, (36, 17): 8597496600, (25, 12): 5200300, (15, 1): 15, (38, 20): 33578000610, (37, 20): 15905368710, (27, 17): 8436285, (26, 11): 7726160, (25, 1): 25, (24, 4): 10626, (39, 17): 51021117810, (27, 2): 351, (26, 6): 230230, (15, 14): 15, (30, 13): 119759850, (28, 5): 98280, (31, 12): 141120525, (40, 16): 62852101650, (31, 8): 7888725, (29, 8): 4292145, (38, 15): 15471286560, (7, 6): 7, (30, 23): 2035800, (19, 14): 11628, (17, 2): 136, (31, 22): 20160075, (36, 12): 1251677700, (20, 9): 167960, (19, 3): 969, (18, 9): 48620, (41, 18): 202112640600, (21, 12): 293930, (20, 4): 4845, (9, 8): 9, (33, 20): 573166440, (22, 3): 1540, (44, 20): 1761039350070, (34, 19): 1855967520, (8, 2): 28, (23, 10): 1144066, (23, 19): 8855, (32, 13): 347373600, (35, 10): 183579396, (9, 3): 84, (33, 14): 818809200, (30, 8): 5852925, (36, 13): 2310789600, (34, 13): 927983760, (12, 11): 12, (36, 24): 1251677700, (35, 16): 4059928950, (25, 21): 12650, (24, 11): 2496144, (14, 2): 91, (13, 10): 286, (27, 22): 80730, (26, 18): 1562275, (25, 10): 3268760, (39, 14): 15084504396, (38, 18): 33578000610, (28, 17): 21474180, (26, 1): 26, (29, 20): 10015005, (3, 1): 3, (27, 12): 17383860, (40, 23): 88732378800, (24, 6): 134596, (30, 11): 54627300, (28, 15): 37442160, (31, 13): 206253075, (29, 14): 77558760, (38, 14): 9669554100, (16, 13): 560, (20, 16): 4845, (19, 8): 75582, (17, 8): 24310, (47, 24): 16123801841550, (32, 16): 601080390, (20, 3): 1140, (18, 15): 816, (32, 19): 347373600, (21, 2): 210, (44, 19): 1408831480056, (33, 18): 1037158320, (23, 3): 1771, (22, 9): 497420, (9, 4): 126, (23, 12): 1352078, (23, 16): 245157, (32, 12): 225792840, (10, 3): 120, (24, 3): 2024, (39, 15): 25140840660, (12, 2): 66, (11, 10): 11, (35, 25): 183579396, (40, 15): 40225345056, (24, 18): 134596, (14, 5): 2002, (13, 3): 286, (36, 18): 9075135300, (25, 19): 177100, (24, 5): 42504, (38, 21): 28781143380, (37, 19): 17672631900, (27, 16): 13037895, (26, 8): 1562275, (39, 16): 37711260990, (38, 24): 9669554100, (27, 5): 80730, (26, 7): 657800, (48, 24): 32247603683100, (4, 1): 4, (28, 6): 376740, (33, 9): 38567100, (6, 4): 15, (5, 4): 5, (29, 7): 1560780, (16, 4): 1820, (30, 20): 30045015, (19, 17): 171, (17, 1): 17, (31, 17): 265182525, (20, 10): 184756, (19, 2): 171, (18, 6): 18564, (41, 17): 151584480450, (21, 11): 352716, (20, 5): 15504, (35, 12): 834451800, (42, 22): 513791607420, (44, 21): 2012616400080, (34, 16): 2203961430, (8, 3): 56, (23, 5): 33649, (45, 24): 3773655750150, (35, 13): 1476337800, (9, 2): 36, (33, 13): 573166440, (23, 17): 100947, (11, 3): 165, (34, 10): 131128140, (14, 12): 91, (12, 4): 495, (36, 25): 600805296, (35, 19): 4059928950, (25, 20): 53130, (15, 9): 5005, (14, 3): 364, (13, 9): 715, (36, 20): 7307872110, (26, 19): 657800, (25, 9): 2042975, (38, 19): 35345263800, (28, 18): 13123110, (26, 14): 9657700, (29, 19): 20030010, (27, 15): 17383860, (16, 1): 16, (28, 8): 3108105, (6, 2): 15, (40, 22): 113380261800, (29, 13): 67863915, (16, 14): 120, (30, 18): 86493225, (20, 17): 1140, (19, 11): 75582, (18, 1): 18, (17, 15): 136, (22, 20): 231, (21, 20): 21, (20, 12): 125970, (18, 12): 18564, (42, 17): 254661927156, (32, 20): 225792840, (21, 1): 21, (31, 10): 44352165, (33, 17): 1166803110, (23, 2): 253, (22, 14): 319770, (34, 22): 548354040, (23, 15): 490314, (25, 5): 53130, (33, 11): 193536720, (23, 22): 23, (12, 3): 220, (32, 10): 64512240, (35, 24): 417225900, (24, 19): 42504, (14, 10): 1001, (13, 2): 78, (46, 22): 7890371113950, (36, 19): 8597496600, (25, 18): 480700, (15, 3): 455, (37, 18): 17672631900, (27, 19): 2220075, (26, 9): 3124550, (25, 7): 480700, (39, 19): 68923264410, (38, 25): 5414950296, (28, 20): 3108105, (27, 4): 17550, (27, 6): 296010, (48, 25): 30957699535776, (4, 2): 6, (28, 7): 1184040, (27, 9): 4686825, (6, 5): 6, (5, 3): 10, (29, 6): 475020, (31, 7): 2629575, (16, 5): 4368, (24, 7): 346104, (30, 21): 14307150, (19, 16): 969, (16, 8): 12870, (31, 16): 300540195, (46, 24): 7890371113950, (20, 11): 167960, (19, 5): 11628, (18, 7): 31824, (42, 24): 353697121050, (41, 16): 103077446706, (22, 18): 7315, (21, 10): 352716, (20, 6): 38760, (43, 21): 1052049481860, (42, 23): 446775310800, (22, 1): 22, (21, 7): 116280, (44, 22): 2104098963720, (34, 17): 2333606220, (8, 4): 70, (23, 4): 8855, (45, 23): 4116715363800, (24, 8): 735471, (34, 25): 52451256, (33, 12): 354817320, (11, 2): 55, (10, 6): 210, (34, 11): 286097760, (14, 13): 14, (12, 5): 792, (32, 9): 28048800, (35, 18): 4537567650, (24, 13): 2496144, (48, 23): 30957699535776, (13, 8): 1287, (36, 21): 5567902560, (26, 16): 5311735, (25, 8): 1081575, (15, 5): 3003, (38, 16): 22239974430, (28, 19): 6906900, (36, 14): 3796297200, (26, 15): 7726160, (39, 21): 62359143990, (29, 18): 34597290, (27, 14): 20058300, (30, 9): 14307150, (28, 9): 6906900, (43, 19): 800472431850, (24, 9): 1307504, (6, 3): 20, (29, 12): 51895935, (16, 7): 11440, (16, 15): 16, (31, 25): 736281, (30, 19): 54627300, (20, 18): 190, (19, 10): 92378, (17, 14): 680, (41, 25): 103077446706, (22, 21): 22, (21, 19): 210, (20, 13): 77520, (18, 13): 8568, (32, 21): 129024480, (29, 24): 118755, (37, 15): 9364199760, (33, 16): 1166803110, (32, 24): 10518300, (22, 15): 170544, (30, 7): 2035800, (7, 1): 7, (44, 24): 1761039350070, (34, 23): 286097760, (23, 14): 817190, (43, 22): 1052049481860, (10, 1): 10, (9, 5): 126, (33, 10): 92561040, (24, 20): 10626, (14, 11): 364, (13, 1): 13, (32, 8): 10518300, (25, 17): 1081575, (15, 2): 105, (37, 17): 15905368710, (27, 18): 4686825, (26, 22): 14950, (25, 6): 177100, (39, 18): 62359143990, (28, 21): 1184040, (27, 7): 888030, (26, 5): 65780, (36, 11): 600805296, (4, 3): 4, (27, 8): 2220075, (46, 21): 6943526580276, (5, 2): 10, (29, 5): 118755, (26, 4): 14950} 126410606437752 >>> ================================ RESTART ================================ # tracing the execution - removed the memoization from the code in this run >>> 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) >>> ================================ RESTART ================================ # tracing again with memoization; # note that (2,1) returns immediately the second time it is called >>> 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 >>>