CSCI 380 - Theory of Computing

Location

WAC 249 (2nd floor)

Time

TR 2:45 - 4:00
Fall 2019

Instructor

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

Covers basic topics in automata, computability, and complexity theory, including: models of computation (finite automata, Turing machines and RAMs); regular sets and expressions; recursive, r.e., and non-r.e. 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.

Prerequisites: MATH 240.

By the end of this course, you should be able to:

• describe the relationship between formal languages and machines that can recognize them;
• describe the hierarchy of finite automaton, stack machines, and Turing machines;
• state the definitions of the primary concepts of the course, such as decidability, intractability, determinism, computability, recursive enumerability, and the Church-Turing thesis;
• understand the difference between decidable and undecidable problems;
• apply reducibility techniques to classify problems;
• classify a given decidable problem as belonging to P, NP, NP-complete, or exponential time complexity classes;
• work together to teach each other course material;
• present a clear, concise solution to a problem in written form;
• present a clear, concise solution to a problem or summary of a topic orally.

An Introduction to Formal Languages and Automata
by Peter Linz, 2016
ISBN: 978-1284077247
Find this book at Amazon
RECOMMENDED ONLY

JFLAP V7.1

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.

I have organized our course topics using a Gantt Chart to help you see the timeline of activities and the relationships between topics. This website also provides a calendar view of these topics to help you organize your schedule this semester.

There will be three methods used to reinforce your mastery of the course material: 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.

You will have many, many individual homework problems in this course, with problems assigned every week. Individual questions must be completed and submitted individually. You are required to complete all individual sections. Each problem will be graded as correct or incorrect. Late work will be accepted up to the last day of class, with a 50% grade penalty.

All homeworks must be written using LaTeX and turned in as a PDF on Moodle. There are many resources available for LaTeX on the web, including the LaTeX Math Symbols, Detexify, and a WikiBook on LaTeX.

I recommend using Overleaf to create your documents, it is an online implementation of LaTeX that allows for collaboration.

Here is a great template LaTeX file for homework assignments.

• HW1 - Problems
  
• HW2 - Problems
  
• HW3 - Problems
  
• HW4 - Problems
  
• HW5 - Problems
  
• HW6 - Problems
  
• HW7 - Problems
  
• HW8 - Problems
  
• HW9 - Problems
  
• HW10 - Problems
  

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.

You will be rotating through assigned groups for your homeworks over the course of the semester, working on problems that will lead to classroom presentations. 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 LaTeX and turned in as a PDF on Moodle by at least one member of the group.

For each question, one member of your group will be randomly chosen to present your group's work in class. This presenter must also be prepared to answer questions first from members of the other groups and then from the instructor.

Presentation points will be awarded as follows:

• +3 points: Awarded to all members of the group if the presenter is successful on the first attempt. If there are major errors in the written answer, the accuracy of the answer, or the oral presentation skills, the question will be remanded to the group. Within one week, in future class sessions, this original presenter must ask to present their question again.
• +2 points: Awarded to all members of the group if the presenter is successful after the second presentation. If there are further concerns, the question will be once again remanded to the group, and can be presented one more final time within one week.
• +1 point: Awarded to all members of the group if the presenter is successful after the third presentation. If there are further concerns after this, the question will earn no points.

Points will be deducted using the following rules:

• -0.5 points: Deducted from all members if the presentation is successful, but there are minor errors in the written answer, the accuracy of the answer, or the oral presentation skills.
• -1 point: Deducted from all members if an absent group member without a valid excuse is randomly chosen to present. Another group member will then be randomly selected.
• -All points: Deducted individually for any group member that is absent from class without a valid excuse when a group is awarded points.

In addition to group presentation points, +4 points per individual per day will also be awarded for asking insightful questions of presentations of other groups.

Your total points accumulated through group presentations and asked questions are converted to a grade using the following scale:

Therefore, to earn the maximum number of points, you are responsible for ensuring that all group members are prepared to accurately present all questions assigned to your group, and that you engage other groups through insightful questions and constructive feedback.

First Grouping

1. Hawkins, Nsabimana, Sanders, West
2. Pinter, Samore, Thomas

Second Grouping

1. Hawkins, Nsabimana, Samore, Thomas
2. Pinter, Sanders, West

Third Grouping

1. Hawkins, Pinter, Samore, Sanders
2. Nsabimana, Thomas, West

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

• Exam 1: 10% - Due September 23
• Exam 2: 15% - Due November 5 at 2:30pm
• Final: 25% - Due Final Exam period December 12

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.

You may miss three TR or four MWF non-presentation days with no penalty. These can be for sports travel, school sanctioned activities, sickness, mental wellness, etc. You are expected to make up any work you miss through these absences.

Every subsequent absence will result in a 4% penalty on your final grade.

If your schedule for the semester will necessarily involve missing more than four days of class, please talk to me very early in the semester so we can develop a gameplan together.

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.

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.

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.