Spring 2022 CS 321 syllabus

Course: CS 321 – Theory of Computation

Two fundamental rules

1.   You are responsible for knowing the contents of the syllabus and all of the information about the course provided on Canvas.

2.   You are responsible for knowing the contents of instructor announcements made on Canvas, which means that you should make sure you receive such announcements and that you check for new        ones at least once a day.

Response times

When you email your TA or myself, you should expect a response within 24 hours.  You should expect your assignments to usually be graded within four days of the due date.

OSU catalog course description, including pre-requisites/co-requisites

Survey of models of computation including finite automata, formal grammars, and Turing machines.

Prerequisites: CS 261 and (CS 225 or MTH 231).

A minimum grade of C is required in CS 261, CS 225 and MTH 231.

Course Learning Outcomes

At the completion of this course, students will be able to:

1.    Convert between finite automata, regular grammars, and regular expression representations of regular languages.

2.   Apply the pumping lemma for regular languages to determine if a language is regular.

3.    Convert between grammars and push-down automata for context-free languages.

4.    Determine if a language is regular or context-free.

5.    Demonstrate that a grammar is ambiguous.

6.   Translate a context-free grammar from one form to another.

7.    Produce simple programs for a Turing Machine

8.    Explain the concept of undecidability

9.    List examples of undecidable problems.

Course tools

•      Canvas is the course management software used for this course.

•     JFLAP is software that lets you construct automata and observe their behavior.

•      Ed Discussion is an asynchronous Q&A forum.

•     Teams is a synchronous discussion forum where the TAs will hold their office hours, and which is also for more casual conversation with fellow students.

More information about these tools is available on the "Tools you will need" page, in the "Start here" module in Canvas.

Coursework and Grading Policies

•     You may submit assignments and quizzes up to 48 hours late for half-credit, with the exception of assignments in module 10.  If you have extenuating circumstances, please contact me about them as early as possible.

•      All assignments are due at 11:59pm Pacific Time.  Be aware of what time zone Canvas is using to        display deadlines.  If it's not your local time zone, you can set it to be.  The Canvas phone app always displays times for the time zone the phone is in.  This is important to keep in mind if you will be          traveling.

•      At the end of the term, you’ll have the opportunity to resubmit one assignment for full credit.

•      If you disagree with a score on any coursework, contact your TA by email within one week of             receiving your grade. If you are dissatisfied with your TA's response (or if they neglect to respond at all), then you should contact me about it.

•     There is no extra credit.

•      I don't plan to “curve” the grades, but that's something I'll re-assess at the end of the term.

•      Makeup exams will only be given for exams excused in advance by the instructor.

•      Incompletes will be given very rarely. If you have been doing well in the course so far, but an               emergency comes up that prevents you from continuing according to schedule, let me know as soon

as you can.

Weights for Grading

Assignments          70%

Quizzes                   30%

Letter Grade Percentages

Reach Out for Success

University students encounter setbacks from time to time. If you encounter difficulties and

need assistance, it’s important to reach out. Consider discussing the situation with an instructor or academic advisor. Learn about resources that assist with wellness and academic success          atoregonstate.edu/ReachOut. If you are in immediate crisis, please contact the Crisis Text Line    by texting OREGON to 741-741 or call the National Suicide Prevention Lifeline at 1-800-273-        TALK (8255)

Statement Regarding Religious Accommodation

Oregon State University is required to provide reasonable accommodations for employee and student sincerely held religious beliefs.  It is incumbent on the student making the request to  make the faculty member aware of the request as soon as possible prior to the need for the    accommodation. See the Religious Accommodation Process for Students.

Guidelines for a Productive and Effective Online Classroom

(Adaptedfrom Dr. Susan Shaw, Oregon State University)

Students are expected to conduct themselves in the course (e.g., on discussion boards, email) in             compliance with the university’s regulations regarding civility. Civility is an essential ingredient for          academic discourse. All communications for this course should be conducted constructively, civilly, and respectfully. Differences in beliefs, opinions, and approaches are to be expected. In all you say and do    for this course, be professional. Please bring any communications you believe to be in violation of this   class policy to the attention of your instructor.

Active interaction with peers and your instructor is essential to success in this online course, paying particular attention to the following:

•     Unless indicated otherwise, please complete the readings and view other instructional materials for each week before participating in the discussion board.

•     Read your posts carefully before submitting them.

•     Be respectful of others and their opinions, valuing diversity in backgrounds, abilities, and experiences.

•     Challenging the ideas held by others is an integral aspect of critical thinking and the             academic process. Please word your responses carefully, and recognize that others are       expected to challenge your ideas. A positive atmosphere of healthy debate is encouraged.

Expectations for Student Conduct

