CSCI 338: More Information

Back to the Syllabus

Textbooks

• The Golden Ticket: P, NP and the Search for the Impossible by Lance Fortnow.
• Introduction to the Theory of Computation, Third Edition by Michael Sipser.

Online Resources

• Python 3.5 with the IDLE editor - site

Catalog Information

• Credits: 3
• Description: Formal languages, theory, automata, Turing Machines, computability, the Church-Turing thesis, computational complexity, and NP-completeness.
• Pre-requisites: CSCI 246 and M 171.

Course Outcomes

At the end of the course, students should be able to

• Be familiar with the basic concepts of computer science theory.
• Be familiar with basic proof techniques.
• Understand the difference between deterministic and nondeterministic computations for finite-state automata, push-down automata and Turing machines.
• Understand decidability and undecidability.
• Understand time complexity and NP-Completeness, including the basic concept of a reduction.

Graded Items

• Midterm 1 - 15%
• Midterm 2 - 15%
• Final - 25%
• Bin Packing - 20%
• Homeworks - 25% (all homeworks are worth the same)

Grading Policy

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-

If you fall within one percentage point of the next grade higher, your grade on the final exam will be examined. If it justifies you being in the next higher grade category, you will receive that higher grade.

Collaboration Policy

All students should read the MSU Student Conduct Code.

When it comes to Python assignments, you may

• Work with the other people on your team if teams are allowed. Each assignment will specify the maximum number of people per team.
• Share ideas with people in other teams.
• Help other teams troubleshoot problems.

You may NOT

• Share code you write with other teams.
• Submit code that someone on your team did not write.
• Modify another team's solution and claim it as your own.

Failure to abide by these rules will result in an "F" for the course and being reported to the Dean of Students.