## CSCI 338: Computer Science Theory

### Fall 2020

Schedule subject to change. Refresh webpage (or hit F5) to view current page.
## Lecture

- Tuesday, Thursday 3:05 - 4:20 pm in NAH 201.
- 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-3pm) and Thursday (2-3pm) pm and by appointment.

## 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 - 60% (evenly weighted, with two lowest dropped). Homework solutions need to be legible. Use a text editor (like LaTeX) if needed.
- Quizzes - 40% (16% for each of your two highest, 8% for your lowest)

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.
## Collaboration Policy

- You may do homework assignments 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.

## Sickness Accommodations

- This entire course can be taken remotely. Lectures are posted online. Office hours can be done remotely. Homework is turned in online. Tests will be given online.
- Do not come to class (or office hours) if you are sick.
- Do not use up all of your homework drops early. You never know when you will get sick and need to use them.

## Masks

Per MSU:
"Face coverings are required in all indoor spaces and all enclosed or partially enclosed outdoor spaces. MSU requires all students to wear face masks or cloth face coverings in classrooms, laboratories and other similar spaces where in-person instruction occurs. MSU requires the wearing of masks in physical classrooms to help mitigate the transmission of SARS-CoV-2, which causes COVID-19. The MSU community views the adoption of these practices as a mark of good citizenship and respectful care of fellow classmates, faculty, and staff.
The complete details about MSUâ€™s mask requirement can be found at https://www.montana.edu/health/coronavirus/index.html."