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. |
Revision as of 21:54, 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.