CS3133 Foundations of Computer Science

Syllabus— A Term 2009

Prof. Carolina Ruiz

WARNING: Small changes to this syllabus may be made during the term.


This course introduces the theoretical foundations of computer science. These form the basis for a more complete understanding of the proficiency in computer science. Topics include computational models, formal languages, and an introduction to computability and complexity theory, including NP-completeness. Students will be expected to complete a variety of exercises and proofs.
Intended audience: computer science majors and others desiring an understanding of the theoretical foundations of computer science.
Undergraduate credit may not be earned both for this course and for CS 503.
Recommended Background: CS 2022 and CS 2223.
Students who have credit for CS 4121 cannot receive credit for CS 3133.
Students graduating under the pre-1996 distribution requirements may satisfy the Theory area requirement by taking this course, although it does not count as a 4000-level course.


MT-ThF 10:00 - 10:50 am


Prof. Carolina Ruiz
Office: FL 232
Phone Number: (508) 831-5640

Office Hours: FL 232
Mondays 11:00 am - 12:00 noon
Thursdays 1:00 pm - 1:50 pm
or by appointment .


  • Li (Lif) Feng

    Office Hours: Fuller Labs Sub-basement Room A22
    Mondays 4:00 pm - 5:00 pm
    Tuesdays 11:00 am - 12 noon
    Thursdays 3:00 pm - 4:00 pm

  • Shweta Srivastava

    Office Hours: Fuller Labs Sub-basement Room A22
    Tuesdays 9:00 am - 10:00 am
    Wednesdays 2:00 pm - 3:00 pm
    Fridays 9:00 am - 10:00 am



Exam 1 25%
Exam 2 25%
Homework 50%
Class Participation Extra Points

Your final grade will reflect your own work and achievements during the course. Any type of cheating will be penalized in accordance to the Academic Honesty Policy.

Students are expected to read the material assigned to each class in advance and to participate in class. Class participation will be taken into account when deciding students' final grades.


  • Exams

    There will be a total of 2 exams. Each exam will cover the material presented in class since the beginning of the term. In particular, the final exam is cumulative. The exams will be based on material covered by the homework assignments, the lectures, and/or the textbook.

  • Quizzes

    Pop quizzes may be given during the term.

See the Course Schedule for the dates of the exams.
Collaboration or other outside assistance on exams and quizzes is not allowed.


Several homework assignments will be given. They will be posted to the course webpage at the appropriate times during the term.

The homework will be INDIVIDUAL, unless otherwise noted. You may discuss the material covered by the homework with your classmates if you wish, but you must develop and write YOUR OWN homework solutions. Your solutions must be your own original work.

LATE HOMEWORK POLICY: Unless otherwhise noted, homework is due at the beginning of class at 10:00 am. No homework will be received during the class period (10:01-10:50 am). Late homework received between 10:51 am and 4:00 pm of the day it is due will be accepted with a 30% off penalty (submit late homework in the CS Department Office FL233). No homework will be accepted after 4:00 pm the day it is due. No exceptions.


There are two mailing lists for this class (replace XXXX with 3133 below): Email your questions about HW, exams, class material, course logistics, etc. to csXXXX-staff@cs.wpi.edu, not just to the professor. The csXXXX-all@cs.wpi.edu mailing list that reaches the whole class should be used ONLY for messsages that are of interest to the entire class.


The web pages for this class are located at http://www.cs.wpi.edu/~cs3133/a09/
Announcements will be posted on the web pages and/or the class mailing list, and so you are urged to check your email and the class web pages frequently.


Small changes to this syllabus may be made during the course of the term.


WPI Worcester Polytechnic Institute

Computer Science Department