Syllabus: Theory of Computation
Instructor: Guan-Shieng Huang (黃光璿)
Office: Room 314, Science and Technology Building 3
Office Hours: 2:00~5:00 pm, Friday
Web Site: http://staffweb.ncnu.edu.tw/shieng/
Email: shieng@ncnu.edu.tw
Time and Location:
Room 301, Science and Technology Building 3
10:00~12:00 am on Tuesday, 5:00~6:00 pm on Thursday
Teaching Assistant:
Pending
Text Book:
Computational Complexity, C. H. Papadimitriou, Addison-Wesley Pub Co, 1994. （台北書局代理）
Prerequisites:
Data Structures and Algorithms
Formal Languages and Finite Automata
Discrete Mathematics
Description:
This course introduces essential issues in the theory of computation. It includes discussions on models for computations; the decidability; the circuit complexity; computational complexity classes and their relations; the idea of reduction and Cook’s theory; the NP-completeness; the approximability; and finally randomized algorithms. Students who attend this course will learn
Turing machines: Know the model for computations.
Computability: Know the limitation of computations.
Boolean logic: Review fundamental constructs in this logic.
Relations between complexity classes: Major theorems on the relations between complexity classes are established.
Reductions and completeness: We will introduce the basic idea of Cook's theory and show that all NP problems can reduce to the satisfiability problem.
NP-complete problems: We will prove the NP-completeness of around thirty combinatorial problems by using reductions.
coNP and function problems: We focus on problems within NP and coNP. Primality testing is the main issue.
Randomized computation: We will discuss basic concepts and important algorithms that involve randomness.
Grading Policy:
Every student who takes this course should follow two rules: hand in your homework on time and do it by yourself. Cheating is absolutely forbidden and no late homework will be accepted. The distribution of grading is as follows:
50% Homework (about 8 assignments)
50% Paper Reports
There are about eight homework assignments in the form of paper work. In addition, each student should read two regular papers assigned by the instructor before the end of this semester.