George Mason University
DEPARTMENT OF COMPUTER SCIENCE
CS330 - Formal Methods and Models - Summer 2007
MW 9:30-11:45, Innovation 206
Prerequisites |
Description |
Readings |
Syllabus |
Grading |
Late |
TA |
Dates
This page last updated on 4/10/07
Professor Dana Richards
703-993-1545
richards@cs.gmu.edu
(Please prefix the subject of your email with CS330.)
Course office hours: Monday and Wednesday 2:00-3:00 or by appt.
Sci&Tech II Room 425
PREREQUISITES :
CS211 and Math 125 (C or better in both).
The exposure to Discrete Mathematics (in Math 125 or a similar course) for
most students has been important for success in this course.
DESCRIPTION :
This course is an introduction to two kinds of formal systems
- languages and logics - with important applications to
computer science. The study of formal languages underlies
important aspects of compilers and other language processing
systems, as well as the theory of computation. Various
systems of logic and automatic reasoning are put to use in
artificial intelligence, database theory and software
engineering. The entire course will give you practice in
precise thinking and proof methods that play a role in the
analysis of algorithms. The programming assignments in Lex
and Prolog provide practical experience with some theoretical topics.
READINGS:
- Logic and Languages Models for Computer Science, by Hamburger and Richards.
SYLLABUS:
The pace is approximate. It is adjusted for the summer.
Topic Week Chapters
Introduction 1 1
Propositional Logic and Proofs 1-2 2-3
Predicate Logic and Proofs 3-4 4-5
Applications: Prolog and Verification 5-6 6-7
Exam #1 6
Finite Automata, Regular Expressios 7-9 8-10
Lex: a Regular Expression Language 10 11
Context-Free Grammars & Applications 11-12 12-13
Turing Machines & Solvability 13-14 14
##Tenatively, Exam #1 will be , and quizzes will every .
GRADING :
Quizzes -- 20%
Programs -- 20%
Exams -- 60%
The two exams, including the final, each cover about a half
of the semester; the final is not cumulative. Of these exams the
highest score will count 35% and the lowest 25%.
Homework is ungraded.
Quizzes will test homework, typically every other class class.
The lowest quiz grades will be dropped.
There will be small programming assignments in Lex and in Prolog.
All testing is closed book, but limited notes are permitted,
as follows for exams (but not for quizzes).
One sheet of notes (8.5 by 11 inches, 1 side only). NO COPYING is
allowed. That means no photocopying of anything, even the
textbook, though you may write out material from it verbatim.
It also means no copying of anyone else's notes, even by
hand. You may use a computer for editing your own notes.
The sheet must be turned in with your exam. Violations of these
rules for creating the notes is considered a violation of
the Honor Code.
There is to be NO group work on the programs. Receiving direct
contributions to the code that is submitted is considered a
violation of the Honor Code. (See cs.gmu.edu/students/hnr_cds.html
for the GMU and Computer Science guidelines.)
LATENESS:
Programs will be marked down 25% each week they are late;
in particular, they are marked down 25% after the due date.
TA:
Walid Jindan, wjindan1@gmu.edu