Thu March 28

First : remaining midterm projects

• Nick - Kruskal's
• Eoghan - Prim's

Second : start describing how dynamic programming works.

Third : I've posted an assignment for Tuesday where you get to try some!

dynamic programming

It's a terrible name - really it's a variation on recursion and divide-and-conquer : find a way make the problem smaller, saving intermediate results as you go along, while building up the final answer. Oh, and be clever about the order of doing the smaller pieces.

The only way I know to get a handle on this to try to work some of these yourself.

We'll look at several examples in class :

• fibonacci series (textbook)
• longest increasing sequence (textbook)
• coin change problem : projecteuler | mathblog | tutorialhorizon
• change-making problem
  • greedy ? sometimes ... if a "good" set of coin values.
  • dynamic programming ! <= This explanation is worth studying ... and comparing to the Fibonacci example.
• knapsack problem (We may not get to this today.)

There is a nice list of examples at sanfoundry with solutions ... and the homework for Tuesday asks you to pick two of them to study, understand, implement, and explain next Tuesday. :)

I've attached the fibonacci files we did in class.

attachments

		last modified	size
	fib1.py	Sun Dec 22 2024 01:27 am	329B
	fib2.py	Sun Dec 22 2024 01:27 am	463B
	fib3.py	Sun Dec 22 2024 01:27 am	399B