CSCI 338: Computer Science Theory
Fall 2021
Schedule subject to change. Refresh webpage (or hit F5) to view current page.
Lecture
- Tuesday, Thursday 3:05 - 4:20 pm in Reid 101.
- Lectures will be video taped and put on this website.
Instructor
Sean Yaw
- E-mail: sean.yaw (at) montana.edu (email me whenever, I'll respond as soon as I get it)
- Office: Barnard Hall 360
- WebEx: link
- Office Hours (in my office and on WebEx): Tuesday 1:00 - 3:00 pm and Thursday 2:00 - 3:00 pm and by appointment.
Grader/TA
Daniel Laden. Office hours: Wednesday 8:00 - 10:00 am in Barnard 259.
Textbook
- Introduction to the Theory of Computation by Michael Sipser.
Course Prerequisites
- CSCI 246: Discrete Structures.
- M 171Q: Calculus 1
Course Objectives
MSU course description: Formal languages, theory, automata, Turing Machines, computability, the Church-Turing thesis, computational complexity, and NP-completeness.
At the end of the course, my goal is for you to be able to:
- Understand what NP-Complete problems are, have an intuition for the solvability of new problems, and have familiarity with techniques to deal with NP-Complete problems.
- Given a problem, understand it and develop a clear, efficient plan to solve it.
- Be comfortable proving statements and formulating clear arguments.
- Understand that some problems cannot be solved.
- Understand various computational models and their inherit limitations.
Grading
- Homework - 40% (evenly weighted with two lowest dropped). Homework solutions need to be legible. Use a text editor (like LaTeX) if needed.
- Projects - 30% (evenly weighted with no drops).
- Quizzes + Final - 30% (evenly weighted with lowest dropped).
At the end of the semester, grades will be determined (after any curving takes place) based on your class average as follows:
- 93+: A
- 90+: A-
- 87+: B+
- 83+: B
- 80+: B-
- 77+: C+
- 73+: C
- 70+: C-
- 67+: D+
- 63+: D
- 60+: D-
- 0+: F
Late Policy
If you submit a homework assignment late, but within 12 hours of being due, the maximum credit you can receive is 50%. After 12 hours, you receive 0. If you submit a project late, but within 24 hours, the maximum credit you can receive is 70%. After 24 hours, you receive 0.
Collaboration Policy
- You may do homework assignments and projects in groups of up to three people. You must indicate on the submission everyone that contributed. If someone did not substantially contribute to a submission, they cannot be included on it.
- Exams are to be taken individually.
- You may not copy or modify solutions that are not your own (e.g. from the Internet, from a classmate not listed as a contributor,...) for any graded material. I know how to use the Google and I have a Chegg membership. If you find it, I will too!
Failure to abide by these rules will result in everyone involved being reported to the Dean of Students and could result in failing the course.