This course covers the formal foundations of computability and complexity. We aim to answer fundamental questions about what problems can be solved and what problems cannot be solved, and what problems can be solved given our limited resources. Topics include: the Church-Turing thesis; variations of Turing Machines; decidability; the Halting Problem; reducibility; the Recursion Theorem; time and space complexity; intractability; NP-completeness; and Cook’s theorem. We will also discuss some unconventional computing models, such as optical computing and DNA computing.
The Spring 2021 offering of CSCI 4962 counts in the Theory and Algorithms concentration area for the B.S. in Computer Science.
The Spring 2021 offering of CSCI 6962 counts in the Theory depth area for MS and PhD students.
This class will be offered online in the spring. Lectures will be livestreamed and will also be recorded for offline vieweing.
In addition, on successful completion of CSCI 6962, a student is able to:
Introduction to the Theory of Computation, 3rd edition, by Michael Sipser
Homework will be assigned rougly every 2 weeks, and can be done in groups of two. There will not be any programming assignments.
You may discuss the homework problems with students outside of your group, but each group must write up their solutions independently.
You must type your homework solutions. You can include hand-drawn figures if applicable. Homework must be submitted through Gradescope in pdf format. If you are working with a partner, only submit one copy of your solutions and use the team feature in Gradescope to identify the team members.
Homework must be submitted by 11:59pm on the deadline. Every student will be allowed one late submission. A late submission can be submitted within three days of the homework deadline with no penalty. No other late homework will be accepted without an official Excused Absence Letter from RPI.There will be three exams. Each exam will be available for an 8-hour window on the exam date. You will have two hours to complete each exam. Your two hours must fall within the exam availability window.
You may use your notes, books, research papers, and online resources as references. You must write all solutions in your own words. Do not copy text from another source, even if you cite the source.
No collaboration is allowed. Do not discuss the course material or exam with anyone during the exam window. Do not post questions online about the course material or the exam during the exam window. Do not read exam-related questions or answers online while you are taking the exam.
All solutions must be typed. You may include figures where appropriate. Figures may be created digitally or may be hand-drawn (neatly).
Grades will be based on homework and exams. The grading breakdown is:
To fairly evaluate your class performance, I must be able to assess each student individually. SO, to pass the course, you must earn a passing grade on assignments completed individually. Individual assignments indluce the three exams and any homeworks that were done individually.
Academic Integrity Student-teacher relationships are built on trust. For example, students must trust that teachers have made appropriate decisions about the structure and content of the courses they teach, and teachers must trust that the assignments that students turn in are their own. Acts that violate this trust undermine the educational process. The Rensselaer Handbook of Student Rights and Responsibilities and The Graduate Student Supplement define various forms of Academic Dishonesty and you should make yourself familiar with these. In this class, all assignments that are turned in for a grade must represent the student’s own work. In cases where help was received, or teamwork was allowed, a notation on the assignment should indicate your collaboration. No collaboration is allowed on exams.
A violation of this policy will result in a penalty ranging from a 0 on the affected assignment to failing the course, depending on the severity of the offense. Violations of academic integrity may also be reported to the appropriate Dean (Dean of Students for undergraduate students or the Dean of Graduate Education for graduate students, respectively).
If you have any question concerning this policy before submitting an assignment, please ask for clarification. In addition, you can visit the following site for more information on our Academic Integrity Plicy: Students Rights, Responsibilities, and Judicial Affairs.
Rensselaer Polytechnic Institute strives to make all learning experiences as accessible as possible. If you anticipate or experience academic barriers based on a disability, please let me know immediately so that we can discuss your options. To establish reasonable accommodations, please register with The Office of Disability Services for Students. After registration, make arrangements with the Director of Disability Services as soon as possible to discuss your accommodations so that they may be implemented in a timely fashion. DSS contact information: dss@rpi.edu; +1-518-276-8197; 4226 Academy Hall.