Foundations of Computation (CPSC 229)—Syllabus

Spring Semester, 2017

Vital Stats

  • Time: MWF 12:20 - 1:15 pm
  • Place: Gulick 206A
  • Instructor: John Lasseter
  • Office: Lansing 300
  • Office Hours:Wed 1:30 - 2:30, Th 10- 1:30, or by appointment (or just drop by)
  • Phone: (315) 781-4652
  • E-mail:
  • This web page:


In this course, we will study some of the mathematical foundations of computer science. This will include some fundamental techniques from discrete mathematics, such as logic, sets, functions, and techniques for mathematical proof. However, we will devote the bulk of the class to the study of fundamental considerations that underly that notion of computation itself.

A variety of formal languages that provide mathematical models of computing devices. These devices will focus our study in the exploration of three fundamental questions: what is a computer, what problems are possible for a computer to solve, and what problems can a computer solve with anything like reasonable efficiency? The formalisms developed in these models establish the mathematical foundations upon which all computation is based.


The prerequisite for this course is Introduction to Programming (CPSC 124). It is not a requirement, but you might also find it helpful to have some background in discrete mathematics, equivalent to what is taught in MATH 135.


Required Texts

Foundations of Computation, by Carol Critchlow and David Eck (2011).

The physical copy of this text is extremely cheap—a little over 10 bucks—and it is also available for free online at (LINK).


Foundations of Computer Science, by Alfred Aho and Jeffrey Ullman (2011).

This book is out of print. However, it is available for free online at (LINK).

Format of the Course

Participation and Preparation

In advance of each class, you will be assigned reading and the occasional small problem set, which you are expected to prepare in advance. Class time will be a mix of lecture, discussion, and collaborative problem-solving, and your preparation is essential to the success of that.


There will be several graded problem sets, which will be assigned approximately every other week.

Midterm Exam

There will be one mid-term exam, given in-class.

Final Exam

Tuesday May 9, 1:30 - 4:30 pm.



Your prompt attendance is required at every class, for the entire class. You may take a total of 2 excused absences for the semester. Each absence beyond that (unless explicitly arranged with me) will cost 5 points from your final grade, up to the maximum participation component.

Late Policy

All problem sets are due at the beginning of the class for which they are assigned, and cannot be turned in after that. In exceptional circumstances (such as the inability to attend a class session), I might make an exception, but this is at my discretion. You should arrange such a thing in advance.

Students with Disabilities:

Students with documented disabilities who may need accomodations, who have any emergency medical information an instructor should know of, or who require special arrangements in the event of an evacuation, should contact me as early as possible, preferably no later than the first week of classes.

If you are a student with a disability for which you may need accommodations, you should self-identify and register for services with the Coordinator of Disability Services at the Center for Teaching and Learning (CTL), and provide documentation of your disability. Disability related accommodations and services generally will not be provided until the registration and documentation process is complete. The guidelines for documenting disabilities can be found at the following website:

Please direct questions about this process or Disability Services at HWS to David Silver, Coordinator of Disability Services, at or x3351.

Academic Honesty:

I take this very seriously: a breach of academic honor will result in a failing grade for the course, and may be subject to further college sanctions. These standards are clearly laid out in the HWS Catalogue

and for the most part, they're pretty straightforward: your work must be yours and yours alone (or your working groups, if that applies), and your exams can only be discussed with me. Basically, you know already know the difference. Don't cheat.

Collaboration: Most assigned work is intended to be collaborative. Where individual efforts are required, you are still permitted -- indeed, encouraged -- to discuss course material with each other, to evaluate, trace, debug, refute, validate, or otherwise compare each others' work, and to adjust your own work if this collaboration results in new understanding.

However, you are not free to simply mail or print identical copies of the same work, and claim that it is the work of two separate individuals/groups. This is plagiarism, and is a breach of academic honor standards (it is also extremely easy to spot, especially in a class this small). While I encourage you to learn from each other, at the end of the day, the work you submit for a grade must be yours and yours alone.

If you find yourself unsure whether a form of collaboration or borrowing is acceptable, please ask me, in advance.


Relative weights for your final grade are as follows

  • Participation and Preparation: 10%
  • Homework: 40%
  • Midterm Exam: 20%
  • Final Exam: 30%