Instructor: Ivan Avramovic
Email: iavramo2-at-gmu.edu
Hours: 10:30-11:30am Tue/Thu, 4609 Engineering Building
Assistants:
grader for this section -
Venkateshwar Chintakunta (vchintak-at-gmu.edu)
Bahman Pedrood (bpedrood-at-gmu.edu)
Anzal Khan (akhan62-at-gmu.edu)
Prerequisites:
CS211 and MATH125 (C or better in both)
Textbook:
Hamburger and Richards,
Logic and Language Models for Computer Science,
Third Edition
Webpage:
https://mason.gmu.edu/~iavramo2/classes/cs330s19.html
Piazza:
https://piazza.com/ for questions and discussion
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
-
Students will understand the concepts and relevance of logic,
formal languages and automata theory, and computability.
-
Students will be able to do mechanical formal proofs, program
correctness proofs and solve problems in first-order logic.
-
Students will be able to solve problems in elementary machine
models: designing finite-state, pushdown and turing machines.
-
Students will be able to solve problems in formal languages:
writing regular expressions, regular grammars, and context-free
grammars.
Topics
- Logical proofs
-
Propositional Logic (including truth tables; boolean algebra)
- Rules of Inference (proof by deduction)
- Mathematical Induction
- Predicate Logic (including quantifiers)
- Program Verification (including loop invariants)
- Regular Languages and conversions:
- Regular Grammars
-
Finite Automata (including deterministic and non-deterministic
FAs)
- Regular Expressions
- Context-Free Languages
- Context-Free Grammars
- Push-Down Automata
- Turing Machines
Grades
- Homework: 0%
-
homework will be assigned weekly but not collected or graded
- Quizzes: 30%
- the lowest quiz score is dropped
- quizzes will be weekly (except when displaced by exams)
- Exams (2): 40% + 30%
- exams are not cumulative
-
exams are closed-book, but one sheet (8.5"x11", 1-sided) of
hand-written or printed (original work only, no photocopies!)
notes is allowed; no copying note sheets from other students;
the better score of the two exams will receive the greater weight
- note: there will be no programming assignment this semester
Policies
-
please do not use laptops, cellphones, or similar electronic
devices during class without special permission
-
it is a departmental requirement that all undergraduate Computer
Science students taking CS330 must see their
advisor during the semester and submit
documentation of their visit; failure to do so will result in
an Incomplete grade
Honor Code
Programming assignments are an individual effort, no group work is
allowed. This includes the sharing of test cases. Any direct
contribution on a quiz, exam, note sheet or programming assignment will
be treated as a violation of George Mason's
Honor Code.