CISC 3230 [CIS 38]   Theoretical Computer Science

Fall 2016   May still be updated.

Prof. Eva Cogan    cogan_at_sci.brooklyn.cuny.edu     Replace _at_ with @.
http://www.sci.brooklyn.cuny.edu/~cogan/
Office: 2112N (718)951-5000 X2046

Prerequisites (Chap 0 of text)

• CISC 2210 (CIS 11)
• Recursion
• Sets
• Sequences
• Functions and relations
• Graphs
• Strings and languages
• Boolean logic
• Definitions
• Theorems
• Proofs

Text

Introduction to the Theory of Computation (2^nd edition)  by Michael Sipser.

It is assumed that you will do the reading without being told. Order may vary. Other topics may be covered. Some topics may be omitted.

           Chap 0: Sec 1-3, Induction   Review of previous courses. You must read this on your own. Do I have to test this to make you read it?

          Chap 1: Sec 1-4

          Chap 2: Sec 1,2 (,3)

          Chap 3: Sec 1,2,(3)

          Chap 4: Sec  1,2

          Chap 5: Sec  1

          Chap 7: Sec 1-5

Other resources

• Martin Davis, Ron Sigal, Elaine J. Weyuker; Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science.
• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman; Introduction to Automata Theory, Languages, and Computation.
• Harry R. Lewis, Christos H. Papadimitriou; Elements of the Theory of Computation.
• Christos H. Papadimitriou;  Computational Complexity
• Many online sites with notes, slides, videos, tutorials, etc. Please share with class list when you find good ones

•   ….     
•  ….

Performance Objectives

Student will be able to:

1. Understand and design deterministic and non-deterministic finite state automata as well as regular expressions.
2. Design simple context-free grammars and push-down automata.
3. Design simple Turing machines and understand its relationship with real-world computers.
4. Understand the limits of computation via the halting problem and other problems.
5. Understand the basic concepts reducibility of problems and the main ideas of computational complexity.

Grade

• 16% homework and quizzes, to be adjusted as needed
• 24% Exam1 24% Exam2
• 36% Cumulative Final
• No makeup exams.  Please tell me immediately if there is any day on which you cannot take an exam.
• There will be homework every class. Make sure you have the time to do it. Some exam questions may be similar to the homework.
• This class requires a lot of homework and study time. Schedule it.
• Read the book. Get the notes and assignments from someone if you miss a class. The material “builds” on itself.
• Class participation may change your grade by up to 10%.

Homework 0

Subscribe to the class list

Exchange phone numbers or e-mail addresses with a classmate.

Academic Integrity

Any attempt to cheat is grounds for failure.

http://www1.cuny.edu/portal_ur/content/2004/policies/policies.html
The CUNY Policy and the Report of the Committee on Academic Integrity

The faculty and administration of Brooklyn College support an environment free from cheating and plagiarism. Each student is responsible for being aware of what constitutes cheating and plagiarism and for avoiding both. The complete text of the CUNY Academic Integrity Policy and the Brooklyn College procedure for implementing that policy can be found at this site: http://www.brooklyn.cuny.edu/bc/policies. If a faculty member suspects a violation of academic integrity and, upon investigation, confirms that violation, or if the student admits the violation, the faculty member MUST report the violation.

Center for Student Disability Services

In order to receive disability-related academic accommodations students must first be registered with the Center for Student Disability Services. Students who have a documented disability or suspect they may have a disability are invited to set up an appointment with the Director of the Center for Student Disability Services at 718-951-5538. If you have already registered with the Center for Student Disability Services please provide your professor with the course accommodation form and discuss your specific accommodation with him/her.

Religious Onservance

The state law regarding non-attendance because of religious beliefs is on p. 64 in the Undergraduate Bulletin or p. 40 of the Graduate Bulletin. Tell me now if there is any day you cannot attend.

Wednesday, August 31 Last day to add a course
Last day to file for elective course Pass/Fail
Wednesday, September 14 Last day to drop a course without a grade
Thursday, September 15 Last day to apply for Fall 2016 Graduation
Thursday, October 6 Conversion Day; Classes follow a Monday Schedule
Friday, October 14 Conversion Day; Classes follow a Tuesday Schedule
Wednesday, November 9 Last day to resolve Spring and Summer 2016 incomplete grade (INC)
Thursday, November 10 Last day to withdraw from a course with a W (non-penalty) grade