MEDGAR EVERS COLLEGE of CUNY
Department of Physical, Environmental and Computer Sciences
Department Office, Carroll 417 - Phone 718-270-6453
“Time, Effort, Integrity”
Theoretical Computer Science (CS 300)
Course Syllabus - 4 class hours, 3 credits
Course Description: This course focuses on fundamental issues of Computer Science Theory. Here we discuss the relationship between Automata and Formal languages. Even though this is a theoretical course, the students will also gain certain rudimentary knowledge of compiler construction.
Prerequisite: CS 241 Discrete Structures.
Co-requisites: None
Required Textbook: Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, ISBN: 0-534-94728-X
Course Requirements: All students have the responsibility to arrive on time, attend class regularly, and to participate fully in the work of the course. Additionally, students are not to work on other materials in class. Assigned readings, problems should be completed before class.
Grading Procedure: The final grade will be determined objectively by using a weighted average of the following areas: chapter examinations, homework assignments, mid-term and the final examinations. Note that missed chapter examinations cannot be made-up. The lowest score from all chapter examinations will be dropped, before calculating the final average, provided all class examinations are taken.
Academic Requirements and Regulations: Students who officially withdraw from a course between the 4th through the 8th week receive a grade of W, which is not counted in computing the grade point average. Courses officially dropped after the 8th week of class will appear as a WF and count as an F grade. INC (Incomplete) or ABS (absent) grades will only be given to students who are passing the course.
Honor Code and Plagiarism: Students are required to sign and adhere to the departmental honor pledge. Check with the department for a copy of the pledge.
CUNY Proficiency Examination (CPE)
The CPE is a graduation requirement. All students between 45-60 credits are required to sit for and pass the CPE. You have only three chances to pass this examination. Each missed scheduled examination after the 45 credit mark counts as a failure. For more information about this requirement, contact the Medgar Evers College CPE Liaison.
CS 300
MEDGAR EVERS COLLEGE of CUNY
Department of Physical, Environmental and Computer Sciences
Theoretical Computer Science (CS 300)
Course Outline
This course focuses on fundamental issues of Computer Science Theory: automata and formal languages, computational complexity, and computability. Topics include finite state automata, regular languages, pushdown automata, context-free languages, Turing machines, computability, decidability, classes P and NP, and NP-complete problems.
Note: CS 300 is required for BS degree in Computer Science.
| WEEK # | TOPICS | CHAPTER |
| 1 - 2 | Review of Discrete Structures (CS 241) |
|
| 3 | INTRODUCTION |
0 |
| 4 - 6 | REGULAR LANGUAGES |
1 |
| 7 - 9 | CONTEXT-FREE LANGUAGES |
2 |
| 10 - 11 | CHURCH-TURING THESIS |
3 |
| 12 | DECIDABILITY |
4 |
| 13 - 14 | COMPLEXITY |
7.1 – 7.4; 9.1 |
| 15 | REVIEW |
