An introduction to the abstract notions encountered in machine computation. Topics include finite automata, regular expressions, and formal languages, with emphasis on regular and context-free grammars. Questions relating to what can and cannot be done by machines are covered by considering various models of computation, including Turing machines, recursive functions, and universal machines. (3 credits)
The following are the official course goals agreed upon by the faculty for this course.
An ability to define and use abstract models of computation such as finite and push-down automata, and analyze their relative expressive power.
An ability to define, use, and convert between abstract machine models and formal languages.
An ability to apply abstract models of computation to analyze the power and inherent limitations of algorithms.
To submit homework assignments, students will need to have access to facilities that will enable them to typeset or or scan their homework submissions, convert them to PDF, and upload them to Brightspace. For attending office hours, students will need to have a computer that satisfies the minimum requirements for the Zoom videoconferencing application, including a working webcam and microphone, and access to reliable high-speed internet service.
Note: All office hours held by Prof. Stark will take place online via Zoom. Zoom links for attending office hours are published via the Google Calendar that appears on the course home page. Barring unforeseen technical difficulties, the same link will be valid for the entire semester. Outside of office hours, the best way to contact Prof. Stark is by email. Any TA office hours and locations will be announced once the semester has started.
You must be an official CSE major and have achieved a grade of C or higher in one of CSE 214 or CSE 160 and in one of CSE 215 or CSE 150 to take this course.
Monday and Wednesday, 2:30PM-3:50PM, in Javits 110.
There will be two midterm exams, held during regular class time on dates to be announced, and a cumulative final exam, held during Finals Week at the officially scheduled time: Wednesday, May 15, 2:15PM - 4:45PM and at the officially scheduled location, which will be published later by the Registrar. You must take the exams at the scheduled times -- no make up exams will be given, except for {\bf prior} excused absences with official documentation approved by the University.
Michael Sipser,
Introduction to the Theory of Computation,
(3rd edition: June 27, 2012)
Cengage Learning
Ding-Zhu Du and Ker-I Ko,
Problem Solving in Automata, Languages, and Complexity,
(1st edition: September 15, 2002)
Wiley-Interscience
Harry R. Lewis and Christos H. Papadimitriou,
Elements of the Theory of Computation,
(2nd edition: August 7, 1997)
Prentice-Hall
This semester, all course handouts, including homework assignments, will be available on the Web for you to download and print, if desired. No paper copies will be handed out. It is assumed that you know how to use a Web browser and have regular access to the Internet. Homework assignments will be posted and submissions made on Brightspace:
https://mycourses.stonybrook.edu/d2l/home/1135584
.
There will be homework assigned regularly (probably weekly). Homeworks will consist of problem sets drawn from the textbook and other sources. Homeworks are either to be typeset or written neatly and scanned, then submitted via Brightspace (PDF only, please). The homeworks must be submitted by the specified due date; late homeworks will not be accepted. The level of grading will depend on available teaching assistant support. Regardless of the grading, in a mathematical course like this one, doing problems will be very important to help you learn the material. Homework solutions are to be your own work; you are expected to attempt to solve the problems yourself using your own brain. Looking up and copying answers from the Internet or someone else is not permitted and will not help you.
The final grade will be determined as follows: The raw scores obtained by a student on each assignment and exam will be standardized for that particular assignment or exam, either by converting them to percentile scores, or else by applying a linear transformation to map the scores to a standard [0, 100] scale. A weighted sum of the resulting standardized scores will then be formed (with weights as shown below) to obtain a composite score for each student.
Finally, the composite scores will be ranked, and I will apply a subjective method of my choice to determine the cutoffs for each grade category. Absolute performance standards, the distribution of composite scores, and information derived from late homeworks are factors likely to contribute to this decision.
The Pass/No Credit (P/NC) option is not available for this course.
This policy applies to all CSE/ISE undergraduate courses used to satisfy the graduation requirements for the major.
The following statement about academic dishonesty, is required to be included in syllabi for all undergraduate courses:
"Each student must pursue his or her academic goals honestly and be personally accountable for all submitted work. Representing another person's work as your own is always wrong. Faculty is required to report any suspected instances of academic dishonesty to the Academic Judiciary. Faculty in the Health Sciences Center (School of Health Technology \& Management, Nursing, Social Welfare, Dental Medicine) and School of Medicine are required to follow their school-specific procedures. For more comprehensive information on academic integrity, including categories of academic dishonesty please refer to the academic judiciary website at the academic judiciary website."
Be advised that any evidence of academic dishonesty will be treated with utmost seriousness. Those involved will be prosecuted to the fullest extent permitted by the University and College policies.
If you have a physical, psychological, medical, or learning disability that may impact your course work, please contact the Student Accessibility Support Center, Stony Brook Union Suite 107, (631) 632-6748, or at sasc@stonybrook.edu. They will determine with you what accommodations are necessary and appropriate. All information and documentation is confidential.
https://www.stonybrook.edu/commcms/studentaffairs/sasc/Students who require assistance during emergency evacuation are encouraged to discuss their needs with their professors and the Student Accessibility Support Center. For procedures and information go to this website and search Fire Safety and Evacuation and Disabilities.
"Stony Brook University expects students to respect the rights, privileges, and property of other people. Faculty are required to report to the Office of Student Conduct and Community Standards any disruptive behavior that interrupts their ability to teach, compromises the safety of the learning environment, or inhibits students' ability to learn. Faculty in the HSC Schools and the School of Medicine are required to follow their school-specific procedures. Further information about most academic matters can be found in the Undergraduate Bulletin, the Undergraduate Class Schedule, and the Faculty-Employee Handbook."