search

caltechcs2 / dna_carving

Assignment 4
0 stars 4 forks source link

Re-work question about recursion in seam carving #6

Closed AGFeldman closed 8 years ago

AGFeldman commented 8 years ago

The current writeup describes a seam-carving algorithm, and then asks how "this algorithm" would be implemented recursively. This is very confusing. The algorithm description included dynamic programming, but didn't mark it as such. The question about recursion is trying to ask what the complexity would be without dynamic programming. I and several students at office hours were very confused about this.

I recommend that we change the problem to this: Describe an approach to seam-carving that does not use dynamic programming. Give the students code for a recursive, non-dynamic-programming solution and ask them for the complexity in big-O notation. Keep the question about "How long would it take to find a seam on a 50x50 image if 1billion computations were made per second?". Then, ask the students to use dynamic programming to speed up the computation. (They have to figure out the details of how to use dynamic programming.)

AGFeldman commented 8 years ago

A "band-aid" fix might be to mark dynamic programming in our current algorithm description, and specify that the "recursive solution" does not use dynamic programming.