CPSC 229 Course Information

From the course catalog:

This course introduces students to some of the mathematical and theoretical foundations of computer science, and to their practical applications to computing. Topics include propositional and predicate logic, sets and functions, formal languages, finite automata, regular expressions, grammars, and Turing machines. This course is required for the major in computer science.

By the end of the course, the successful student should be able to:

• explain the terminology and concepts of propositional and predicate logic
• explain the terminology and concepts of formal languages, including methods of specifying, producing, and recognizing those languages (regular expressions and finite-state automata, context-free grammars and pushdown automata, general grammars)
• explain aspects of computability theory, including the Church-Turing thesis, decidability, the halting problem, and the limits of computation
• explain the relevance and some applications of the "foundations of computation" studied to computer science and computing
• recognize and write rigorous proofs, applying formal proof techniques (including induction and contradiction) to establish and clearly convey the validity of a statement
• understand and use regular expressions
• understand syntax expressed as a grammar using BNF or similar notation
• use, write, and analyze context-free grammars, and design and analyze finite-state automata, pushdown automata, and Turing machines
• model and reason about computational systems, including their limitations and capabilities

This is primarily a lecture-based class with three class meetings per week, weekly written homeworks, and in-class exams. In addition, there will be five one-hour lab sessions scheduled over the course of the semester, with accompanying lab assignments exploring practical applications of the course material.

You are expected to attend all scheduled class meetings, including the lab sessions. The timing of the lab sessions will be set early in the semester and effort will be made to schedule them at times everyone can attend. If you cannot attend a scheduled lab, it can be made up by coming to office hours instead.

You should expect to spend approximately 8-10 hours per week on average on additional work (readings, homework, studying) outside of class. While your experience may vary from topic to topic or from week to week, if you routinely spend substantially more time or you feel like you are spinning your wheels and not making progress, you should visit office hours for help.

CPSC 124 is required.
Java will be used in some examples, and some of the lab assignments will require writing small programs in Java.

Textbook

Foundations of Computation, 2nd ed.
Carol Critchlow and David Eck

The book is freely available at https://math.hws.edu/FoundationsOfComputation. You can download a PDF version from the website, or order a printed copy if you'd like a physical copy. Please do not use the Math/CS department printers to print the text for yourself.

Additional material will be handed out or posted on the course webpage.

Software

All of the software used in the lab assignments is available online and/or in the campus Linux environment (accessible in Demarest 002 or remotely through the Linux VDI).

last updated: --Wed Jan 14 21:50:34 EST 2026--
page owned by: bridgeman@hws.edu