Turing machines and other models of computability such as M-5-recursive functions and random-access machines. Undecidability. Recursive and recursively enumerable sets. Church-Turing thesis. Resource-bounded complexity. Complexity comparisons among computational models. Reductions. Complete problems for complexity classes.
The course will cover topics from Parts 2 and 3 of the textbook. This outline is subject to change.
References to the textbook are given simply as section numbers. References to secondary sources are given as section numbers preceded by:
There will be 5 assignments. Assignments are to be done individually. Assignments are to be handed in at the beginning of class in class on the due date. Late assignments will not be accepted. If you are unable to finish the assignment, please discuss the matter with me before the assignment is due, as soon as possible. If approved, the weight of the assignment will be transferred to the following exam (midterm or final).
The midterm will be held on Thursday February 16, in class. It will cover everything on computability theory (Chapters 3 to 5).
This is a closed-book test. You may bring one (1) standard letter size (8.5" x 11") sheet of notes and use it during the test.
The final will be held on Monday April 17 at 9:00 am in Goodwin 247. You will have 3 hours to complete the final. It will cover topics in complexity theory (Chapters 7 to 10).
This is a closed-book test. You may bring one (1) standard letter size (8.5" x 11") sheet of notes and use it during the test.
Academic Integrity is constituted by the five core fundamental values of honesty, trust, fairness, respect and responsibility (see www.academicintegrity.org). These values are central to the building, nurturing and sustaining of an academic community in which all members of the community will thrive. Adherence to the values expressed through academic integrity forms a foundation for the "freedom of inquiry and exchange of ideas" essential to the intellectual life of the University (see the Senate Report on Principles and Priorities).
Students are responsible for familiarizing themselves with the regulations concerning academic integrity and for ensuring that their assignments conform to the principles of academic integrity. Information on academic integrity is available in the Arts and Science Calendar (see Academic Regulation 1), on the Arts and Science website, and from the instructor of this course. Departures from academic integrity include plagiarism, use of unauthorized materials, facilitation, forgery and falsification, and are antithetical to the development of an academic community at Queen's. Given the seriousness of these matters, actions which contravene the regulation on academic integrity carry sanctions that can range from a warning or the loss of grades on an assignment to the failure of a course to a requirement to withdraw from the university.
Queen's University is committed to achieving full accessibility for persons with disabilities. Part of this commitment includes arranging academic accommodations for students with disabilities to ensure they have an equitable opportunity to participate in all of their academic activities. If you are a student with a disability and think you may need accommodations, you are strongly encouraged to contact Student Wellness Services (SWS) and register as early as possible. For more information, including important deadlines, please visit the Student Wellness website at: http://www.queensu.ca/studentwellness/accessibility-services/.