[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[Honesty]
[On Teaching and Learning]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Readings]
[Reference]
Misc:
[SamR]
[Java 1.5 API]
[Espresso]
[TAO of Java]
[CS152 2004F]
[CS152 2005S]
[CS152 2005F]
Held: Friday, April 7, 2006
Summary: Today we consider dynamic programming, an algorithm design technique that can significantly improve the running time of very slow algorithms.
Related Pages:
Assignments
Notes:
Overview:
public long fib(int n) { if (n < 2) return n; else return fib(n-1) + fib(n-2); } // fib(int)
public long fibra(int n) { // Build a cache, use -1 for "I don't know." int cache = new long[n+1]; cache[0] = 0; cache[1] = 1; for (int i = 2; i <= n; i++) cache[i] = -1; // Compute the nth number using the cache. fibra_helper(n, cache); } // fibra(int) public long fibra_helper(int n, long[] cache) { // If the cache contains no value if (cache[n] == -1) // Compute it cache[n] = fibra_helper(n-1, cache) + fibra_helper(n-2, cache); // The cache must now return a value, so // return it. return cache[n]; } // fibra_helper
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[Honesty]
[On Teaching and Learning]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Readings]
[Reference]
Misc:
[SamR]
[Java 1.5 API]
[Espresso]
[TAO of Java]
[CS152 2004F]
[CS152 2005S]
[CS152 2005F]
Disclaimer:
I usually create these pages on the fly
, which means that I rarely
proofread them and they may contain bad grammar and incorrect details.
It also means that I tend to update them regularly (see the history for
more details). Feel free to contact me with any suggestions for changes.
This document was generated by
Siteweaver on Tue May 9 08:31:47 2006.
The source to the document was last modified on Thu Jan 12 14:58:07 2006.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2006S/Outlines/outline.36.html
.
You may wish to
validate this document's HTML
;
;
Check with Bobby