Prerequisites
CS211 and Math 125 (C or better in both).Content
This course is an introduction to two kinds of formal systems - languages (which are treated as sets of strings) 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.Objectives and 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, prove program correctness for simple programs, and solve problems in first-order logic.
Will be able to solve problems in elementary machine models: designing finite-state automata, pushdown automata and Turing machines.
Will be able to solve problems in formal languages: writing regular expressions, regular grammars, and context-free grammars.Textbook
Title: Logic and Languages Models for Computer Science, 3rd edition.
Authors: Dana Richards and Henry Hamberger
Available at the campus bookstore
Note that the 3rd edition is substantially different from the 2nd.
Zoom Meetings
The lectures and all office hours will meet virtually, using Zoom. I do not intend to be in my office this semester. You will need to register one time (only) before you can attend a lecture. You can find the meeting link through Blackboard: click on Tools, then Zoom. The meeting ID is 926 5467 1840. If we ever have problems with Zoom, we will move to Blackboard Collaborate Ultra. The same holds for Office hours, but it is a separate meeting ID. Register once for Monday office hours (998 6140 6481), and once for Tuesday office hours (990 9294 8975).Webcams
I will not insist on the use of cameras during class time, but I strongly encourage it. The more people that use them, the more engaging the experience will be for us all. Cameras are turned on by default as you join the meetings.Piazza
I will answer all questions on piazza, rather than by email. I realize that some posts need to be private, but when in doubt, I encourage you to make your posts public! Everyone will benefit from your questions, and I prefer that we all learn from them. Generally, I'm not that worried about questions that give hints. (Within reason.) Please note: piazza is changing their business model. If they ask you for money, you should feel no obligation to provide that.Gradescope
Quizzes, homeworks and exams will all be submitted through Gradescope. You can find gradescope through Blackboard: click on Tools, then gradescope. You should also be able to access it directly from the gradescope website, if you use your GMU login. When submitting an assignment, please mark each question with the appropriate question number, as this makes grading much easier.Overleaf
I will release the assignments on overleaf. This is a web-based platform for writing latex documents. You do not need special software, and I will not insist that you use latex to write your answers. You can simply view the PDF from the webpage, and submit answers to Gradescope in whatever format you like. However, I encourage you to use latex - it is fairly easy, and produces nice PDFs. To do that, just copy the project that I've shared, and edit.
Grading
Quizzes -- 10%
Homeworks -- 30%
Exams -- 60%
Of these exams the highest score will count 35%, and the lowest 25%.Homework
Homework will be assigned each week. The two lowest homework grades will be dropped.
Suggestions: It will be very hard to do well in this course if you do not do all of the homework by yourself, including any optional problems. You are strongly encouraged to do all of the problems, and to ask questions, in class and in office hours, when you do not understand any of them. Don't start the homework the day before it is due!Quizzes
Quizzes are short: 1-3 questions, multiple choice or fill-in-the-blank. You will need a laptop or phone to answer the questions, as the results will be tallied immediately. Each single quiz is worth < 1% of your grade. They will be given at the start of class (don't be late!), typically every other class period. They will cover the previous 1 or 2 lectures, and mainly serve to help me gauge what the students have understood, and what needs further explanation.Exams
All testing is closed book, and notes are not permitted. The two exams, including the final, each cover about a half of the semester. The final is not cumulative.
The midterm is Wednesday, March 3rd, in class.
The final is Wednesday, 5/5, 1:30-4:15pm. .CS330 Adviser Forms
It is a departmental requirement that students in CS330 must see their adviser and discuss their degree progress. The form can be downloaded here. Be sure to fill out the form before seeing your adviser, if you are meeting virtually. This semester, I believe it is also OK to communicate by email. Note, if you do it earlier in the semester, you will be more likely to connect with your adviser, and you will have more time to correct any problems. If you wait until the last week, your adviser might not be available. Students not fulfilling this requirement will receive an Incomplete grade. (Non-majors are not included.)