Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2012:journals:jeanpaul:chaptersixsectioni [2012/03/28 01:09] – [Designing a Recursive Algorithm] mugabej | courses:cs211:winter2012:journals:jeanpaul:chaptersixsectioni [2012/03/28 01:13] (current) – [Memoizing the Recursion] mugabej | ||
|---|---|---|---|
| Line 54: | Line 54: | ||
| By the Memoization technique, we can simply store the value of each Compute-OPT in a globally accessible structure the first time we compute it and simply use this precomputed value in place for all future recursive calls.\\ | By the Memoization technique, we can simply store the value of each Compute-OPT in a globally accessible structure the first time we compute it and simply use this precomputed value in place for all future recursive calls.\\ | ||
| **Algorithm with Memoization** | **Algorithm with Memoization** | ||
| - | \\ | + | |
| - | >>>>>>>>>>>>>>>> | + | >>>>>>>>>>>>>>>> |
| - | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | + | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> |
| >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | ||
| >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | ||
| Line 72: | Line 72: | ||
| * M-Compute-OPT algorithms gives us the value of an optimal solution. But we also need to know the optimal solution(made of a set of non overlapping intervals) itself. | * M-Compute-OPT algorithms gives us the value of an optimal solution. But we also need to know the optimal solution(made of a set of non overlapping intervals) itself. | ||
| * Following is the algorithm to efficiently find the solution:\\ | * Following is the algorithm to efficiently find the solution:\\ | ||
| + | \\ | ||
| + | |||
| >>>>>>>>>>>>>>>> | >>>>>>>>>>>>>>>> | ||
| >>>>>>>>>>>>>>>> | >>>>>>>>>>>>>>>> | ||
| Line 87: | Line 89: | ||
| \\ | \\ | ||
| \\ | \\ | ||
| + | This section was really interesting, | ||
