Understanding Reductions in Computation

In this lecture our goal is to develop ways to classify problems according to their computational requirements. We introduce the concept of reduction as a technique for studying the relationship among problems. People use reductions to design algorithms, establish lower bounds, and classify problems in terms of their computational requirements.

Desiderata - Something that is needed or wanted

Designing Algorithms

SPT Scheduling - Shortest Processing Time Scheduling

Establishing Lower Bounds

Classifying Problems