Assistants: (see Piazza for hours and contact info)
TBA
Prerequisites:
CS211 and MATH125 (C or better in both)
Textbook:
Hamburger and Richards,
Logic and Language Models for Computer Science,
Fourth Edition
Lectures: Lectures will be held in-person.
Course resources:
Piazza for questions and discussion. Please note that while Piazza requests donations, it is due to Piazza's business model independent from any input from the university; students should not feel any obligation to provide donations.
Canvas to view grades and course materials, and to take online quizzes.
GradeScope for feedback on exams and in-class assessments.
Schedule: see below for schedule; subject to change.
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
| Grade | A+ | A | A- | B+ | B | B- | C+ | C | C- | D | F |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Min Score | 98 | 92 | 90 | 88 | 82 | 80 | 78 | 72 | 70 | 60 | ↓ |
It is a departmental requirement that all undergraduate Computer Science students taking CS330 must speak with their faculty advisor during the semester and submit an advising form (found here) documenting their visit.
All graded work in this class is individual. Any direct contribution on an exam, quiz, or assessment will be treated as a violation of George Mason's Academic Standards Code and the CS Department Honor Code, and will typically result in failing the class.
Generative AIs (including but not limited to ChatGPT, Copilot, Gemini, or PatriotAI) should not be used to assist in the completion of any graded coursework. Any assignment solved with the help of such an AI, or derived from an AI-based solution, would be considered unauthorized assistance and would be in violation of the Academic Standards Code. Much like using calculators to perform arithmetic, you would not learn the skill if you used a tool to solve a problem for you, and you should not present work as your own unless you have done it yourself. AIs add an additional concern, which is that they may very confidently present incorrect answers as true, which is not helpful to your learning experience.
Some kinds of participation in third-party online study sites violate the GMU Academic Standards Code: these include accessing exam questions for this class which have been uploaded by others; accessing exam or assignment answers for this class; uploading of any of the instructor's materials or exams; and uploading any of your own answers or finished work. It is your resposibility to protect your work, including protecting your computer with a password and avoiding sites which make your work publicly visible. Always consult with the professor before using these sites.
Please respect the importance of upholding the Honor Code, since it affects the meaningfulness of your degree and the degrees of other students. As a practical matter, an understanding of the material presented in this course has a potential to positively impact your ability to acquire computing skills and perform computing skill which will be used in your future careers; you put yourself in the best position to gain that understanding when you rely on your own work.
GMU upholds the Academic Standards of honesty, acknowledgement, and uniqueness of work. Please respect the importance of upholding the Academic Standards Code, since it affects the meaningfulness of your degree and the degrees of other students. As a practical matter, an understanding of logic and proof techniques has a strong potential to impact your ability to land a job and perform well in your future careers; you put yourself in the best position to gain that understanding when you rely on your own work.
Student responsibility: Students are responsible for understanding how these general expectations regarding academic standards apply to this course and any assignment or exam they participate in; students should ask their instructor for clarification on any aspect that is not clear to them.
Privacy statement
All course materials posted to Canvas or other course site are private to this class. By the Family Educational Rights and Privacy Act (FERPA), a federal law which governs the disclosure of educational records for eligible students, the professor and TAs cannot share academic documents with a different student, and any materials that identify specific students (via their name, voice, or image) must not be shared with anyone not enrolled in this class. Students must use their GMU email account to receive communications related to this class.
Student responsibility: Students are responsible for checking their GMU email regularly for course-related information, and/or ensuring that GMU email messages are forwarded to an account they do check.
Disability accomodations
Disability Services at George Mason University is committed to providing access
to learning opportunities for all students by upholding the laws that ensure equal treatment
of people with disabilities. Students seeking accommodations for this class, please first
visit Disability Services (ods@gmu.edu;
703-993-2474) for detailed information about the
Disability Services registration process. Then please discuss the approved accommodations with
the instructor. The Disability Services office can be found in Student Union Building I (SUB I),
Suite 2500.
Student responsibility: Students are responsible for registering with Disability Services and communicating about their approved accommodations with their instructor in advance of any relevant class meeting, assignment, or exam.
Title IX
As a faculty member and designated "Responsible Employee," the instructor is required to report all disclosures of sexual assault, interpersonal violence, and stalking to Mason's Title IX Coordinator, per university policy 1412. Students who wish to speak with someone confidentially, should contact the Student Support and Advocacy Center (ssac@gmu.edu; 703-993-3686) or Counseling and Psychological Services (caps@gmu.edu; 703-993-2380). Assistance may also be sought from GMU's Title IX Coordinator (titleix@gmu.edu; 703-993-8730).
Student opportunity: If you prefer to speak to someone confidentially, please contact one of Mason’s confidential employees in Student Support and Advocacy (SSAC), Counseling and Psychological Services (CAPS), Student Health Services (SHS), and/or the Office of the University Ombudsperson.
Schedule
| Week | Date | Topic | Assignments/Notes |
|---|---|---|---|
| Week 1 | Jan 18-24 | ||
| Introduction; Mathematical Preliminaries, Sections 1.1-1.6. | First day of class Wednesday, Jan 21 | ||
| Week 2 | Jan 25-31 | Propositional Logic, Sections 2.1-2.7. | Practice HW 2.4, 2.7a, 2.8, 2.9, 2.11 |
| Quiz 1 (Intro/Prop Logic) open Wed-Thu | |||
| Week 3 | Feb 1-7 | Proof by Deduction, Sections 3.1-3.9. | Practice HW 3.10 (1st-4th), Prove Transitive/Contrapositive/Trivial/Vacuous/Alt Elim/Contradiction Elim, 3.8 |
| Assessment 1 (Prop Logic); Quiz 2 (Deduction) open Wed-Thu | |||
| Week 4 | Feb 8-14 | Predicate Logic, Sections 4.1-4.5. | Practice HW 4.1, 4.3, 4.7, 4.10a,b |
| Assessment 2 (Deduction); Quiz 3 (Pred Logic) open Wed-Thu | |||
| Week 5 | Feb 15-21 | Mathematical Induction, Sections 5.1-5.5. | Practice HW 5.2-5.4, 5.9 |
| Assessment 3 (Pred Logic); Quiz 4 (Induction) open Wed-Thu | |||
| Week 6 | Feb 22-28 | Program Verification, Sections 6.1-6.4. | Practice HW 6.2-6.4, 6.6, 6.7 |
| Assessment 4 (Induction); Quiz 5 (Prog Verif) open Wed-Thu | |||
| Week 7 | Mar 1-7 | Midterm Exam review | |
| Midterm Exam | Midterm covers material from chapters 1-6 | ||
| Week 8 | Mar 8-14 | No Classes | Spring Recess |
| Week 9 | Mar 15-21 | Language Basics; Regular Languages, Chapter 7 + Sections 8.1-8.2 | Practice HW 7.4, 7.5, 7.12, 7.15, 8.2, 8.3, 8.5, 8.6 |
| Quiz 6 (Langs/RLs) open Wed-Thu | |||
| Week 10 | Mar 22-28 | Regular Expressions/Regular Grammars, Sections 8.2-8.5 | Practice HW 8.8, 8.9, 8.11, 8.12 |
| Assessment 5 (Langs/RLs); Quiz 7 (REs/RGs) open Wed-Thu | |||
| Week 11 | Mar 29-Apr 4 | Regular Grammar Conversions, Sections 8.5,8.6 | Practice HW 8.14, 8.15 |
| Assessment 6 (REs/RGs); Quiz 8 (RG Conv) open Wed-Thu | |||
| Week 12 | Apr 5-11 | Finite Automata, Sections 9.1-9.4,9.8 | Practice HW 9.7, 9.5, 9.16, 9.17 |
| Assessment 7 (RG Conv); Quiz 9 (FA) open Wed-Thu | |||
| Week 13 | Apr 12-18 | Nondeterministic Finite Automata/Properties of Regular Languages, Sections 9.5-9.7 | Practice HW 9.8, 9.9, 9.25 |
| Assessment 8 (FA); Quiz 10 (NFA/Prop RLs) open Wed-Thu | |||
| Week 14 | Apr 19-25 | Context-Free Grammars, Sections 10.1-10.4 | Practice HW 10.1, 10.2, 10.8 |
| Assessment 9 (NFA/Prop RLs); Quiz 11 (CFGs) open Wed-Thu | |||
| Week 15 | Apr 26-May 2 | Pushdown Automata/Turing Machines, Sections 11.1,11.2, 12.2 | Practice HW 11.1, 11.4, 11.6, 11.9a (NPDA are allowed) |
| Assessment 10 (CFGs); Quiz 12 (PDA/TMs) open Wed-Thu | |||
| Week 16 | May 3-9 | Final Exam review | Last day of class (Monday) |
| Final covers material from chapters 7-12 | |||
| Exam Week | May 6-13 | Reading Day May 5 | |
| Final Exam Section 001 | Monday, May 11, 10:30am-1:15pm |