CSE 303: Introduction to the Theory of Computation (Spring 2021)
Also: CSE 587: Proficiency Requirement in Computer Science (Spring 2021)
1 Class Meetings
- When: Tuesdays & Thursdays, 3 PM to 4:20 PM
- Where: ONLINE (Check Blackboard for a link to every ONLINE meeting)
- Instructor: Omkant Pandey, omkant [at] cs stonybrook edu
- Office hours: TuTh 4:30 PM to 6:00 PM, held ONLINE
- Teaching Assistant(s):
- Zhi Chai, zhchai [at] cs stonybrook edu, Office hours: MW: 11AM to 12:30PM
- Grading Assistant(s):
- Gowtham Kumar Karanam, email@example.com
- Aakarsh Duvvuru, firstname.lastname@example.org
- Lu Chen, email@example.com
- Announcements: All announcements and latest information is on Blackboard.
2 Course Description
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 Course Learning Outcomes
At the end of this course, the students should have an understanding of different models of computation, their strengths and limitations, as well as why some problems cannot be solved by a computer. The students should have the ability to argue about the the correctness and complexity of a computational algorithm as well as perform reductions between different computational problems.
4 Prerequisites C or higher: CSE 215/150 or CSE 214/160
Introduction to the Theory of Computation, 3rd edition, by Michael Sipser
The grading will be based on the following examinations and assignments:
Note the following:
- Final Exam: 30%
- Midterm Exams: 2 x 15% = 30%
- Homework Assignments: 4 x 10% = 40%.
- Students will have exactly one week to review their graded answer sheets following the release of scores for each assignment/exam. The scores will be final after this week and no further reviews will be entertained.
- Exams are open book and open notes. However, access to electronic notes or resources will NOT be permitted during the exams. No make-up exams or assignments will be provided except when mandated by university regulations.
- Homework assignments must be completed in LaTeX, and submitted on time. Students will be responsible for learning LaTeX on their own. Late submissions will not be accepted.
- Students must complete their work independently. Offering or accepting solutions from others is an act of plagiarism, which is a serious offense. All parties involved in academically dishonest behavior will be penalized according to the Academic Integrity Policy provided below.
7 Tentative Examination Dates and Times:
- Midterm Exam 1: Tuesday, March 16, 3:00 PM to 4:20 PM, in class.
- Midterm Exam 2: Tuesday, April 27, 3:00 PM to 4:20 PM, in class.
- Final Exam: Tuesday, May 11, 2:15 PM to 5:00 PM, in class. (See official schedule.)
8 Tentative Class Schedule
||Finite automata, non-determinism, regular languages, pumping lemma. [Chap. 0--1]
|| HW1 due
||Context-free languages, grammars, pushdown automata [Chap. 2]
|| HW2 due
||Turing machines, decidability, reductions, computability [Chap. 3--5]
|| HW3 due + Midterm 1
||Complexity theory, NP Completeness [Chap. 7]
|| HW4 due + Midterm 2
||Selected Advanced Topics [Chap. 6--10]
9 Student Accessibility Support Center Statement
If you have a physical, psychological, medical, or learning disability that may impact your course work, please contact the Student Accessibility Support Center, 128 ECC Building, (631) 632-6748, or via e-mail at: firstname.lastname@example.org. They will determine with you what accommodations are necessary and appropriate. All information and documentation is confidential.
10 Academic Integrity Statement
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 http://www.stonybrook.edu/commcms/academic_integrity/index.html
11 Critical Incident Management
Stony Brook University expects students to respect the rights, privileges, and property of other people. Faculty are required to report to the Office of University 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.
12 Reasonable Accommodation
Students are expected to attend every class, report for examinations and submit major graded coursework as scheduled. If a student is unable to attend lecture(s), report for any exams or complete major graded coursework as scheduled due to extenuating circumstances, the student must contact the instructor as soon as possible. Students may be requested to provide documentation to support their absence and/or may be referred to the Student Support Team for assistance. Students will be provided reasonable accommodations for missed exams, assignments or projects due to significant illness, tragedy or other personal emergencies. In the instance of missed lectures or labs, the student is responsible for seeking notes from a classmate or an identified class note taker. Please note, all students must follow Stony Brook, local, state and Centers for Disease Control and Prevention (CDC) guidelines to reduce the risk of transmission of COVID. For questions or more information click here.