CS 2800 is a 4-credit course. The Office of the Registrar has useful information.

Sections

• 1: Manolios, M,W,Th 10:30AM-11:35AM, Hurtig Hall 130
• 2: Tripakis, M,W,Th 1:35PM-2:40PM, Int Village 019
• 3: Manolios, M,W,Th 4:35PM-5:40PM, Int Village 019

For Instructors, TAs, and Tutors, click on Contact Info on your left.

You are required to check for announcements daily.

Rules

• If you don't understand something, please ask questions. We love questions. One of the benefits of attending a university as opposed to reading a book is that you get to interact with faculty.
• Give us feedback. Tell us what works; what doesn't. Tell us what you like about the class and what you don't like.
• In class, stay engaged during the lectures. There are only three hours of lectures a week and we want your undivided attention. Therefore, the use of electronic devices (computers, recording devices, phones, etc) is not allowed, without permission. The only exception is when we takes quizzes using PollEverywhere, which will require that you have a cell phone or laptop. Bring that with you every day.
• We will be fair with everyone, so rest assured that all the students will play by the same rules. To that end, we have clear policies. Make sure you understand them, as they apply to everyone in the class. For example, late homeworks will not be accepted under any circumstances. If you ask us to make an exception for just you, the answer will be no. If you ask us to change the due date for everyone, then we will consider it. Please feel free to question the policies; if you suggest improvements, we can change our policies (and have done so in the past).

Books and Supplies

There is no required book. If you want a reference that also includes a lot of exercises, then consider: Computer Aided Reasoning. Kaufmann, Manolios, Moore. You can order it from here. Please note that the book was written for at least upper level undergraduate students, so expect parts of the book to be hard. Also, in class we use a version of ACL2 that includes contracts and lots of other things that are not mentioned in the book. Nevertheless, this is the standard reference for ACL2 and contains many exercises whose solutions are available online.

Software

We will be using the ACL2s system. Please download it and install it on your machines. It is also installed in the CCIS computer labs, but there are some instructions you should follow to use that installation properly.

Academic Integrity

Read and intimately familiarize yourselves with the Northeastern Academic Integrity policy.

Please read and sign the Course Contract.

Warning: We do not tolerate any violations. If we suspect that you violated the policy, we will report you and the consequences can be as severe as expulsion from the university.

For example, here is something you cannot do, but again, read the full policy, the course contract and see Mitch Wand's Web page on the topic.

Unauthorized Collaboration: The University defines unauthorized collaboration as instances when students submit individual academic works that are substantially similar to one another. While several students may have the same source material, the analysis, interpretation, and reporting of the data must be each individual's independent work.

You can only collaborate with your partners on homework problems. Besides staff, the use of any other sources for homework solutions is a violation of the academic integrity policy.

For quizzes, the electronic device you use can only have the polleverywhere app/webpage open during quizzes. The use of lecture notes, ACL2s, or any other applications during quizzes is a violation of the academic integrity policy. Sharing information with other students, taking quizzes for other students or communicating with other students is also a violation of our academic integrity policy.

Exams

There are exactly two exams. They will take place at the following times:

• Friday, Feb 22, 6-8pm
All Manolios Section 1 & Manolios Section 3 last names I-Z: ISEC 102
All Tripakis & Manolios Section 3 last names A-H: Snell Engineering 108
• Monday, April 8, 6-8pm
All Manolios Section 1 & Manolios Section 3 last names I-Z: ISEC 102
All Tripakis & Manolios Section 3 last names A-H: WVF 020

Let us know by January 15 if you have a conflict.

Grading

Grades will be determined as follows.

• Homeworks: 20%
• Exam 1: 30%
• Exam 2: 30%
• Quizzes: 20%

There are only 2 exams and there is no final.

Quizzes will occur regularly. Be prepared for a short quiz every day. Only a subset of the quizzes might be graded. If you are not present for a quiz or if you do not have Poll Everywhere working, you will get 0 points. We will drop the lowest 10% of quizzes.

Homeworks will be given about once a week. Your homework grade will be based on your top ten homeworks. You will mostly work in groups. We will give you instructions on group sizes and composition. We recommend that you to first try to solve the problems on your own. Then meet with your partners to go over your solutions and solve any unresolved problems. We may only grade a subset of the problems assigned. Homeworks will be due on Tuesday at 10:00PM, unless otherwise noted.

You will spend most of your time in labs working on problems that we distribute in advance. If you solve the problems on your own before lab and are confident in your solutions, there is no need to show up. If you did not have time to solve the problems, or you tried and ran into trouble, then go to lab.

