30516  THEORETICAL COMPUTER SCIENCE
Department of Computing Sciences
ALON ROSEN
Lezioni della classe erogate in presenza
Suggested background knowledge
Mission & Content Summary
MISSION
CONTENT SUMMARY
Unit 1 (Computability  introduction)
· Course overview
· Introduction
· Turing Machine (TM)
Unit 2 (Computability – more on TM)
· More on the definition of TM
· Decidable and Recognizable languages
· Variants of TM
· Simulation
Unit 3 (Computability – undecidability)
· The ChurchTuring Thesis
· Examples of decidable languages
· The Halting problem
Unit 4 (Computability – undecidability contd.)
· More nondecidable problems
· Reductions
Unit 5 (Computability – Rice’s theorem)
· Rice’s Theorem
· Post Correspondence Problem
· Wrap up computability
Unit 6 (Complexity  Introduction)
· Definition of time complexity
· Complexity of single vs Multiple Tape TM’s
· PTIME, PATH
Unit 7 (Complexity – The class NP)
· Nondeterministic TM
· Polytime verifiability
· The classes NP and coNP
Unit8 (Complexity – NP completeness)
· Polytime reducibility
· NP completeness
· Existence of NPcomplete problems
Unit 9 (Complexity – CookLevin)
· CookLevin Theorem
· More NPcomplete problems
· Decision vs. Search
Unit 10 (Complexity – The class PSPACE)
· Cook/Karp/Levin reductions
· Coping with NPhardness
· Space complexity
Unit 11 (Cryptography  Encryption)
· Perfect secrecy
· Computational secrecy
Unit 12 (Cryptography  Authentication)
· Message authentication
· Digital signatures
Intended Learning Outcomes (ILO)
KNOWLEDGE AND UNDERSTANDING
The most important skill that the students are expected to pick up during this course is the ability to recognize and interpret computational intractability in case it is encountered. The course aims to develop a solid conceptual understanding of notions related to computation:
· The concept of universal models of computation (such as Turing machines), that capture our intuitive notion of computation and allow us to reason about the capabilities of computers in a technologyindependent manner.
· The existence of intrinsic limits to computation. Computational problems that cannot be solved by any algorithm whatsoever (undecidability), and problems that are solvable but require unreasonable computational resources (computational complexity).
· The notion of nondeterminism and in particular the conceptual difference between finding a solution and verifying that a given solution is correct.
· The representation of computational problems, and the distinction/relationships between decision and search problems.
· The notion of a reduction between computational problems and its implications on the relative complexity of the problems.
APPLYING KNOWLEDGE AND UNDERSTANDING
 Recognize problems that are NPcomplete, and be able to devise simple NPcompleteness proofs
 Recognize problems that are undecidable, and be able to devise simple undecidability proofs
 Apply the idea of a reduction among computational problems
 Apply definitions of security in encryption and authentication
 Be able to spot potential problems in proposed cryptographic protocols
Teaching methods
 Facetoface lectures
 Online lectures
 Guest speaker's talks (in class or in distance)
DETAILS
Biweekly homework assignments (45 questions each) will give you feedback on how you are doing and will help you internalize the material studied.
Assessment methods
Continuous assessment  Partial exams  General exam  


x  

x 
ATTENDING AND NOT ATTENDING STUDENTS
Assessment will be the same for attending and nonattending students.
Written exam (70% of the final grade) consists of openended questions,
some of which will test the student's understanding of the concepts
developed during the course (for example, the ability to reason about
graphs, to reason about the correctness of a given algorithm, or to analyze
the running time of a given
algorithm) and some of which will test the student's ability to apply such
concepts to new contexts, for example their ability to devise an algorithm
for a new problem, to prove the NPcompleteness of a new problem, or to
prove the undecidability of a new problem.
Students can take the first partial written exam in the middle of the
semester and complete the second partial exam at the end of the course. In
this case the weight is: 35% for the first partial exam and 35% for the
second partial exam.
Alternatively, students can take a final written exam that accounts for 70%
of the final grade.
Teaching materials
ATTENDING AND NOT ATTENDING STUDENTS
There is no required textbook. Recommended textbooks will be communicated to the students at the start of classes. Lecture slides and notes will be provided for selected topics.