COSC 340

Theory of Computation


Syllabus

Please read this syllabus thoroughly!

Instructor

Dr. Beau M. Christ

Email: christbm@wofford.edu
Phone: (864) 597-4528
Office: Olin 204F
Office Hours: MWF from 1:00PM - 3:00PM and TR from 9:30AM - 11:00AM
Website: http://www.beauchrist.com

If you have any questions at all, feel free to contact me by email or phone, or stop by my office during office hours. You can also try to catch me at other times or make an appointment. I am always happy to talk!


Meeting Time & Location

We will meet every Monday, Wednesday, and Friday from 9:30AM-10:20AM in Olin 213.


Required Textbook

We will use Introduction to the Theory of Computation (3rd edition) by Michael Sipser.


Course Overview & Goals

Welcome to COSC 340: Theory of Computation!

The purpose of this course is to answer the following question: What are the fundamental capabilities and limitations of computers? In other words, what are computers able to do, and what are they not able to do? In order to find an answer to this question, we explore three separate subdomains: automata theory (the study of abstract machines and the computational problems that can be solved using them), computability theory (the study of the extent to which a problem is solvable on a computer), and complexity theory (the study of how efficiently a problem can be solved on a computer).

Topics will include languages (regular, context-free, context-sensitive, recursively enumerable), models of computation (finite-state machines, pushdown automata, Turing machines), the halting problem, decidability, and complexity classes (P, NP, etc.), among others. The skills you will learn in this course have a wide range of applications including compiler construction, artificial intelligence, parsing and formal verification, and algorithms. In addition, it will make you are better programmer.

Prerequisites: COSC 350 (Data Structures and Algorithms) with a minimum grade of C, MATH 181 (Calculus I) with a minimum grade of D, and MATH 235 (Discrete Mathematical Models) with a minimum grade of D.

Catalog Description: A study of formal models of computation such as finite state automata, push-down automata, and Turing machines, along with the corresponding elements of formal languages. These models are used to provide a mathematical basis for the study of computability and to provide an introduction to the formal theory behind compiler construction.

Course Goals

By taking this course, my goal is for you to:

  1. Gain a greater understanding of computers including their abilities and limitations.
  2. Learn how to construct abstract models of computation.
  3. Learn how to determine whether a given problem is solvable or not by a computer.
  4. Be able to formally classify a given problem as easy or difficult to solve.
  5. Be well prepared for further study in computer science.

You will fulfill these objectives by:


Grading

All grades will be recorded in Moodle as the semester progresses, including your final grade. Your final grade will be weighted as follows:

Assignments (40%)

You will complete multiple assignments to help solidify your understanding of the material, and these will be submitted via Moodle. Every project will be equally weighted, and each will be given a grade out of 10 points.

Quizzes (40%)

You will complete small quizzes every week 1) to help test your knowledge of things we discuss in class and read in the textbook, 2) to help you keep up in the course, and 3) to help me understand what topics need to be covered better.

Quizzes will be given at the end of class every Wednesday, and you will have roughly 15–20 minutes to complete them. These will be closed-book, and will be pencil/pen and paper. All quizzes must be turned in when the time is up. Each quiz will be worth 5 points (five problems, each worth 1 point). An answer to a problem must be completely correct to be awarded a full point. You must show your work for any problem that requires a sequence of steps to answer in order to receive a point for that problem.

The lowest 2 quiz scores will be dropped at the end of the semester.

Final Exam (20%)

You will complete a final exam that will review all of the concepts learned throughout the semester. It will essentially be a much longer quiz, and will occur on the scheduled final exam date.

Grading Scale

Grades will be rounded (92.49% = A- and 92.5% = A)

F D C- C- C+- B- B B+ A- A
0% - 59% 60% - 69% 70% - 72% 73% - 76% 77% - 79% 80% - 82% 83% - 86% 87% - 89% 90% - 92% 93% - 100%

Policies

ATTENDANCE

You are expected to attend class. I do understand that absences are sometimes unavoidable, so I appreciate an email letting me know in advance that you will be absent. You are responsible for catching up on missed classes. If you do not let me know ahead of time that you will be absent on a quiz day, you will not get a chance to retake the quiz. If you have an excused absence, contact me before the quiz to reschedule taking it.

Finally, in accordance with Wofford policy, you must be present for the final exam.

CLASSROOM

You are encouraged to bring your computer to work along with the examples in class. I highly advise you, however, to not become distracted by your devices (notebook, phone, tablet, etc.) for things other than course-related use. Not only are you missing out and inhibiting your learning, but it is often a distraction to others as well.

LATENESS

You are expected to keep up with all coursework and due dates during the semester. Submitting coursework past the due date/time (even by a single minute!) will result in a 20% penalty for that particular project. After that, you have 24 hours to submit the late work. After 24 hours, the project will not be accepted under any circumstances and will receive a 0. There are a few reasons that are acceptable (medical, family emergencies, etc.), but I will usually only grant extensions for those cases when receiving an email or phone call before the due date. I will decide on a case-by-case basis, but having official documentation will help make your case.

Quizzes must be taken on their scheduled date and time. If you must miss class on the day of a quiz, please contact me in advance. I will be much less likely to be forgiving if contacted afterwards.

According to Wofford policy, you must be present during the final exam time.

COMMUNICATION

I will use email for all communication. Feel free to contact me using "christbm@wofford.edu".

ACADEMIC INTEGRITY

Please do your own work! I have caught students cheating in the past, and take these matters very seriously. Any student I determine is guilty of academic dishonesty will receive a '0' for the assignment and have their case referred to the department and the college to be pursued further (trust me, you do not want that to happen). You may discuss ideas and pseudocode with other students, but all work must be your own. I will be using software to analyze your code to see if it closely matches that of another student.

To make sure you understand what constitutes academic dishonesty, please read the Wofford Honor Code. By enrolling in this course, you are pledging that you agree to the Wofford Honor Code and that all submitted work is your own. Please talk to me if you are unsure what constitutes academic dishonesty.

REASONABLE ACCOMMODATIONS

If you need accomodations with anything, please contact both the Wofford Accessibility Services and myself at the beginning of the semester.