D&A -- Learning Objectives Week 7
---------------------------------
students
* learn to know the concept of quad-trees and some applications (collision detection, image segmentation). Get insight into multi-resolution image segmentation methods with simple local regression rules.
* learn to know the concept of memoization with a toy example (Fibonacci Numbers) and see first examples (prefix-/ suffix problems) solved with Dynamic Programming: rod cutting, longest increasing subsequence, piecewise constant approximation of a noisy signal
* see that a dynamic programming algorithm can be applied for problems with optimal substructures and overlapping subproblems. Understand that the subproblems may not provide cyclic dependencies.
* Get an intuition why the formula #subproblems * time/subproblem for the asymptotic runtime is correct for DP problems