Notions of Intractability I

View slides in full screen

Warning

The previous slides are provided as a reminder of the material seen in class. They are intended to be complemented with the vocal part and the blackboard, therefore they are not in any way a substitute of a book, nor some lecture notes. Please use the books provided in the references for the self-study.

Exercises

Once you have revised the material from this class, you can try to do the problems from the EDA ProblemSet, section 7 Intractabilitat. In particular 7.1, 7.2, 7.3, 7.4 . Those exercises will be solved in class in the Problem class P7.

After this class and/or the Problem class P7 you should also be able to solve the following MidTerm EDA Exams from the Collection of Solved Exams, for instance:

• 13/01/2020 Final EDA Exam Problem 4
• 09/06/2020 Final EDA Exam Problem 4A-4B
• 08/01/2021 Final EDA Exam Problem 3
• 07/06/2021 Final EDA Exam Problem 1.b
• 16/01/2023 Final EDA Exam Problem 4
• 08/01/2024 Final EDA Exam Problem 4

As always, the solutions are in the very same pdf.