Professor: Cem Evrendilek
Email NetID: cevrendi
Hours: 13:30-14:30 Wednesday
Phone: (703) 993-1258
Office: Nguyen Engr. Bldg. 4423

Assistants: (see Piazza for hours)

GTA: Xue Yu Chao (xyu21)
UTA: tbd

Prerequisites: CS211 and MATH125 (C or better in both)
Textbook: Hamburger and Richards, Logic and Language Models for Computer Science, Fourth Edition
Other requirements:
A scanner, camera, or digital drawing tool to use to prepare digital uploads of homework

Lectures: Lectures will be held in-person; Lecture Material will be made available via Blackboard.
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 obligated to provide donations.
Blackboard to view grades and course materials.
GradeScope for exam grades, quizzes, and homework assignment turn-in.

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

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.

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: 30%

• Homework will be assigned weekly.
• The lowest homework score is dropped.
• Part of the homework assignment will be posted on GradeScope and will be graded.
• Part of the homework, shown on the schedule below, is for practice only and will not be collected.

• Quizzes: 10%

• Quizzes will be weekly except when displaced by exams.
• The lowest two quiz scores are dropped.
• Quizzes are open book and open notes, but individual and not open Internet (except as necessary for taking and submitting the quiz).
• Quizzes will be 30 minutes, open on GradeScope Friday-Sunday every week in which there is a quiz.

• Exams (2): 35% + 25%

• In-class, unless otherwise dictated by circumstances.
• Final exams is not cumulative.
• The higher-scoring exam gets the higher weight, while the lower-scoring exam gets the lower weight.
• Closed book; one sheet of handwritten notes (8.5×11in; double-sided) is permitted.
• Be prepared to show your GMU ID on exam days.

• There will be no programming assignment.

Grading Scale

Grade	A+	A	A-	B+	B	B-	C+	C	C-	D	F
max	↑	97	91	89	87	81	79	77	71	69	59
min	98	92	90	88	82	80	78	72	70	60	↓

Advising Requirement

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.

• Upload your completed and signed form to Blackboard; scan if necessary.
• Failure to complete the advising requirement will result in an Incomplete grade in CS 330.
• Your faculty advisor is a professor who has been assigned to you, not the CS departmental advising staff; look for an email from the department informing you who your faculty advisor is.
• Non CS-majors and graduate students are exempt from the advising requirement.
• Students who are taking CS110 and CS330 during the same semester only need to complete one form.
• Please complete the advising requirement before the midterm date; your advisor may be busy and unable to meet towards the end of the semester.
• What is the goal of the advising requirement?

• To motivate you to plan ahead when choosing classes.
• To encourage you to take the opportunity to ask a faculty member any questions you may have about your academic plans.
• To check that there are no circumstances that you might have overlooked which might hinder your academic progress.
• To advise you of things to consider if you are contemplating graduate school.

Honor Code

All graded work in this class is individual. Any direct contribution on an exam, quiz, or assignment will be treated as a violation of George Mason's Honor Code and the CS Department Honor Code, and will typically result in failing the class.

Some kinds of participation in third-party online study sites violate the GMU Honor code: these include accessing 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 responsibility 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.

Privacy statement

All course materials posted to Blackboard or other course site are private to this class; by federal law, any materials that identify specific students (via their name, voice, or image) must not be shared with anyone not enrolled in this class. In the event that any class meetings need to be held synchronously online, those classes will be recorded to provide necessary information for students in this class. Recordings will be stored on Blackboard and will only be accessible to students taking this course during this semester.

Disability accommodations

Disability Services at George Mason University is committed to providing equitable 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.

Diversity and inclusion

George Mason University promotes a diverse, inclusive, and anti-racist environment, under the belief that a just and equitable learning environment is a strong learning environment. Students are valued as individuals, irrespective of differences in race, ethnicity, national origin, first language, economic status, gender, gender expression and identity, sexual orientation, religion, disability, or age. As an important member of the GMU community, the Department of Computer Science is integral to the goal of cultivating an environment which is committed to inclusion and anti-racism.

Students who prefer to be addressed by a specific name or gender pronouns should share this information with the instructor (he/him). Additionally, name and pronouns can be changed in the GMU records.

Title IX

As a faculty member and designated "Responsible Employee," I am 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).

COVID-19

This class is in person during the current semester. For information regarding the virus and current university policy regarding the virus, consult the Safe Return to Campus page.

Schedule (Tentative)

Week	Topics	Chapter/Parts	Homework
1	Introduction	1
2	Propositional Logic and Proofs	2-3	HW1
3	Proofs by Deduction	3-4	HW2
4	Predicate Logic	4-5	HW3
5	Inferencing with predicates and Mathematical Induction	5-6	HW4
6	Program Verification and Midterm Review	6	HW5
7	Midterm Exam  and Regular Expressions and Grammers	7
8	Regular Expressions and Grammars	7-8
9	Regular Expressions and Grammars	8	HW6
10	RG from RE	8	HW7
11	Finite Automata	9	HW8
12	NFAs, pumping lemma	9	HW9
13	Pumping Lemma and CFGs	10, 11
14	CFGs	11	HW10
15	NPDAs and Turing Machines, Computability	12
Exam week	Final Exam