CS 475 - Computation Theory
Introduces computational formalisms including: Automata, Lambda Calculus, Turning Machines, Recursive Functions, and emerging models. Explores the relation of formal languages and computation. Studies theoretical and pragmatic limits on computation including halting, NP-Completeness, P-Space, and Reducibility.
CS 324 and CS 390
This course focuses on nature of computation with the primary objective of understanding "what it means to be effectively calculable". Various formal models of computation are introduced throughout the course with the objective of understanding the computational capabilities and limitations of each model. The relation among these computational models and formal languages is also examined throughout this course. Finally, the course also examines how computation theory informs computing practice in the "real-world".
Upon completion of this course, learners should be able to:
Sipser, M., (2013). Introduction to the theory of computation (3rd ed.). Boston, MA: Cengage Learning.
CC&IS Faculty developed Faculty Notes (available by Topic in the Regis Worldclass online shell).
Sign on to Regis WorldClass and become familiar with the course shell navigation. The online content for CS475 is use in both classroom and online versions of this course. Complete the Course Overview and Topic 1 Reading Assignments.
Specific due dates for classroom sections of this course will be assigned by the faculty, but generally adhere to the following schedule.
| Weekly Format* |
Topics | Readings** | Assessed Assignments*** | |
|---|---|---|---|---|
| 15 | 8 | R: Online Faculty Notes, S: Sipser | (% course grade) | |
| 1 | 1 | 1: Foundations 2: Formal Languages 3: Finite State Automata & Regular Languages |
R: Topic 1, , S: Chpt. 0 S: Sec. 0.2, R: Topic 2 S: Chpt. 1, R: Topic 3 |
Topic 1 (assessed exams only) Topic 2 (assessed exams only) Participation (0.5%) |
| 2 | 1 | - continued - | Topic 3 Assignment (9%) Participation (0.5%) |
|
| 3 | 2 | 4: Pushdown Automata & Context-Free Langauges |
S: Chpt. 2 (pp. 101-135), R: Topic 4a | Participation (0.5 %) |
| 4 | 2 | Determinisitic PDAs | S: Chpt. 2 (pp. 135 - 162), R: Topic 4b | Topic 4 Assignment (9%) Participation (0.5%) |
| 5 | 3 | 5: Turing Machines & Recursively Enumerable Languages |
S: Chpt. 3, R: Topic 5 | Participation (0.5%) |
| 6 | 3 | 6: Linear Bounded Automata & Context-Sensitive Languages |
Topic 5 Assignment (9%) Topic 6 (assessed exams only) Participation (0.5 % ) |
|
| 7 | 4 | 7: Decidability | S: Chpt. 4, R: Topic 6 | Topic 7 (assessed exams only) Participation (0.5%) |
| 8 | 4 | 8: Reducibility | S: Chpt. 5, R: Topic 7 | Topic 8 (assessed in exams) Participation (0.5%) Midterm Exam (16%) |
| 9 | 5 | 9: Recursive Function Theory |
R: Topic 9 |
Participation (0.5%) |
| 10 | 5 | - continued - | Topic 9 Assignment (9%) Participation (0.5%) |
|
| 11 | 6 | 10: Lambda Calculus | R: Topic 10 | Participation (0.5%) |
| 12 | 6 | - continued - | Topic 10 Assignment (9%) Participation (0.5%) |
|
| 13 | 7 | 11: Complexity Theory - Time Complexity - |
S: Chpt. 7, R: Topic 11, Part I | Participation (0.5%) |
| 14 | 7 | - continued - | Topic 11 Assignment (9%) Participation (0.5%) |
|
| 15 | 8 | - Space Complexity - | S: Chpt 8, Sect. 9.1-9.2, R: Topic 11, Part II | Participation (1.0% course) Final Exam (22%) |
* Semester 15-Week course sections use column one; Accelerated 8-Week sections use column two
** Complete reading assignments in the order listed (left-to-right).
*** Unless your faculty directs otherwise, individual assessed assignments are found in the online course shell in each Topic.
| Assignments | Weighted Percentage |
|---|---|
| Topic Assignments | 54% |
| Exams | 38% |
| Participation | 8% |
| TOTAL | 100 % |
All programs must be implemented in Java 8.2 using the NetBeans IDE. The programming assignments are designed to reinforce the material in the associated Topic and to give you more practice with programming.
Late assignments will be graded and then 5% will be deducted for each day the assignment is late, up to 5 days late. Therefore, any assignment turned in more than 5 days late will be given a grade of zero, and no feedback will be given. The exams will not be accepted late.
Review the CCIS Policies on the Regis University website.
The Computer Science department and faculty reserves the right to review all assessments in this course, at any time, and revise the assigned grade based on a reassessment of the material, which may include, for example, an oral examination of the student by the faculty or department.
Adding this course during the Drop/Add Period: If you add this course during the drop/add period, you are responsible for immediately notifying the instructor that you joined the course late. None of the course due dates will be extended for you. If a due date has already passed when you add the course, late points will be deducted.
Repeating the course: If you are repeating this course (due to a previous withdraw or low grade), you are responsible for immediately notifying the instructor. If any of the course assignments have not changed since last time you took the course, you may be required to complete alternate assignments.
Plagiarism: Plagiarism includes submitting any work obtained from any other person, publication, or any internet web source without appropriate citations. Any external help you receive or review must be cited and include the reasons you needed this external source and what you learned from it. All work submitted in CS475 must be your own!
NOTE TO LEARNERS: On occasion, the course facilitator may, at his or her discretion, alter the Learning Activities shown in this Syllabus. The alteration of Learning Activities may not, in any way, change the Learner Outcomes or the grading scale for this course as contained in this syllabus. Examples of circumstances that could justify alterations in Learning Activities could include number of learners in the course; compelling current events; special facilitator experience or expertise; or unanticipated disruptions to class session schedule.