George Mason University
DEPARTMENT OF COMPUTER SCIENCE
CS330 - Formal Methods and Models - Spring 2018
TR 9:00–10:15, IN 204
Prerequisites | Description | Readings | Syllabus | Grading | Late | TA | Dates
This page last updated on 1/17/2018
703-993-1545
richards@gmu.edu
(Please prefix the subject of your email with CS330.)
Course office hours: TR 10:30-11:30 or by appt.
Engineering Bldg 5320
PREREQUISITES :
CS211 and Math 125 (C or better in both).
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 provide practical experience with some theoretical topics.
OUTCOMES :
Will understand the concepts and relevance of logic, formal languages and automata theory, and computability .
Will be able to able to do mechanical formal proofs, program correctness proofs and solve problems in first-order logic.
Will be able to solve problems in elementary machine models: designing finite-state, pushdown and Turing machines.
Will be able to solve problems in formal languages: writing regular expressions, regular grammars, and context-free grammars.
READINGS:
SYLLABUS:
The pace is approximate. Later chapters will not be covered as completely.
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-A
Exam #1 7
Regular Languages & Finite Automata 7-10 7-9
[AWK: Regular Expression Application 11 B]
Context-Free Grammars & PDAs 12-13 10-11
Turing Machines & Computability 14 12
GRADING :
Quizzes -- 20%
Program-- 20%
Exams -- 60%
The two exams each cover about a half of the semester; Exam #2 is not cumulative.
Of these exams the highest score will count 35%, and the lowest 25%.
Tentatively Exam #1 will be March 20. Exam #2 will be May 10 (at the official final exam time)
Homework is ungraded.
Quizzes will test homework, typically every other class.
The lowest quiz grades will be dropped (best 10).
There will be small programming assignments in Prolog [and AWK. ]
(This semester there will be no AWK assignment.)
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 http://cs.gmu.edu/resources/honor-code/ for the GMU and Computer Science guidelines.)
It is a departmental requirement that every CS major must see their academic advisor twice, once while enrolled in CS101 and in CS330. Of course, you should see your advisor more often, as needed. If you are in both CS330 and CS101, one visit per semester is enough. (Non-majors and graduate students are not included.) The visit must be documented and signed/verified by the advisor.
If you do not do this you will receive an incomplete in CS330.
When you see your advisor you should discuss your degree progress and anticipate any reason your plan of study would be problematic. Of course you may have other questions. Also note that your advisor may not be able to meet with you at the last minute.
What do you need to do? You should print out the department’s form (cs.gmu.edu/resources/ student.forms)
and a copy of your degree progress from DegreeWorks before the your meeting. Also your advisor can just send me email, if this is very late.
LATENESS:
Programs will be marked down 25% each class they are late; in particular, it is marked down 25% after the due date.
TA:
Sivani Tadepalli, stadepal@gmu.edu, ENGR 4456, M 10-12
Jhanvi Rafalia, jrafalia@gmu.edu, ENGR 4456, W 2-4
(TAs for the other sections Prakhar Dogra, TR 3-4, Neeraj Lamba T 4-5, W 11-12)
NO LAPTOPS, cell-phones, etc. (If you NEED a laptop for note-taking then speak to me.)