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-xxxx [old number] | |
| 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, 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.
Assignments 35 points Midterm Exams (2) 40 points Final Exam 25 points
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,9 Finite Automata and Regular Languages Chapter 1 Sep 11,16 Context-Free Languages and Pushdown Automata Chapter 2 Sep 18,23 Turing Machines and the Church-Turing Thesis Chapter 3 Sep 25,30 Decidability Chapter 4 Oct 2 Catch-up and review Oct 7 Test 1 Oct 9,14 Reducibility Chapter 5 Oct 16,23 Time complexity, P, and NP Sections 7.1-7.3 Oct 28,30 NP-completeness Sections 7.4-7.5 Nov 4 Catch-up and review Nov 6 Test 2 Nov 11,13 Space complexity Chapter 8 Nov 18 Randomization Section 10.2 Nov 20 Interactive Proofs Section 10.4 Nov 25 Parallel Complexity Section 10.5 Dec 2 Quantum Computing Handout Dec 4 Final 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.