CSC444/344: Syllabus

Contact Information

Instructor:James Riely
Home Page:
Address: School of Computing, DePaul University
243 South Wabash Avenue
Chicago, IL 60604-2301
Office:CDM 846
Office Hours: Wed 4:00-5:00pm in CDM 846
Thu 4:00-5:00pm in CDM 846
Class Page:
Class Hours: Wed 5:45pm-9:00pm in CDM 222 [Section 701]
Online, Anytime [Section 702]

Mailing List


This course covers two basic models of computation: finite automata and pushdown automata. We will discuss the various forms that these models can take, the equivalence or inequivalence of each type of model, and the problems that can or cannot be solved by each model.

The topics covered will include:

If we have time, I would like to cover some additional topics, at least superficially (in order of decreasing priority):


By the end of this course you should:

Lecture Plan

The following lecture plan is tentative and subject to change as the course progresses.

Lecture slides will be available after each lecture. They will not normally be available before the lecture.


For undergraduates: MAT141 and CSC211. For graduates: CSC415.

You should be comfortable with basic set theory, functions, proofs by induction, basic graph theory, the analysis of algorithms and asymptotic notation (big-oh, theta, omega).


See file:links-main.

Required: Introduction to the Theory of Computation [Amazon, AddAll], by Michael Sipser (PWS, 1997)


It is important that you read the required material before class, and review it again afterwards.

Our goal is to achieve a depth of understanding. It is essential that you understand both examples and proofs.


The midterm exam will be held 2004/10/06 in class. The final exam will be held 2004/11/17 in class.

Block out these dates now!

I will be giving weekly homeworks and having one or two students answer questions in each class, so some attendance will be necessary.

If you are absent from class you are responsible for understanding the material and for finding out about any announcements made in that class. In addition, much of the discussion will be based upon diagrams drawn on the board. They may not appear in the slides and may not be captured well by COL.


There will be weekly assignments, a midterm, and a final. The course grade will be computed as follows:

You must hand in the homework each week in order to receive the 10 points for homework. Note, however, that I will only review homework in detail for students whose final score is borderline (say between an A- and a B+).

The midterm and final will be cumulative. You must earn a passing grade on the midterm and final to pass the course.

There will be no make-up exams nor extra credit assignments. If there is an extreme emergency and you must miss an exam, you must notify me in advance and provide documented evidence of the emergency.

Students in the distance learning section of the course are expected to take both exams at the same time as the on-campus section of the course. If there is not sufficient space in the regular classroom to accommodate all students, another location will be provided for distance learning students.

Unless otherwise stated, homework assignments are due by 5:30PM before class the week after they are assigned. Any assignment handed in after the deadline will be considered late. Assignments that are late will lose 50% of the points for each day that they are late. No assignment will be accepted more than two days after its due date (including Saturdays, Sundays, and holidays). Assignment deadlines will be strictly enforced; however, your lowest homework score will be dropped in the calculation of your final grade.

Homework assignments must be submitted through the online system. Email submissions will not be accepted.

Distance learning students are subject to the same homework deadlines as students in the regular section of the course.

Program submissions will be assessed on whether they achieve the set task and the quality of the code.

DePaul's academic integrity policy