Olga Lepsky will present a mock lecture for an undergraduate algorithms course such as COMPSCI 311.
Abstract: Consider the problem of scheduling the maximum number of compatible activities - the interval scheduling problem. This problem could be solved by ordering the intervals and applying the greedy strategy, but we need to choose the correct order. Next, if we add priorities of activities (interval weights) to the problem, the greedy algorithm would fail. For this problem a different algorithm approach is required: the dynamic programming, which will be explained in detail.
There will be a reception in the atrium at 3:40 p.m.