Differences
This shows you the differences between two versions of the page.
| courses:cs211:winter2012:journals:jeanpaul:chaptersixsectionii [2012/03/28 01:28] – created mugabej | courses:cs211:winter2012:journals:jeanpaul:chaptersixsectionii [2012/03/28 01:37] (current) – [Designing the Algorithm] mugabej | ||
|---|---|---|---|
| Line 12: | Line 12: | ||
| >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> | ||
| \\ | \\ | ||
| + | ===== Analyzing the Algorithm ===== | ||
| + | \\ | ||
| + | * It is easily proved by induction on j that the above algorithm writes OPT(j) in array entry M[j](See previous section in the book for the proof). We can then pass the filled-in array M to Find-Solution(shown in the previous section) and get the optimal solution in addition to its value. | ||
| + | * The running time of Iterative-Compute-OPT is O(n) as it runs for n iterations spending O(1) time on each iteration.\\ | ||
| + | ** Basic outline of Dynamic Programming** | ||
| + | \\ | ||
| + | >>>>>>>>>>>>>>>>> | ||
| + | >>>>>>>>>>>>>>>>> | ||
| + | >>>>>>>>>>>>>>>>> | ||
| + | |||
| + | This section was both short and straightforward. I give it an 8/10 | ||
