CS154Spring 2003Sec1Home Page/Syllabus

Formal Languages and Computability

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:

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.

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.