A printable PDF is available.

COURSE NUMBER: | CSC 653 |

COURSE TITLE: | Advanced Theory of Computation |

CREDITS: | 3:3 |

PREREQUISITES: | CSC 553 or permission of instructor |

FOR WHOM PLANNED: Graduate students seeking to develop understanding of the underlying fundamentals of computation. This course satisfies the Theory of Computing requirement for Master's students and gives 600-level credit. Graduate students who have had any prior exposure to theory of computing should take this course rather than CSC 553.

INSTRUCTOR INFORMATION: | Name: | Steve Tate |

Office: | Petty 166 | |

Office Hours: | Tues/Thurs 9:30 - 11:30 | |

Phone: | 336-256-1033 | |

E-mail: |

CATALOG DESCRIPTION: Computability theory: Church-Turing thesis (Turing machines, variants, other models); decidability (decidable and undecidable problems for automata and grammars, the halting problem); reducibility (undecidability of mathematical truth).

STUDENT LEARNING OUTCOMES: Upon successful completion of this course students will be able to

*Define*and*describe*formal models of computation, such as finite automata, pushdown automata, and Turing machines;*Give examples*of languages and computational problems appropriate for different models of computation;*Create*proofs for statements regarding formal models of computation;*Describe*class-based resource usage models, including time and space complexity;*Apply*NP-completeness concepts to create proofs regarding the computational complexity of novel problems;*Use*basic concepts and*explain*implications of modern complexity theoretic approaches to advanced topics such as randomization, proof complexity, and quantum computing.

ADDITIONAL INFORMATION: While this course will cover the fundamentals, it is assumed that students have had decent exposure to computability topics in an undergraduate-level course. A significant portion of this course will then be focused on computational complexity, including major topics in theory of computation such as randomization, interactive proofs, parallel computation, and quantum computing.

TEACHING METHODS AND ASSIGNMENTS FOR ACHIEVING LEARNING OUTCOMES: The
primary method of instruction will be two 75-minute periods per week
for lecture and discussion, with students responsible for completing
assigned readings, assignments, and preparing for exams outside of
class. Written assignments should be
turned in on paper and may be either neatly handwritten or printed.
Please do not e-mail written homework solutions unless it is an
emergency situation, and in that case please use a system-independent
format such as a text file or a PDF -- *do not e-mail Word
(.doc or .docx) files*.

EVALUATION AND GRADING: Each student activity will contribute to the final grade in the class according to the following percentages.

This course is primarily concerned with rigorous reasoning about computation. So while there are definitions and facts that must be learned, the main point is to be able to express clear reasoning using the formal definitions. Therefore,

Assignments 35 points Midterm Exams (2) 40 points Final Exam 25 points

*clarity of communication*is extremely important, and grading will reflect not only whether solutions are factually correct, but how clearly and effectively the student's reasoning is expressed.

There are 7 assignments planned: the first assignment will be given on the first day of class and is designed primarily to gauge the background of the students (it will be counted half as much as the remaining assignments). Of the remaining 6 assignments, 2 will be given for each set of topics covered by an exam (mid-term or final), with the goal of having all assignments graded and returned prior to each exam.

REQUIRED TEXTS/READING/REFERENCES: The following required textbook will be the primary source of readings and material for the class:

- Michael Sipser.
*Introduction to the Theory of Computation, Second Edition*, Thompson Course Technology, 2006. ISBN-13 978-0-534-95097-2.

TOPICAL OUTLINE/CALENDAR: The following calendar is approximate, and
reflects the design/plan for the course. __Underlined__ dates
indicate due dates for assignments. Times may be
adjusted as needed during the course, so "schedule shift" may result
in later topics not being covered on the exact dates given below.

Aug 26,28 Class Introduction and Overview Chapter 0 Math Review Sep 2,4,9Finite Automata and Regular Languages Chapter 1 Sep 11,16 Context-Free Languages and Pushdown Automata Chapter 2 Sep 18,23Turing Machines and the Church-Turing Thesis Chapter 3 Sep 25, 30Decidability Chapter 4 Oct 2 Catch-up and review Oct 7 Test 1Oct 9,14 Reducibility Chapter 5 Oct 16,23Time complexity, P, and NP Sections 7.1-7.3 Oct 28, 30NP-completeness Sections 7.4-7.5 Nov 4 Catch-up and review Nov 6 Test 2Nov 11,13 Space complexity Chapter 8 Nov 18 Randomization Section 10.2 Nov 20Interactive Proofs Section 10.4 Nov 25 Parallel Complexity Section 10.5 Dec 2 Quantum Computing Handout Dec 4Final course wrap-up and review Dec 11 Final Exam (12:00 - 3:00)

ACADEMIC INTEGRITY POLICY:
Students are expected to
abide by the UNCG Academic Integrity Policy, which is online
at
`http://academicintegrity.uncg.edu/`

Students are required to sign the Academic Integrity Pledge on any work they do. The pledge is the statement "I have abided by the UNCG Academic Integrity Policy on this assignment."

ATTENDANCE POLICY: Attendance will not be taken in class, and attendance is up to the student. Class periods will focus on discussion of results and proofs, including how to think about and approach problems. This is a vital component of the course, and reading the textbook is no substitute -- students who do not attend all classes are at a serious disadvantage and should not expect to do well in the class. Furthermore, students are responsible knowing for all information from classes, including changes to assignments or class/exam schedule, so any student missing class should get notes from another student who was present.

FINAL EXAMINATION: The final exam will be Thursday, December 11, from 12:00 to 3:00, in the regular classroom. While most of the material on the final exam will be from the material covered after the 2nd exam, it will also contain questions covering topics from the first two exams. Therefore, the answer to the common question "Is the final cumulative?" is "Yes, it is comprehensive, but weighted heavily toward the material covered at the end of the semester."

ADDITIONAL REQUIREMENTS:

**Laptop/Cellphone Policy:**
Laptops can be both a benefit and a distraction in a classroom. While
many students benefit from taking notes using a laptop, or having
access to outside class-related resources during class, other students
cannot resist the temptation of checking e-mail, chatting, or even
playing games during class time. This class has a strict "no
non-class related use" rule for laptops -- if you are found
violating this policy, then your in-class laptop privileges will be
taken away. Cellphones are a distraction for everyone, and should be
turned off during class. If there is a special situation where you
need to have your phone on for a particular day, please let the
instructor know the situation before class.

**Late Policy and Makeup Exams:**
Assignments are due at the beginning of class on the due date, and may
be turned in up to 7 calendars days late with a 25% late penalty.
*No assignment will be accepted more than 7 calendar days after
the original due date!*

Exam/test dates are given in this syllabus, and all students are
expected to be in class on exam dates. Exams
may be made up *only* if it was missed due to an extreme
emergency and arrangements are made *before* the exam date.
Exams (including the final) may not be taken early or late due to
personal travel plans.

ADA STATEMENT: UNCG seeks to comply fully with the Americans with Disabilities Act (ADA). Students requesting accommodations based on a disability must be registered with the Office of Disability Services located in 215 Elliott University Center: (336) 334-5440.