Advanced Algorithms (Fall 2014)

Shay Mozes

Lecture 5 Video [previous] [next]

[+] Solving hard problems on structured instances

We discuss problems that are NP-Hard, but can be solved efficiently if we assume the input is restricted in some way. Examples include minimum independent set on trees using greedy and dynamic programming algorithms, the partition problem on powers of two, facility location problems on trees, and maximum independent set on interval graphs.

Download Video: 720p

Lecture notes, page 1/76 • [previous page] • [next page] • [PDF]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email me.