Student conduct is governed by the university’s policies, as explained in the Student Conduct Code (https://beav.es/codeofconduct).

This program strives to prepare students for careers in computer science, which includes preparing         students to communicate professionally. Therefore, students in this class are expected to communicate in a professional manner in discussion forums, email messages and all communications for this course.   Critiques, disagreements, problems, or other topics of a sensitive nature can be addressed, but should   be addressed civilly and professionally. If a student's communications become unprofessional,                  disruptive, abusive, inflammatory, or if they otherwise obstruct the learning process of the class, the      instructor may restrict the student from participating in the electronic forums associated with the class  and notify Ecampus and the OSU Office of Student Conduct and Community Standards. Productive          learning communities and workplaces depend on civil, professional discourse. It is our hope that this      policy strengthens your learning community and prepares you for the professional workplace.

Establishing a Positive Community

It is important you feel safe and welcome in this course. If somebody is making discriminatory              comments against you, sexually harassing you, or excluding you in other ways, contact the instructor, your academic advisor, and/or report what happened at                                                                                  http://studentlife.oregonstate.edu/studentconduct/reporting so we can connect you with resources.

Technical Assistance

If you experience any errors or problems while in your online course, contact 24-7 Canvas            Support through the Help link within Canvas.  If you experience computer difficulties, need help downloading a browser or plug-in, or need assistance logging into a course, contact the IS            Service Desk for assistance.  You can call 541-737-8787 or visit the IS Service Desk online.

Academic Integrity

The Code of Student Conduct prohibits Academic Misconduct and defines it as:

Any action that misrepresents a student or group’s work, knowledge, or achievement, provides a potential or actual inequitable advantage, or compromises the integrity of the educational

process.

To support understanding of what can be included in this definition, the Code further classifies and describes examples of Academic Misconduct, including cheating, plagiarism, assisting and  others. See the Code of Student Conduct for details: https://beav.es/codeofconduct

You are expected to do your own work and demonstrate academic integrity in every aspect of     this course. Familiarize yourself with the standards set forth in the OSU Code of Student               Conduct Section 4.2. You must only access sources and resources authorized by the instructor.    You may not show your work to any other current or future students without the instructor's      authorization.  Violations of these expectations or the Code of Student Conduct will be reported to the Office of Student Conduct and Community Standards. If there is any question about           whether an act constitutes academic misconduct, it is your responsibility to seek clarification       and approval from the instructor prior to acting.

Academic Integrity DOs and DON’Ts

•    Do feel free to discuss course content with each other, including general discussion of homework assignments.

•    Do feel free to ask conceptual questions related to assignments on Piazza or the official course Slack.

•    Don’t post any quiz questions or answers in any form.

•    Don’t make your assignments publicly accessible, for example by posting them on Stack Overflow, Chegg, a public GitHub repository, etc.

•    Do feel free to share and compare your assignments with other students on Piazza or the official course Slack starting the Sunday after the assignment was due.

•    Don’t copy someone else’s work, whether someone else in the course, a previous

student in the course, or work you found somewhere online.   Remember that

plagiarism goes on your academic record.

Students with Disabilities

Accommodations for students with disabilities are determined and approved by Disability   Access Services (DAS). If you, as a student, believe you are eligible for accommodations but have not obtained approval please contact DAS immediately at 541-737-4098 or at

http://ds.oregonstate.edu. DAS notifies students and faculty members of approved academic accommodations and coordinates implementation of those accommodations. While not          required, students and faculty members are encouraged to discuss details of the                        implementation of individual accommodations.

Accommodations for students with disabilities are determined and approved by Disability Access              Services (DAS). If you, as a student, believe you are eligible for accommodations but have not obtained    approval, please contact DAS immediately at 541-737-4098 or at http://ds.oregonstate.edu. DAS notifies  students and faculty members of approved academic accommodations and coordinates implementation of those accommodations. While not required, students and faculty members are encouraged to discuss          details ofthe implementation of individual accommodations.

Accessibility of Course Materials

All materials used in this course are accessible. If you require accommodations please contact Disability Access Services (DAS).

Additionally, Canvas, the learning management system through which this course is offered, provides a vendor statement certifying how the platform is accessible to students with disabilities.

Ecampus Reach Out for Success

University students encounter setbacks from time to time. If you encounter difficulties and need            assistance, it’s important to reach out. Consider discussing the situation with an instructor or academic advisor. Learn about resources that assist with wellness and academic success.

Ecampus students are always encouraged to discuss issues that impact your academic success with the Ecampus Success Team. Email [email protected] to identify               strategies and resources that can support you in your educational goals.

•     For mental health:

Learn about counseling and psychological resources for Ecampus students. If you are in            immediate crisis, please contact the Crisis Text Line by texting OREGON to 741-741 or call the National Suicide Prevention Lifeline at 1-800-273-TALK (8255).

•     For financial hardship:

Any student whose academic performance is impacted due to financial stress or the inability to afford groceries, housing, and other necessities for any reason is urged to contact the Director  of Care for support (541-737-8748).

Academic Calendar

All students are subject to the registration and refund deadlines as stated in the Academic Calendar: https://registrar.oregonstate.edu/osu-academic-calendar.

Student Bill of Rights

OSU has twelve established student rights. They include due process in all university disciplinary processes, an equal opportunity to learn, and grading in accordance with the course syllabus: