Round 6: Dynamic programming and greedy algorithms

This round introduces two algorithm design techniques, dynamic programming and greedy algorithms, that can be applied to solve many decision and optimization problems.

Contents:

• Dynamic programming
• Greedy Algorithms

Material in Introduction to Algorithms (Aalto access):

• ​ Dynamic programming: Sections 14.0, 14.1 and 14.4

• ​ Basics of greedy algorithms: Sections 15.1 and 15.2

Material elsewhere and external links:

• ​ MIT Open Courseware video on dynamic programming, part I (we’ll come back to shortest paths, introduced in the second half of the video, later in this course)

• ​ MIT Open Courseware video on dynamic programming, part II

• ​ MIT Open Courseware video on dynamic programming, part III