Spring 2020: Formal Methods and Models [CS330]

General Description and Preliminary List of Topics

This course is an introduction to two kinds of formal systems—languages and logics—that are crucial to large numbers of areas in computer science. The study of formal languages underlies important aspects of compilers and other language processing systems, software engineering, agents and multiagent systems, game development, robotics, and networking. Formal logics and automatic reasoning are put to use in artificial intelligence, database theory, and software engineering. The course gives students practice in precise thinking and proof methods that play a role in the analysis of algorithms.

Topics include: Propositional Logic and Proofs; Predicate Logic and Proofs; Program Verification; Finite Automata, Regular Expressions; Context-Free Grammars; Turing Machines and Solvability.

Outcomes

  1. Students will understand the concepts and relevance of logic, formal languages and automata theory, and computability.
  2. Students will be able to do mechanical formal proofs, program correctness proofs and solve problems in first-order logic.
  3. Students will be able to solve problems in elementary machine models: designing finite-state, pushdown and turing machines.
  4. Students will be able to solve problems in formal languages: writing regular expressions, regular grammars, and context-free grammars.

Grading

Quizzes: 25%
Assignments: 15%
Midterm + Final: 60% (highest score counts 35%; lowest score counts 25%)

Quizzes and exams are closed book. We'll have weekly quizzes and assignments. The lowest quiz grade will be dropped. No make-up quizzes will be offered.
Assignments must be performed individually. No extensions will be granted for assignments as we will discuss the solutions in class. Group work is NOT allowed.
Any deviation from this policy will be considered a violation of the GMU Honor Code. The CS Department has specific CS Honor Code Policies.
Please, no laptops in class!

In order to receive a passing grade in this class, each student will also meet at least once with their academic advisor during the semester. The form that must be turned in TO ME (hardcopy and signed by your advisor) is here:

  • Academic Year Check List

    Communication

    We use Piazza to communicate. Technical questions, and questions in general about the material discussed in class, should be posted on Piazza. Clarifying questions on assignments should also be posted on Piazza. Do NOT post your assignment solutions on Piazza. Do NOT use email for technical questions. Your questions are likely to be of interest to other students as well! Come see me or the GTA during office hours to discuss in person. If you do send me an email, you are required to use your mason account to communicate with me. I mantain a course webpage with the schedule of classes. Assignments and readings will be posted on the Schedule of Classes. Grades will be recorded on Blackboard. Further instruction on how to submit assignments will be provided.

    Use of Electronics in Class and Attendance

    Please, no laptops in class. This is a firm rule, and includes phones, tablets and electronics in general! Without these distractions, you’ll have a superior learning experience during lectures. Regular attendance is highly recommended! If you need a computer to take notes, please talk to me. For disability services, please contact the office of disability services.