Warning: include(/home/faculty/schahczenski/webSites_Common/contact.php): failed to open stream: No such file or directory in /opt/www/classes/csci438/csci438.php on line 9
Warning: include(): Failed opening '/home/faculty/schahczenski/webSites_Common/contact.php' for inclusion (include_path='.:/usr/share/php') in /opt/www/classes/csci438/csci438.php on line 9
Office Hours:
Warning: include(/home/faculty/schahczenski/webSites_Common/officeHours_spring.php): failed to open stream: No such file or directory in /opt/www/classes/csci438/csci438.php on line 15
Warning: include(): Failed opening '/home/faculty/schahczenski/webSites_Common/officeHours_spring.php' for inclusion (include_path='.:/usr/share/php') in /opt/www/classes/csci438/csci438.php on line 15
Text: Introduction to the Theory of Computation , 3rd edition, by Michael Sipser
Prerequisite: CSCI 305, Programming Languages
Meeting times and place: MWF 2:00-2:50pm, MUS 205
What is in this course?
This course gives you a chance to stand back and look abstractly at computers and what it means to be computable. You'll study the most general computing machine, the Turing Machine, which appears powerful enough to serve as the basis for defining computability. You'll see that some questions are not computable by any computing machine. For example, no machine can be developed that determines the truth or falsity of all mathematical statements. Similarly, no machine can be developed to determine if a given program halts on a given input.
You'll study two classes of machines that are less powerful than the Turing Machine: finite automata and push down automata. These machines are useful for pattern matching and parsing languages, respectively.
You'll review the classes P and NP and learn a new way to define these in terms of Turing Machines.
Grading
| Activity | Percentage | Elaboration |
|---|---|---|
| Exams | There will be 3 exams during the semester and a final exam at the end. These exams will be weighted equally. The final exam will not be significantly longer than the other exams, but you will have more time to complete the final exam. | |
| Quizzes | A few quizzes will be given early in the semester, before the first exam. These quizzes give me a chance to give you indiviual feedback and for you to see how well you are learning the material. | |
Expectations:
A general guideline is that for every one-hour of in-class lecture you do two hours of outside work.
In my experience, some students pickup this material easily, while others struggle. Therefore,
some students take 30 minutes to read the text and complete the homework problems, while others
spend over two hours, going back and forth between reading the text and working the problems.
Still, these students are sometimes not confident about their answers to some homework problems.
I suggest that each of you set aside a regular time to work on this course after each lecture.
For some of you this will be 30 minutes, for others 2 or more hours.
Warning - this course moves fast and you don't want to fall behind.
Exams:
Each exam will have two parts: a definition portion and a problem solving portion. While most of this course is focused on problem solving, it is difficult to solve a problem unless you know the language in which to reason. I don't see memorizing the definitions used in this course as useless information that ordinarily, you will simply look up. I see these definitions as the building blocks and concepts, necessary for reasoning about computation.
Some exams will include an essay portion which can be completed before the exam period.
Homework:
The concepts in this course build on each other. For this reason it is important that you keep up with the material. Not understanding one topic will make the next topic harder to learn. Homework solidifies your understanding of the material. Therefore, assignments will be given most class periods. Assignments will be problems which I bring to class. In some cases, you will be able to finish these in class. In most cases these will be homework problems. You are to complete the exercises by the next class period. Once again, completion of the previous material homework will make learning the new material easier.
Doing the homework conscientiously will help you master the material. Writing out your solutions carefully, even if you think that the work is wrong, enables you to learn from your mistakes. Sometimes going down a wrong path turns out to be very instructive. Mistakes can be a valuable window into your thinking process, enabling you to make corrections when necessary. Homework solutions will be posted on the class web site. While homework will not be collected, I will be happy to go over any assigned problems. I am also happy to grade any problems which you ask me to grade.
Quizzes:
A few quizzes will be given early in the semester, before the first exam. These quizzes provide a chance for me to give you individual feedback and for you to get a sense of how well you are learning the material.
Extra Credit Presentations:
Outside material which is related to the course and which you find interesting, may be interesting to other students and me as well. You are invited to share such material with the class in one or more mini-presentations. You can earn a maximum of 5% extra credit points, added to your overall exam score for a maximum of 100%, from these mini-presentations. Please tell me in advance if you have a mini-presentation which you would like to give. Mini-presentation topics must be approved by me by March 25th and the mini-presentation must be completed by April 11th.
COVID 19:
Classes are face-to-face. If, due to COVID, you cannot attend a class, let me know in advance and I will zoom the class. If you will not be able to attend the zoom session, also let me know in advance. I will record the zoom session and send the recording to you.
If, due to COVID you are forced to take an exam or quiz outside the classroom, you must have a camera (so I can proctor you taking the exam), a printer (so you can print the exam or quiz) and a scanner (so you can scan your work and send it to my email). In some cases, taking a picture and sending it to me, is an alternative to scanning, but only if you and I have practiced, and it is clear to me that your pictures will not be too onerous to work with.
Catalog description of the course:
Students will look abstractly at computers and what it means to be computable. Turing Machines, which appear to be powerful enough to serve as the basis for defining computability, will be studied and students will learn that some questions are not computable by any computing machine. Regular and context-free languages will also be studied. Prerequisite: CSCI 305. (2nd)
See catalog online, spring semester of senior year, in Computer Science, B.S. Program.
Expected skills students have coming into the course:
- E1. Students have a working knowledge of elementary set theory and mathematical structures such as relations, functions, and graphs and are able to apply this knowledge towards solving algorithmic problems. (CSCI 246)
- E2. Students are able to use inference and to develop direct and inductive proofs, proofs by construction, and proofs by contradiction. (CSCI 246)
- E3. Students can identify and understand why some problems cannot be solved efficiently (NP problems). (CSCI 332)
- E4. Students recognize regular languages, know situations where regular languages are useful, and are able to define regular languages using finite automaton (deterministic and non-deterministic), grammars and regular expressions. (CSCI 305)
- E5. Students recognize context free languages, know situations where context free languages are useful, and are able to define context free languages using push down automaton and grammars. (CSCI 305)
Expected outcomes from taking this course:
- R1. Students can translate between the regular language formalisms (deterministic finite automaton, non-deterministic finite automaton, regular grammars and regular expressions) and can show that a language is not regular using a pumping lemma argument. (CS 1, CS 6)
- R2. Students can translate between push-down automaton and context-free grammars and can show that a language is not context free using a pumping lemma argument. (CS 1, CS 6)
- R3. Students understand the concept of a Turing Machine, and know several variations on Turing Machines that are all equivalent. (CS 1, CS 6)
- R4. Students know that Turing Machines can be used to define computability and that all other sufficiently complex models of computation are equivalent to Turing Machines (Church-Turing Thesis). (CS 1, CS 6)
- R5. Students know examples of problems that are undecidable by any Turing Machine. (CS 1)
- R6. Students understand the complexity classes P, NP and NP-complete and can prove membership within these classes. (CS , CS 6)
Related student outcomes:
- CS 1 An ability to analyze a complex computing problem and to apply principles of computing and other relevant disciplines to identify solutions
- CS 6 An ability to apply computer science theory and software development fundamentals to produce computing-based solutions