Recitation 9
From 6.006: Introduction to Algorithms
(Difference between revisions)
Line 1: | Line 1: | ||
− | == Code for number of paths == | + | == Code for number of paths == |
[http://courses.csail.mit.edu/6.006/fall07/source/dp.py DP] and [http://courses.csail.mit.edu/6.006/fall07/source/memo.py memoization] code for counting the number of "paths" in an n*n grid. | [http://courses.csail.mit.edu/6.006/fall07/source/dp.py DP] and [http://courses.csail.mit.edu/6.006/fall07/source/memo.py memoization] code for counting the number of "paths" in an n*n grid. |
Latest revision as of 21:55, 30 January 2008
Code for number of paths
DP and memoization code for counting the number of "paths" in an n*n grid.
Here a path is like the one from the previous lecture: Start at some cell in the top, and at each row, choose a cell touching (either below, below and to the left, or below and to the right) the cell chosen in the previous row.
Matrix Chain Multiplication
Given a chain of matrices (of varying sizes) computer the optimal order to multiply them in. See CLRS 15.2 (page 331) for details.