Instructor: Gianfranco Ciardo

Class meetings: Tue/Thu 12:30 p.m. - 1:50 p.m., Room: Blair 223

Textbook: An Introduction to Formal Languages and Automata, 3rd Edition, P. Linz (Jones and Bartlett)

Office hours: Tue/Thu 2:00 p.m. - 4:00 p.m., Room: McGlothlin-Street Hall 117

Final examination: Friday, December 14, 2001, 8:30 a.m. - 11:30 a.m.

Prerequisites: Undergraduate students enrolled in CSci 423 must have taken and successfully passed CSci 303, Algorithms, and Math 211, Linear Algebra. Graduate students enrolled in CSci 523 must have a knowledge of linear algebra and data structures.

Satisfaction of writing requirement

Homeworks

One of the goals of this course is to teach how to write high-quality technical prose. To improve the terseness and readability of your homeworks, I am requiring you to typeset your homeworks in LaTeX, available on our Unix system. I provide examples of LaTeX files for you to learn how to format particular equations. Pictures, diagrams, and graphs can be drawn using tgif or any other drawing tool that can generate ``eps'' files, which are then included into LaTeX. Homeworks should be printed single-sided, and stapled in the upper left corner.

Within the first week, I divide the undergraduate class into groups of two, or possibly three, students each. These groups remain fixed for the entire duration of the course. The students in a group are allowed to discuss the homework problems among themselves and with me, but not with anybody else. An empty hand policy must be observed when you meet with other members of your group: you are free to discuss any aspect of the homework, but you must leave the meeting without any any record (on paper, tape, or other means) of these discussions. This is because the actual writing of the detailed homework answers must be an individual activity, so that each student can receive an individual grade for each homework.

Unless stated otherwise, sharing of information in permanent format (such as accessing someone else's files, hardcopy outputs, or handwritten notes), even if between members is the same group, will be considered a violation of the Honor Code. If you have even the slightest doubt about whether a certain activity is admissible, ask me before you do it!

You are of course allowed, actually encouraged, to consult other reference material in addition to your textbook and class notes. However, if you used this reference to derive the anser to an exercise, you should give it proper credit in your write-up. In no case you should copy verbatim from a reference without proper attribution, as this is considered plagiarism.

I do not accept late homeworks except for justifiable reasons, such as an illness with a doctor's written note.

Homework grading method

For undergraduate students a similar policy holds, but the total weight required might be less. For example, HW3 might consist of four problems with weight 100, hence the total weight for HW3 is 400, but the undergraduate students might be required to reach weight 300. Hence, to obtain a full score, you need to solve three of the four problems perfectly, or obtain a 75 on each of the four problems, or any other combination resulting in 300. If you obtain a score higher than the required weight, it is counted in your average, so don't worry about scoring too high! My goal is to encourage each of you to at least attempt the solution of every problem.

While I may choose to give you partial credit on an exercise, more often than not an answer is either ``right'' (perhaps with minor notational errors or problems that can be easily fixed) or ``wrong'' (completely incorrect because of some fundamental flaw in your reasoning). Thus, the grade you receive on each individual exercise is usually either close to the maximum or to zero. However, there are several exercises in an homework set, so the overall grades can, and usually do, span a wide range.

Student portfolio

By the last day of classes, each student is required to turn in a portfolio consisting of all the original graded homeworks, plus a corresponding set of revised homeworks. Since the solution to most, if not all, homework problems is eventually discussed in class, I expect to see correct solutions in the revised homeworks. Therefore I judge them mostly on the basis of how much their presentation improved with respect to the original version. Of course, if I did not find any problem initially, your revised version can coincide with the original one. Your portfolios are returned to you on the day of the final exam.

Reading and commenting other student's answers to the homeworks is an excellent way to improve your own ability to write technical prose. Hence, you are allowed to distribute a hardcopy of any revised homework to the members of your group, who will then be able to write comments on it before returning it it to you. Of course, you can do this only after each homework has been graded and returned. This is an exception to the rule about the exchange of information in permanent format.

Evaluation of your portfolio accounts for 5% of your grade.

In class examinations

After a couple of lectures on basic background and introductory notions, the course can be divided into three main sections: regular languages, context-free languages, and Turing machines. There will be one 80-minute exam focussing on regular and context-free languages. It is scheduled for Thursday, November 1, 2001, 12:30 - 1:20 p.m. and accounts for 15% of your grade. The final exam covers the entire course material. It is scheduled for Monday, December 14, 2001, 8:30 - 11:30 a.m. and accounts for 30% of your grade.

Final grade policy

I reserve the right to raise the final grade, but not to lower it: if your overall grade is 89%, I might decide to give you an A- or a B+, but if it is 80% you are guaranteed at least a B.

Detailed schedule

Students with disabilities