11933 - Theoretical Computer Science

Course contents

• Problems and algorithms
• Computability vs Complexity
• Turing machines
• Recursive and recursively enumerable problems
• Complexity classes
• The classes P and NP
• NP-complete problems, and the P vs. NP question
• A quick look at space complexity classes
• A quick look at oracle classes, class hierarchies, and functional classes

Prerequisites:

Students are assumed to have a solid background in algorithmic reasoning, to have acquired the notion of subroutine call, and to be somewhat familiar with basic data structures such as lists, trees, and graphs. Previous knowledge of the notion of finite state automaton is helpful but not necessary.

Readings/Bibliography

Textbook:

• Hopcroft, Motwani, Ullman. Introduction to Automata Theory, Languages, and Computation. 3rd ed. Pearson Education, 2013
  

Additional readings:

• Sipser. Introduction to the Theory of Computation. 3rd ed. Cengage Learning, 2012
  
• Arora, Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009

Teaching methods

Lectures; Guided exercises.

Assessment methods

The examination consists of a written test and, where applicable, an oral exam.

The written test includes:

• One exercise requiring the design of a Turing machine that decides a given language.

• Four or five open-ended theoretical questions covering the topics discussed during the course.

• A couple of proofs of theoretical results presented in the lectures.

• One exercise requiring the student to prove that a language (not discussed during the course) is either decidable or undecidable.

• One exercise requiring the student to determine the computational complexity of a problem (not discussed during the course), typically by proving that it is NP-complete.

Depending on the marks obtained in the written test (in addition to the option of rejecting the marks obtained and retaking the written test), the following scenarios apply:

• 15–17 (inclusive): the student may take the oral exam in order to achieve a final grade of 18, but no higher.

• 18–25 (inclusive): the student may accept and register the written test marks as the final grade of the exam without taking the oral exam.

• 26–27 (inclusive): the student may either accept and register the written test marks as the final grade of the exam, or take the oral exam.

• 28 or higher: the student may either accept and register a final grade of 27 (without taking the oral exam) or take the oral exam.

The oral exam may result in a higher grade, a lower grade, or the same grade as the written test. Once a student chooses to take the oral exam and the examination begins, the written test result is forfeited. The final grade will therefore be determined solely by the outcome of the oral exam. It is not possible to revert to or retain the written test marks.

Both the written test and the (optional) oral exam are designed to assess not only the student's knowledge of the course material, but also their ability to reason formally and apply that knowledge. In particular, the following grading bands correspond to the expected competencies.

• 18–21: A good understanding of the fundamental definitions (the minimum required to pass the examination) and the ability to manipulate simple concepts. E.g., the notions of algorithm, computational problem, language, and Turing machine (including its variants); the complexity classes P, NP, and NP-hard; the notion of reduction; examples of undecidable problems; examples of NP-complete problems.
  
  
• 22–26: A good and precise understanding of more advanced definitions; the ability to formally prove relatively simple results; and the ability to relate basic concepts. E.g., formal examples of reductions; formal proofs of the undecidability of selected languages; formal proofs of NP-completeness for selected problems; Rice's Theorem.
  
  
• 27 and above: The ability to formally prove more advanced results and to connect more sophisticated concepts. E.g., proving that the Hamiltonian Cycle problem is NP-complete; proving Cook's Theorem; advanced undecidability proofs.

To be awarded "cum laude" (30L), in addition to demonstrating complete mastery of all course material, the student must also show the ability to make creative connections between topics and to answer questions concerning concepts that were not explicitly covered during the lectures.

Within each grading band, the specific grade depends on the quality of the student's presentation and reasoning. In particular, among others, the evaluation considers the following areas:

• To what extent has the student mastered the concepts?

• Can they apply and manipulate those concepts effectively?

• Are the definitions they provide precise and formally correct?

• Are their proofs sufficiently rigorous?

• Is the exposition logically coherent?

• Are causal relationships made explicit?

• Are the connections between concepts clear?

 

Use of Artificial Intelligence During Examinations: The use of Artificial Intelligence tools, whether generative or non-generative, is strictly prohibited in any form during both the written and oral examinations. Any use of AI is considered a violation of the principles of honesty and fairness and constitutes a breach of academic integrity.

Any suspicion that AI tools have been used during an examination may, at the sole discretion of the instructor, result in the student being required to take a mandatory oral examination to verify their knowledge.

 

Students with learning disorders and\or temporary or permanent disabilities: please, contact the office responsible (https://site.unibo.it/studenti-con-disabilita-e-dsa/en/for-students) as soon as possible so that they can propose acceptable adjustments. The request for adaptation must be submitted in advance (15 days before the exam date) to the lecturer, who will assess the appropriateness of the adjustments, taking into account the teaching objectives.

Teaching tools

The pdf files of the virtual whiteboard will be provided.

Office hours

See the website of Enrico Malizia