Reading material and exercises

Here is some reading material for the past two weeks, I apologise for the delay.

• Page 236 to to page 273 in the IN210 compendium, this has some old slides from 1999s. (https://github.uio.no/IN3130/h26/blob/main/material/IN210_lec11%2Clec12.pdf),
• "C10": (https://github.uio.no/IN3130/h26/blob/main/material/chapter-10.pdf)
  • In my opinion it has an unnecessarily high level of formalism. Focus on the underlying ideas, not the formalisation. 

Exercises:

• Consider the problem of EXAM PLANNING, model this problem using a SAT formula
  • EXAM PLANNING given
    • E(xams), T(ime slots), R(ooms), S(tudents), and an a set of pairs of exams and students giving which students are taking which exams.
      • Find out whether there is a plan (mapping each exam to exactly one time slot and exactly one room) where there are no conflicts
      • no student has more than one exam for a given time slot
      • no exam can share a room in the same time slot
  • an example input would be:
    • E={Maths, English, Norwegian}
    • T={16.12, 17.12} (days)
    • R={404, 405}
    • S={1,2,3,4,5,6}
    • {(Maths, 1), (Maths, 2), (Maths, 3), (English, 1), (English, 4), (English, 5), (Norwegian, 2), (Norwegian, 4), (Norwegian, 6)}
  • What more can we tell from the assignment, other than whether or not it is possible?
  • What are the drawbacks of using SAT over other models?
• In C10
  • 10.1
  • 10.2
  • 10.3
  • 10.12
  • 10.23