PollEverywhere Instructions

Sign up on the website using your Husky email account here.

In class, we will periodically ask you to respond to a poll. We will either provide a link to the poll or give you our PollEverywhere user name. To join any active poll, either click the provided link--or, if we give you our user name, you can click "Join a Presentation" when logged into PollEverywhere on your laptop or phone (if you install the PollEverywhere app).

If you use the app, log into PollEverywhere using your Husky email.

Grading Notes

• You can take 1 double-sided sheet of paper to each exam.
• You have exactly 1 week after any assignment, quiz, or exam is graded to challenge your grade. After that, we will not change your grade.
• You are responsible for making sure that we entered the right points on Blackboard. If you notice any data entry errors, please inform us right away.
• You must take all exams and quizzes in the section you are registered for. If you take an exam or a quiz in a different section that the one you are registered for, you will not get any points for that exam or quiz.

Prerequisites

CS 1800 and CS 2500.
If you do not have this background you should get the permission of the instructor. Our policy is that we do not grant exemptions if you did not getting passing grades in both the prerequisites: experience has shown that this is the best policy for students.

Schedule

Week	Topics	Readings
Jan 7 L1-L3	Introductions & motivation, slides Syllabus, class webpage, programming review, slides Designing data-driven programs, the ACL2s development environment, slides	None None None
Jan 14 L4-L6	Basic data types, expressions, syntax & semantics of atomic data and associated primitive functions, slides Syntax & semantics of lists, design considerations of the ACL2s core language, contracts, termination, slides, code helpful function, quote, let, Datatypes: enumerated, range, product, record, union, list, (mutually) recursive, slides, code	2.1-2.4 2.5-2.8 2.9-2.11,2.13
Jan 21 L7-L8	Property-based testing, test?, thm, design recipe, program mode and defunc settings, slides, code Property-based testing in industry, Fuzzing, security applications, slides, code	2.12, 2.14-2.16 None
Jan 28 L9-L11	Boolean logic, characterization of formulas, introduction to P=NP, Security: one-time pads, slides Properties of Boolean operators, Proof methods: instantiation, case analysis, equational proofs, truth tables, decision procedures, slides Normal forms, Boolean logic in ACL2s, applications, slides	3-3.2 3.3-3.5 3.6-3.9
Feb 4 L12-L14	Limitations of Boolean logic, intro to equational reasoning for programs, slides Axioms for equality, cons-first-rest axioms, definitional axioms, instantiation, contract checking and completion, slides Equational reasoning in the presences of implications, context vs. theorems, undecidability results, slides	None 4-4.1 4.2-4.4
Feb 11 L15-L17	Reasoning about arithmetic, program equivalence: proving correctness of an exponential-time improvement, numeric reasoning in C & other languages, slides, code Equational reasoning with nested Boolean operators, derived context, how to prove theorems, slides, code The equational reasoning recipe and examples, slides	4.5 4.6 None
Feb 18 L18-L19	Definitions: soundness, termination, contracts, the ACL2s Definitional Principle Termination, measure functions, Review	5.1 None
Feb 25 L20-L22	Using termination to show soundness of common recursions schemes and the design recipe, big-Oh analysis as a refinement of termination Undecidability of halting problem Proof by contradiction, mathematical induction, well-foundnesses, a proof that mathematical induction works, how to extract induction schemes from admissible recursive functions	5.2-5.3 5.4-5.5 6-6.1
Mar 11 L23-L25	Using induction to prove program correctness Data-function-induction trinity, Importance of termination Induction like a professional, reasoning about algorithms: sorting, correctness	6.1 6.2-6.3 6.4
Mar 18 L26-L28	Generalization, lemma generation, dealing with induction failure Intro to reasoning about accumulators Tail recursion: efficiency considerations, how to prove correctness	6.5 6.6 6.6
Mar 25 L29-L31	Accumulator reasoning examples Abstract and algebraic data types Observational equivalence	6.6 8.1-8.2 8.3-8.4
Apr 1 L32-L34	Reasoning about imperative programs: defining the semantics of a simple while language in ACL2s Reasoning about imperative programs using loop invariants; checking such proofs in ACL2s Reasoning about imperative programs and security	9-9.2 9.3 None
Apr 8 L35-L37	Compiler correctness, exam2 review Compiler correctness Mathematical logic: syntax, semantics, proof theory, undecidability, incompleteness
Apr 15 L38	A look back: Logic and the birth of computer science; A look forward: what's next	None