Syllabus
Basic Information
| Item | Details |
|---|---|
| Instructor | Jared Coleman |
| jared.coleman@lmu.edu | |
| Office | DOO-212 |
| Office Hours | TBD |
| Zoom | https://lmula.zoom.us/my/jaredcoleman |
| Lecture Time | TBD (schedule below assumes Tu/Th) |
| Lecture Location | TBD |
Course Description
This course studies the theory of computation: what problems can be solved by computers at all (computability), and what problems can be solved efficiently (complexity). It is a theory course; there is no programming. You will write proofs, and by the end you will understand some of the most beautiful results in computer science, including the halting problem, NP-completeness, and the P versus NP question.
The course is organized into four units:
- Foundations & Review: Proof techniques, sets/relations/functions, asymptotic notation done carefully
- Models of Computation: Finite automata, regular languages, context-free grammars, the Chomsky hierarchy
- Computability: Turing machines, decidability, the halting problem, reductions, Rice's theorem
- Complexity: P, NP, NP-completeness, coNP, space complexity, the hierarchy theorems
Learning Objectives
By the end of this course, students will have gained:
- Fluency with the core proof techniques of theoretical computer science: induction, contradiction, diagonalization, and reduction
- A precise working command of asymptotic notation and complexity classes
- An understanding of the major models of computation and the boundaries between them
- The ability to prove problems undecidable via reductions and to prove problems NP-complete
- An appreciation of the central open questions of the field, especially P versus NP
Texts
- Sipser, Introduction to the Theory of Computation (3rd edition): the spine of the course; readings are assigned per lecture.
- Arora & Barak, Computational Complexity: A Modern Approach: supplement for the complexity unit. A free draft PDF is available from the authors.
- Additional free references linked from each lecture page.
Important Dates (Fall 2026)
Per the LMU Fall 2026 Academic Calendar:
| Date | Event |
|---|---|
| Mon Aug 31 | First day of instruction |
| Fri Sep 4 | Last day to add/drop without a grade of W |
| Mon Sep 7 | Labor Day, no classes |
| Fri Oct 9 | Autumn Day, no classes |
| Fri Nov 13 | Last day to withdraw or request credit/no-credit grading |
| Wed-Fri Nov 25-27 | Thanksgiving Holiday, no classes |
| Fri Dec 11 | Last day of instruction |
| Mon-Fri Dec 14-18 | Final examinations |
Labor Day and Autumn Day fall on Monday and Friday, so no Tu/Th lecture meetings are lost to holidays except Thanksgiving Thursday (Nov 26).
Lecture Attendance
- Mandatory: Lecture attendance is required; graded warm-up problems happen in class with no makeups (lowest two dropped)
- No need to notify for absences: I'll assume you will make up the material
- Participatory lectures: Come prepared to ask and answer questions!
Work Load Expectations
At LMU, each unit corresponds to 3 hours of weekly work.
Since this is a 4-unit class, expect ~12 hours per week.
This includes lecture time, exercises, studying, and preparation. Expect ~8 hours/week outside of lecture.
I highly recommend that you make a weekly schedule for yourself, blocking out time for lectures and coursework/studying for all of your classes. Even if you aren't able to follow it exactly, this will help you visualize how much time you are actually spending on your classes and whether they match the expected workload.
Finding Help for the Course
LMU CMSI offers many resources to support your success:
- Slack Messaging: Download Slack (https://slack.com) and join the LMU CS workspace (https://lmucs.slack.com). If I don't respond within 24 hours (excluding weekends), please send a reminder!
- Office Hours: Attend weekly office hours (times listed above). If you have valid schedule conflicts, email me to arrange alternatives.
Assignments and Grading
(Tentative; final structure will be announced before the semester starts.)
In-Class Work (40%)
Nearly every class begins with a warm-up problem: handwritten, worked in class, 20 minutes. Each warm-up is worth 20 points:
| Points | For |
|---|---|
| 5 | Getting it right |
| 5 | Applying the right concepts and explaining them |
| 10 | Participation (having reasonable work written down) |
There is plenty of room for partial credit: a serious attempt that applies the right ideas will earn most of the points even if the answer is wrong.
There are no makeups for warm-ups. They can only be completed in class, which is how attendance is enforced. Your lowest two scores will be dropped.
Exercises (ungraded)
Each lecture ends with an Exercises section: work through it once we cover that lecture's material. Exercises are not collected or graded: they are your study material for the exams, and the exams will look a lot like them. Where possible, exercises come with an "unlimited practice" widget that generates fresh instances of the same problem (with solutions) right on the page. Solutions are discussed in office hours and on Slack.
Exams (60%)
Two exams:
- Midterm Exam: in class (tentatively Tue Oct 13), covering Units 0-1.
- Final Exam: during the registrar's final exam slot (Dec 14-18), cumulative with emphasis on Units 2-3.
Your stronger exam is weighted twice your weaker exam: whichever of the two you score better on counts for 40% of your course grade, and the other counts for 20%.
Grading Scale
| Percentage | Grade |
|---|---|
| 93-100 | A |
| 90-93 | A- |
| 87-90 | B+ |
| 83-87 | B |
| 80-83 | B- |
| 77-80 | C+ |
| 73-77 | C |
| 70-73 | C- |
| 65-70 | D |
| 0-65 | F |
Grades round to the nearest whole number.
Tentative Schedule
(Subject to change; check back here regularly for updates.)
Unit 0: Foundations & Review
| Date | Topic | Lecture |
|---|---|---|
| 09/01 | Course Introduction | - |
| 09/03 | Proof Techniques: Induction and Contradiction | Lecture 1 |
| 09/08 | Diagonalization and Countability | Lecture 2 |
| 09/10 | Sets, Relations, and Functions | Lecture 3 |
| 09/15 | Asymptotic Notation and Growth Rates | Lecture 4 |
| 09/17 | Asymptotics (cont.), the Idea of a Complexity Class | Lecture 4 |
Unit 1: Models of Computation
| Date | Topic | Lecture |
|---|---|---|
| 09/22 | Finite Automata: DFAs and NFAs | Lecture 5 |
| 09/24 | Finite Automata (cont.) | Lecture 5 |
| 09/29 | Regular Expressions and Closure Properties | Lecture 6 |
| 10/01 | The Pumping Lemma and Nonregular Languages | Lecture 7 |
| 10/06 | Context-Free Grammars and Pushdown Automata | Lecture 8 |
| 10/08 | CFGs (cont.), the Chomsky Hierarchy | Lecture 8 |
| 10/13 | Midterm Exam (Units 0-1) | - |
Unit 2: Computability
| Date | Topic | Lecture |
|---|---|---|
| 10/15 | Turing Machines and the Church-Turing Thesis | Lecture 9 |
| 10/20 | Turing Machines (cont.) | Lecture 9 |
| 10/22 | Decidability and Recognizability | Lecture 10 |
| 10/27 | The Halting Problem | Lecture 11 |
| 10/29 | Reductions and Rice's Theorem | Lecture 12 |
| 11/03 | Reductions (cont.) | Lecture 12 |
Unit 3: Complexity
| Date | Topic | Lecture |
|---|---|---|
| 11/05 | Time Complexity and the Class P | Lecture 13 |
| 11/10 | NP and Polynomial-Time Verifiers | Lecture 14 |
| 11/12 | NP-Completeness and the Cook-Levin Theorem | Lecture 15 |
| 11/17 | Classic NP-Complete Reductions | Lecture 16 |
| 11/19 | coNP and Space Complexity | Lecture 17 |
| 11/24 | PSPACE and Savitch's Theorem | Lecture 18 |
| 11/26 | Thanksgiving Holiday - No Class | - |
| 12/01 | The Hierarchy Theorems | Lecture 19 |
| 12/03 | Catch-up / Randomized and Approximation Classes (if time) | - |
| 12/08 | Review | - |
| 12/10 | Review / Course Wrap-up | - |
| Finals | Final Exam, Dec 14-18, per registrar schedule | - |
Academic Integrity
Students are encouraged to collaborate and discuss concepts, but all submitted work must be your own.
All forms of plagiarism result in severe disciplinary action.
Unacceptable behavior includes:
- Copying significant text from any external source without attribution
- Copying solutions from peers
- Presenting others' work as your own
AI Tools Policy: You may use AI assistants (ChatGPT, etc.) as learning aids, but you must understand and be able to explain everything you submit. Oral checks will verify your understanding.
If unsure whether something is allowed: ask first.
University Policy on Academic Honesty
LMU expects honesty and integrity in all academic work. Violations include copying, unauthorized collaboration, misrepresentation, and plagiarism. Consequences range from zero credit to expulsion.
Full policy: https://academics.lmu.edu/honesty/
Tentative Nature of the Syllabus
This syllabus may be updated. Students are responsible for checking announcements and this website regularly.
University Resources
Expectations for Classroom Behavior
Students should engage respectfully and follow LMU's behavioral guidelines:
- Lion's Code: https://studentaffairs.lmu.edu/about/osccr/studentcodespolicies/
- Classroom behavior guidelines: https://lmu.box.com/s/v2x89uspgbx3l23egcz7mjd6dbekcn60
Respect for self and others is expected at all times.
Computer Science Department - Student Guide
Resources and support: https://sites.google.com/view/lmucs
Academic Degree Requirements and Policies
See: https://bulletin.lmu.edu/academic-degree-requirements-policies/
Disability Support Services (DSS)
The DSS Office supports students with documented disabilities. Email: dsslmu@lmu.edu Phone: (310) 338-4216 Website: http://www.lmu.edu/dss
Academic Resource Center
Writing support and tutoring across subjects. More info: https://academics.lmu.edu/arc/
Emergency Preparedness
Public Safety: 310-338-2893 (x222 on campus) Emergency info: http://www.lmu.edu/emergency
Community of Care
Case-management support for student well-being: https://studentaffairs.lmu.edu/wellness/coc/learnmoreaboutus/