Chris Pollett >Old Classes >

( Print View )

Grades: [Sec1]

Course Info:
Texts & Links]
  [HW Info]
  [Exam Info]

HW Assignments:
  [Hw1]  [Hw2]  [Hw3]
  [Hw4]  [Hw5]

Practice Exams:
  [Mid1]  [Mid2]  [Final]


CS154Spring 2003Sec1Home Page/Syllabus

Formal Languages and Computability

Instructor: Chris Pollett
Office: MH 214
Phone Number: (408) 924 5145
Office Hours:MW 2:30-4:00pm F 2:30-4:30pm
Class Meets:
Sec1 MWF 1:30pm-2:20pm in MH224


To take this class you must have taken: MA42 and CS46B with a grade of C- or better.

Texts and Links

Required Texts: Elements of the Theory of Computation. 2nd Ed.. by H. Lewis and C. Papadimitriou.
Online References & Other Links: comp.theory.


The purpose of this class is to introduce students to the concepts that lie behind the way compilers works, that form the basis of an important family of string matching algorithms, and that lie behind many modern XML-based web languages as well as AI programming techniques used in video games. In particular, in this class the concepts of formal languages and decidability will be introduced. We begin by considering regular languages and finite automata. These concepts are used in practice to do such things as to match the tokens of a programming languages or to monitor the state of a creature in a video game. We will next consider context free languages and push down automata. These are used to parse program structures such as matching braces or pairs of XML tags. We will then consider what it means for one programming language to be able to do all the things that one could consider doable in any programming language. We will also consider what kinds of problems do not have algorithms in any programming language. Finally, we will be interested in studying what kinds of algorithms can be guarenteed to run in a feasible amount of time. To this end we will consider the classes P and NP and some of the issues connected with these classes.

Below is a tentative time table for when we'll do things this quarter:

Week 1: Jan 22, Jan 24 Read pp5-23
Week 2: Jan 27, Jan 29, Jan 31 Finish Ch 1
Week 3: Feb 3, Feb 5, Feb 7 Read pp55-75
Week 4: Feb 10, Feb 12, Feb 14 Read pp75-92
Week 5: Feb 17, Feb 19, Feb 21 Finish Ch 2
Week 6: Feb 24, Feb 26, Feb 28 Read pp113-130
Week 7: Mar 3, Mar 5, Mar 7 Read pp130-150
Week 8: Mar 10, Mar 12, Mar 14 Finish Ch 3
Week 9: Mar 17, Mar 19, Mar 21 Read pp179-200 (then Spring recess)
Week 10: Mar 31(Holiday), Apr 2, Apr 4 Read pp200-219
Week 11: Apr 7, Apr 9, Apr 11 Finish Ch4
Week 12: Apr 14, Apr 16, Apr 18 Read pp245-262
Week 13: Apr 21, Apr 23, Apr 25 Read Ch6
Week 14: Apr 28, Apr 30, May 2 Read pp301-317
Week 15: May 5, May 7, May 9 Finish Ch7
Week 16: May 12 Review.
The final will be May 21, 12:15pm-2:30pm


Homeworks 40%
Midterm 1 15%
Midterm 2 15%
Final 30%

When I assign grades the high score has an opportunity to receive an A+. I do curve grades and my curving will be in line with previous times this class has been taught. If you do better than an A- in this class and want me to write you a letter of recommendation, I will generally be willing.

Homework Info

Links to the current list of assignments can be found on the left hand frame of the class homepage. A link that will allow you to view your grades for the course can also be found here.

Homeworks are required to be done in groups of two to three people. Homeworks with fewer than two or more than three names on them will not be accepted. Homeworks must be written up neatly on paper and are always due by the start of class on the due date. Late homeworks will not be accepted; however, your low homework score will be dropped. The names of the people who worked together on the assignment must be clearly written on the upper right corner of the first page. If I cannot read a name that person will not receive any credit on that homework set. Each homework will consist of a reading and writing part. Material from the reading part of an assignment may appear on midterms and finals.

As each homework set will consist of many problems it is recommended that you divide the labour of doing the problems among the members of the group. You are allowed to change groups after each homework provided that you still remain in groups of two or three. On the day a homework is due, I will invite each group to write a problem on the board. I will grade this problem at that time. Students can copy down what is on the board as a solution set for that homework. If there is anything ambiguous about a problem that has been written on the board I will choose a random member to the group who wrote the problem on the board to ask for clarification. It is each group member's responsibility to make sure the other group members know how to do all the problems on a given homework set.


The midterms will be during class time on: Mar 5 and Apr 16.

The final will be: May 21, 12:15pm-2:30pm.

All exams are closed book, closed notes and in this classroom. You will be allowed only the test and your pen or pencil on your desk during these exams. Beeper or cell-phone interruptions will result in immediate excusal from the test. The final will cover material from the whole quarter although there will be an emphasis on material after the last midterm. No make ups will be given. The final exam may be scaled to replace a midterm grade if it was missed under provably legitimate circumstances. These exams will test whether or not you have mastered the material both presented in class or assigned as homework during the quarter. My exams usually consist of a series of essay style questions. I try to avoid making tricky problems. The week before each exam I will give out a list of problems representative of the level of difficulty of problems the student will be expected to answer on the exam. Any disputes concerning grades on exams should be directed to me, Professor Pollett.


If you believe an error was made in the grading of your program or exam, you may request in person a regrade from me, Professor Pollett, during my office hours. I do not accept e-mail requests for regrades. A request for a regrade must be made no more than a week after the homework is returned.

Academic Honesty

Plagiarism on homework or cheating on tests will result in appropriate academic disciplinary action being taken. Information on the university policy governing academic dishonesty can be found at