CSCI 380
Theory of Computation

Time

MWF 9:10am - 10:00am

Location

MCREY 316

Instructor

Dr. Mark Goadrich
goadrich@hendrix.edu
(501) 450-1367
Office Hours


Overview

Covers basic topics in automata, computability, and complexity theory, including: models of computation (finite automata, Turing machines and RAMs); regular sets and expressions; recursive, recursively enumerable, and non-recursively enumerable sets and their basic closure properties; complexity classes; determinism vs. non-determinism, with and without resource bounds; reductions and completeness; practice with NP- and P-completeness proofs; and the complexity of optimization and approximation problems. Prerequisite: MATH 240

Learning Goals

Upon completing this course, our goal is for you to be able to:

Resources

Introduction to Formal Languages and Automata

Introduction to Formal Languages and Automata

Typst

Typst

JFLAP

JFLAP

We will be covering most of the recommended textbook following the format in the table of contents. We will also be using additional supplemental material such as relevant web-pages and background material. Additional readings will be assigned before material will be covered in class. You are expected to review the material and come to class prepared.

Schedule

This is where you will find all of your assignment due dates.

Checkins

Three times throughout the semester, you will be expected to check in for detailed feedback on your individual and group homework assignments and understanding. These should be scheduled via office hours with me in the week directly before each exam.

Coursework

There will be four methods used to reinforce your understanding of the course material: POGIL in-class activities, small individual worked problems which focus on the fundamentals, large group problems and presentations which focus on proof and abstraction, and exams which focus on transfer and application.

POGIL Activities

You will be rotating through assigned groups for your in-class activites and group presentations over the course of the semester. For these activities, you will begin by picking up the POGIL role cards, along with the activity worksheet for the day. You will then work with your assigned group to complete the tasks, to the best of your ability within the role assigned. It is important that you attend class so that you can earn POGIL participation credit. In the event of an excused absence, individual completion of the exercise is required. If you do not communicate with me before your absence, it will be unexcused unless in case of emergency. Unexcused absences cannot complete POGIL exercises.

# Activity
1 POGIL and Set Theory

Individual Homework

Individual homework will be assigned and due approximately once per week. The homework is excellent preparation for the three exams. This homework will be graded based on completion (i.e. turning in the homework will result in a Complete grade). If you would like extensive feedback or are struggling to complete these homework problems, please schedule an office hours appointment.

Group Presentations

Presentations will take place typically on Wednesdays. As you rotate through the Spokesperson POGIL role each week, you will also be tasked with presenting to the class on Wednesdays selections from the Group Homework for that week. The Spokesperson must also be prepared to answer questions first from members of the other groups and then from the instructor. The Spokesperson should not be reading directly from the written proof, but instead guiding the class through the main concepts.

The goal of these presentations is to work as a class and as a group to teach each other the concepts in theory of computation and to improve each other’s presentation skills. As above, all group problems must be written using Typst and turned in as a PDF on Teams by at least one member of the group.

Presentations will graded Complete if a solution is provided with only minor errors and questions can be answered reasonably. If there are questions unanswered, or major errors in the explanation or writeup, the presentation will be Partially Complete. Partially complete presentations can be revised and attempted again in a future class period.

Exams

There will be three take-home exams. These will cover material from the homeworks and group presentations.

Attendance

Attending class and being an active participant in the class community is one of the most important contributors to your learning at Hendrix. Attendance is especially important in this class since you will often engage in group learning activities. Active participation is expected in order to achieve higher grade levels in the course.

If you know that you will be absent, please email me so that we can find accomodations. If there is an emergency, please get in touch with me as soon as is possible once the emergency is resolved. I trust you to be honest with me about your reasons for the absence (I do not need details), and honest with yourself about if you truly need to be absent. If you do not communicate with me before your absence, it will be unexcused unless in case of emergency.

Grading Specifications

A Level Work

B Level Work

C Level Work

D Level Work

Commitments

It is my ultimate goal for this course, and my teaching, to develop your academic skills, advance your learning of computer science concepts, and support the liberal arts in general. To do so will require commitments from myself and from you toward meeting this goal.

Active Participation

I will be prepared and on time for class each day, ready to use class time to help you understand the course material. I will respectfully listen to, understand, and answer questions asked in class.

You are expected to attend class and actively participate in discussions every day, answering questions, asking questions, presenting material, etc. Your participation will be respectful of your classmates, both of their opinions and of their current point in their educational journey, as we each approach the material with different backgrounds and contexts.

Constructive Feedback

I will keep office hours and be available for outside appointments, and respond to emails within one business day (not including weekends). I will provide feedback on group presentations within one day. For exams, projects, and homeworks, I will provide graded feedback within two weeks.

You are encouraged to provide constructive comments for improving this course for furthering your learning throughout the semester. There will be an opportunity for anonymous course feedback at the end of the term, in which I hope you all participate. Through your feedback I can improve this course and others for future students.

Academic Integrity

I will abide by the above syllabus and grade your work fairly.

As stated in the Hendrix Academic Integrity Policy, all students have agreed to adhere to the following principles:

  • All students have an equal right to their opinions and to receive constructive criticism.
  • Students should positively engage the course material and encourage their classmates to do the same.
  • No students should gain an unfair advantage or violate their peers' commitment to honest work and genuine effort. It follows that any work that a student submits for class will be that student's own work. The amount of cooperation undertaken with other students, the consistency and accuracy of work, and the test-taking procedure should adhere to those guidelines that the instructor provides.
  • Members of the Hendrix community value and uphold academic integrity because we recognize that scholarly pursuits are aimed at increasing the shared body of knowledge and that the full disclosure of sources is the most effective way to ensure accountability to both ourselves and our colleagues.
More details of our departmental stance on integrity can be found in the Hendrix Computer Science Academic Integrity Policy

Learning Accomodation

I will make this classroom an open and inclusive environment, accommodating many different learning styles and perspectives.

Any student seeking accommodation in relation to a recognized disability should inform me at the beginning of the course. It is the policy of Hendrix College to accommodate students with disabilities, pursuant to federal and state law. Students should contact Julie Brown in the Office of Academic Success (505.2954; brownj@hendrix.edu) to begin the accommodation process.

Diversity and Inclusion

Hendrix College values a diverse learning environment as outlined in the College's Statement on Diversity. All members of this community are expected to contribute to a respectful, welcoming, and inclusive environment for every other member of the community. If you believe you have been the subject of discrimination please contact Dean Donna Eddleman at eddleman@hendrix.edu or 501-450-1222 or the Title IX Coordinator Jennifer Fulbright at titleix@hendrix.edu or 501-505-2901. For more information on Hendrix non-discrimination policies, visit hendrix.edu/nondiscrimination.

Physical and Mental Health

I am willing to work with you individually when life goes off the rails.

Coursework and college in general can become stressful and overwhelming, and your wellness can be impacted when you least expect it. You should participate in self-care and preventative measures, and be willing to find support when you need it.

  • The Office of Counseling Services welcomes all students to see a counselor in a private and safe environment regardless of their reasons for making an appointment. Counseling services are available to all Hendrix students at no cost.
  • Student Health Services provides free healthcare to Hendrix students. Services are provided by an Advanced Practice Registered Nurse (APRN) in collaboration with a local physician.

The Offices of Counseling Services and Student Health Services are located in the white house behind the Mills Center for Social Sciences at 1541 Washington Avenue. Your health is important, and I care more about your health and well-being than I do about this class!