Lecture 1: Course Overview, Interval Scheduling

What this lecture covers

This opening lecture of MIT's Design and Analysis of Algorithms course sets up the semester's central question: how small changes to a problem's constraints can move it between easy, harder-but-still-polynomial, and intractable. After a short logistics overview, Professor Devadas reviews the classes P and NP and what makes a problem NP-complete, then uses a single running example, scheduling requests on a resource, to show the same idea in action three times.

By the end, you can state the interval scheduling problem, explain why picking the request with the earliest finish time is provably optimal, see how adding weights turns the same problem into a dynamic programming exercise, and recognize why adding multiple non-identical machines pushes the problem into NP-completeness.

Key ideas

• P: the class of problems solvable in polynomial time, such as O(V^2) shortest paths.
• NP: problems whose proposed solutions can be verified in polynomial time, such as checking a Hamiltonian cycle.
• NP-complete: the hardest problems in NP; solving any one of them in polynomial time would solve all of NP in polynomial time.
• Interval scheduling: given requests each with a start and finish time on a single resource, select the largest compatible subset.
• Greedy algorithm template: repeatedly pick a request by a simple rule, reject everything incompatible with it, and recurse on what remains.
• Earliest finish time rule: among the rules tried (smallest interval, numeric order, fewest incompatibilities), only picking the request that finishes earliest is proven optimal, by induction on the size of the optimal solution.
• Weighted interval scheduling: when requests carry weights and you want maximum total weight rather than maximum count, the greedy rule fails and a dynamic programming solution is needed instead.
• Problem generalization and hardness: allowing multiple non-identical machines, where each request can only run on a subset of machines, turns the scheduling decision problem into an NP-complete one.

Walkthrough

Course overview and logistics (0:00)

The lecture opens with introductions (Devadas, Demaine, and Lynch as co-lecturers) and course logistics: 6.006 is a prerequisite, coursework runs through the Stellar website, and problem sets are worth 30% of the grade but carry a larger penalty for not attempting them. Devadas then previews the course's modules: divide and conquer, greedy algorithms, dynamic programming, network flow, intractability, and advanced topics such as distributed algorithms and cryptography.

P, NP, and NP-completeness (10:06)

Devadas frames the semester's theme: small changes to a problem statement can move it from an easy linear-time solution to something intractable. He reviews P as problems solvable in polynomial time, NP as problems whose solutions are verifiable in polynomial time (using the Hamiltonian cycle problem as an example), and NP-completeness as the property that a problem is both in NP and at least as hard as every other problem in NP. Reductions between problems are introduced as the tool for showing a new problem is hard.

Defining interval scheduling (17:07)

The problem is defined formally: a single resource, requests numbered 1 through n, each with a start time s_i and finish time f_i where s_i < f_i. Two requests are compatible if their intervals don't overlap (a shared boundary point counts as compatible). The goal is to select the largest compatible subset of requests, illustrated with a six-interval example where the answer is three.

Testing greedy selection rules (24:13)

Devadas defines the greedy template: pick a request by some rule, reject everything incompatible with it, repeat. Students propose several selection rules interactively: earliest finish time, numeric order, shortest interval, and fewest incompatible requests. Counterexamples drawn on the board eliminate every rule except earliest finish time, which survives every example tried.

Proving earliest finish time is optimal (41:36)

The lecture gives a full induction proof that the greedy algorithm using earliest finish time always produces a maximum-size compatible set. The proof inducts on the size K* of an optimal solution: the base case is a single interval, and the inductive step swaps the first interval of an assumed optimal solution for the greedy algorithm's first pick, shows the resulting schedule is still optimal, and then applies the inductive hypothesis to the smaller remaining problem to conclude the greedy schedule matches K* + 1.

Weighted interval scheduling by dynamic programming (1:01:56)

Adding a weight w_i to each request and asking for maximum total weight breaks the greedy rule, shown with a two-request counterexample. Devadas builds a dynamic programming solution instead: subproblems R(f_i) consist of requests starting no earlier than f_i, giving n subproblems total. The recursion tries every request i as the first pick and takes opt(R) = max over i of w_i + opt(R(f_i)), giving an O(n^2) algorithm (a faster O(n log n) version is left for section).

From polynomial to NP-complete (1:20:05)

The lecture closes by generalizing to multiple, non-identical machines, where each request can only run on a specified subset of machines. This small change makes the decision version of the problem ("can K requests be scheduled?") NP-complete, previewing the course's later treatment of approximation algorithms and exponential-time fallbacks for intractable problems.

Before you watch

• Review basic data structures, sorting, dynamic programming, and shortest-path algorithms from an introductory algorithms course (6.006 or equivalent), since this lecture assumes that background.
• Be ready to think about proofs by induction; the earliest-finish-time proof is done in full detail as a model for later problem sets.

Check your understanding

1. Why does picking the request with the earliest finish time always leave room for at least as many future selections as any other first pick?
2. In the induction proof, why is it valid to replace the first interval of an optimal solution with the greedy algorithm's first pick without changing the schedule's size?
3. Why does the same greedy rule that works for unweighted interval scheduling fail once requests have different weights?
4. What are the subproblems R(f_i) in the weighted interval scheduling DP, and why do they not simply equal "all requests compatible with request i"?
5. What specific change to the interval scheduling problem moves it from polynomial time into NP-completeness?