String Edit Distance (and intro to dynamic programming)
String Edit Distance
(and intro to dynamic programming)
Lecture #4
Computational Linguistics
CMPSCI 591N, Spring 2006
University of Massachusetts Amherst
Andrew McCallum
Andrew McCallum, UMass Amherst,
including material from William Cohen
Dynamic Programming
? (Not much to do with ¡°programming¡± in the
CS sense.)
? Dynamic programming is efficient in finding
optimal solutions for cases with lots of
overlapping sub-problems.
? It solves problems by recombining solutions
to sub-problems, when the sub-problems
themselves may share sub-sub-problems.
Andrew McCallum, UMass Amherst,
including material from William Cohen
Fibonacci Numbers
1 1 2 3 5 8 13 21 34 ...
Andrew McCallum, UMass Amherst,
including material from William Cohen
1
Andrew McCallum, UMass Amherst,
including material from William Cohen
Calculating Fibonacci Numbers
F(n) = F(n-1) + F(n-2),
where F(0)=0, F(1)=1.
Non-Dynamic Programming implementation
def fib(n):
if n == 0 or n == 1:
return n
else:
return fib(n-1) + fib(n-2)
For fib(8), how many calls to function fib(n)?
Andrew McCallum, UMass Amherst,
including material from William Cohen
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- string comparison
- python 3 beginner s reference cheat sheet http www
- using python in labeling and field calculations
- python cheat sheet programming with mosh
- string edit distance and intro to dynamic programming
- tries and string matching stanford university
- logix 5000 controllers ascii strings 1756 pm013g en p
- a guide to f string formatting in python
Related searches
- intro to philosophy pdf
- intro to philosophy notes
- intro to ethics quizlet
- intro to finance pdf
- intro to business online textbook
- intro to finance textbook
- intro to philosophy textbook pdf
- intro to business
- intro to biology games
- intro to philosophy study guide
- intro to philosophy class
- intro to project management pdf