title: "Syllabus"

Syllabus

Basic Information

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:

0. Foundations: Proof techniques, sets, functions, and countability
1. Models of Computation: Finite automata, regular expressions, the pumping lemma, context-free grammars, and pushdown automata
2. Computability: Turing machines, decidability, the halting problem, reductions, and Rice's theorem
3. Complexity: Asymptotic notation, P, NP, verifiers, and NP-completeness

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

Prerequisites

This course assumes a first course in discrete mathematics: sets and set operations, functions and relations, elementary number theory (divisibility and remainders), and comfort reading and writing quantified statements. Unit 0 reviews this material rather than teaching it from scratch.

It also assumes the usual programming and algorithms background of the major. No programming is assigned, but the motivating examples throughout draw on it: loop invariants, dynamic programming, compilers and parsers, and public-key cryptography all appear as illustrations, and the payoff sections of Units 2 and 3 assume you have written programs before.

Course Materials

Everything you need is on this site. The lecture notes are the course text: each one is written to stand on its own, and every exercise is solvable from the notes and the linked terminology alone. There is no required or recommended textbook to buy.

Important Dates (Fall 2026)

Per the LMU Fall 2026 Academic Calendar:

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, and your lowest two warm-up scores are dropped to cover ordinary absences
• Routine absences: no need to notify me. The two drops exist for exactly this, and I will assume you make up the material
• Documented absences: if you will miss more than two meetings for a documented reason (illness, religious observance, university-sanctioned travel, or an accommodation arranged through Disability Support Services), email me as early as you can and those warm-ups will be excused rather than counted, so your grade is computed over the warm-ups you were able to take. Excused absences are not capped at two
• 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.

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.)

Classwork (40%)

Nearly every class begins with a classwork problem: handwritten, worked in class, 20 minutes. Each classwork problem is worth 20 points:

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 classwork. 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.

Exams (60%)

Two exams:

• Midterm Exam: in class (tentatively Thu Oct 15), covering Units 0-1.
• Final Exam: during the registrar's final exam slot (Dec 14-18), covering 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%.

Missing an exam. Contact me before the exam if at all possible. Without a documented reason, a missed exam scores zero and counts as your weaker exam.

Grading Scale

Grades round to the nearest whole number.

Tentative Schedule

(Subject to change; check back here regularly for updates.)

Lecture pages are published as we reach them, so a lecture linked below may not open until we approach the last days of the lecture. Everything already covered will stay available for the rest of the term.

Unit 0: Foundations

Unit 1: Models of Computation

Unit 2: Computability

Unit 3: Complexity

Academic Integrity

Students are encouraged to collaborate and discuss concepts, but all submitted work must be your own.

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: [email protected] 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/