Outline:

1. Partitioning tasks as bin packing
   • overview
   • complexity
2. A brief intro to P vs NP
3. Heuristics for bin packing
   • next-fit
   • first-fit
   • best-fit
   • worst-fit
4. How to read a paper
   • title, abstract, and intro
   • read section and sub-section headings, figures, and conclusion
   • read middle section, skipping proofs
   • read proofs

Reading assignment (to be completed by the next class):

• Keshav, S. “How to Read a Paper” (2016)
• Dhall, Sudarshan K., and Chung Laung Liu. “On a real-time scheduling problem.” Operations research 26, no. 1 (1978): 127-140.
  • First pass, part 1: read the title, abstract, and section 1
  • First pass, part 2: read section headings and section 6
  • Second pass, part 1: read sections 2-3
  • Second pass, part 2: read sections 4 and 5, reading everything but the proofs (do read the statements of lemmas and theorems)