CSE 311 logo

CSE 311 Autumn 2018
Foundations of Computing I



Discussion board: Piazza (sign up)
Use this board to discuss the content of the course. That includes everything except the solutions to current homework problems. When you sign up, make sure to opt out of Piazza Careers to ensure data privacy.
Class mailing list: multi_cse311a_au18@uw
Low traffic, but mandatory. Critical reminders and emergency change of plans will be announced to this list. Enrolled students should be subscribed automatically.
Staff mailing list: cse311-staff@cs
Use the staff mailing list for questions about the course and special circumstances.
Gradebook and dropbox: Canvas
Use Canvas to view your grades and submit all homework assignments.

Meetings and office hours

Section Time Room Staff
A MWF 09:30-10:20 SIG 134 Emina Torlak
B MWF 13:30-14:20 JHN 102 Kevin Zatloukal
AA Th 09:30-10:20 MGH 242 Zhiheng (Frank) Qin
AB Th 09:30-10:20 MGH 288 Oscar Sprumont
AC Th 10:30-11:20 MGH 284 Benjamin MacMillan
AD Th 11:30-12:20 CHL 105 Aditya Saraf
AE Th 12:30-13:20 PCAR 395 Siddharth Iyer Vaidynathan
AF/BF Th 08:30-09:20 SAV 136 Benjamin Lee
AG/BG Th 13:30–14:20 LOW 102 Jason Waataja
BA Th 12:30-13:20 DEM 124 Weihan (Joy) Ji
BB Th 13:30-14:20 SAV 131 Aishwarya Nirmal
BC Th 14:30-15:20 JHN 022 Philip Garrison
BD Th 12:30-13:20 MGH 248 Kush Gupta
BE Th 11:30-12:20 SAV 131 Sarvagya Gupta
Staff Office hours Room
Philip Garrison M 15:00-16:00 CSE 021
Benjamin MacMillan M 16:00-17:30 CSE 021
Jason Waataja T 12:00-13:00 CSE 021
Sarvagya Gupta T 14:00-15:00 CSE 021
Emina Torlak W 10:30-11:30 CSE 596
Weihan (Joy) Ji W 11:30-12:30 CSE 021
Aishwarya Nirmal W 14:30-15:30 CSE 5th floor breakout
Siddharth Iyer Vaidynathan W 15:00-16:00 CSE 4th floor breakout
Zhiheng (Frank) Qin W 17:00-18:00 CSE 4th floor breakout
Oscar Sprumont Th 11:00-12:00 CSE 021
Benjamin Lee F 12:00-13:00 CSE 220
Aditya Saraf F 15:30-16:30 CSE 007
Kush Gupta F 16:30-17:30 CSE 007
Kevin Zatloukal MF 12:45-13:15 CSE 212


There is no required text for the course. For the first 6-7 weeks of the course, the following textbook can be useful: Rosen, Discrete Mathematics and Its Applications, 6th Edition, McGraw-Hill. It is available used through the bookstore, and on short-term loan from the Engineering Library.


Lecture Date Topic Reading
01 Sep 26 Propositional Logic [html, pdf] 1.1
02 Sep 28 Equivalence and Circuits [html, pdf] 1.1-1.2
03 Oct 01 Equivalence and Proofs [html, pdf] 11.1-11.3
04 Oct 03 Boolean Algebra [html, pdf] 11.1-11.3
05 Oct 05 Canonical Forms and Predicate Logic [html, pdf] 1.3-1.4
06 Oct 08 Predicate Logic [html, pdf] 1.5-1.7
07 Oct 10 Inference Rules and Proofs for Propositional Logic [html, pdf] 1.5-1.7
08 Oct 12 Inference Rules and Proofs for Predicate Logic [html, pdf] 1.5-1.7
09 Oct 15 Proof Strategies [html, pdf] 1.5-1.7
10 Oct 17 Set Theory [html, pdf] 2.1-2.3
11 Oct 19 Modular Arithmetic [html, pdf] 3.4-3.6
12 Oct 22 Modular Arithmetic and Applications [html, pdf] 3.4-3.6
13 Oct 24 Primes and GCD [html, pdf] 3.5-3.7
14 Oct 26 Euclidean Algorithm and Modular Equations [html, pdf] 3.5-3.7
15 Oct 29 Modular Exponentiation and Induction [html, pdf] 3.7, 4.1
16 Oct 31 Induction [html, pdf] 4.1
17 Nov 02 Strong Induction [html, pdf] 4.2
18 Nov 05 Recursively Defined Functions and Sets [html, pdf] 4.3
  Nov 07 Midterm Exam  
19 Nov 09 Structural Induction [html, pdf] 4.3
  Nov 12 Veteran’s Day (no class)  
20 Nov 14 Regular Expressions [html, pdf] pp. 817-819
21 Nov 16 Context-Free Grammars [html, pdf] pp. 790-793
22 Nov 19 Relations and Directed Graphs [html, pdf] 8.1, pp. 541-548
  Nov 21 Thanksgiving (no class)  
  Nov 23 Thanksgiving (no class)  
23 Nov 26 Finite State Machines (FSMs) [html, pdf]  
24 Nov 28 FSM Minimization and NFAs [html, pdf]  
25 Nov 30 Relating NFAs, DFAs, and Regular Expressions [html, pdf]  
26 Dec 03 Limitations of DFA, NFA, RegExp [html, pdf]  
27 Dec 05 Cardinality and Uncomputability [html, pdf] 12.5, p.177
28 Dec 07 Undecidability of the Halting Problem [html, pdf]  
  Dec 10 Final Exam  

Videos from the afternoon lecture will be available on Canvas.


Section Date Topic
01 Thu, Sep 27 Propositional Logic [problems, solutions]
02 Thu, Oct 04 Equivalences [problems, solutions]
03 Thu, Oct 11 Predicate Logic and Inference [problems, solutions]
04 Thu, Oct 18 English Proofs and Sets [problems, solutions]
05 Tue, Oct 23 Number Theory [problems, solutions]
06 Thu, Nov 01 Induction [problems, solutions]
07 Thu, Nov 08 Strong Induction and Recursive Sets [problems, solutions]
08 Thu, Nov 15 Structural Induction and Regular Expressions [problems, solutions]
  Thu, Nov 22 Thanksgiving (no class)
09 Thu, Nov 29 CFGs, Relations, DFAs, NFAs, and Minimization [problems, solutions]
10 Thu, Dec 06 Subset Construction, Irregularity, and Cardinality [problems, solutions]


Assignment Out Due
Homework 01 Thu, Sep 27 Wed, Oct 03 at 23:59
Homework 02 Thu, Oct 04 Wed, Oct 10 at 23:59
Homework 03 Thu, Oct 11 Wed, Oct 17 at 23:59
Homework 04 Thu, Oct 18 Wed, Oct 24 at 23:59
Homework 05 Fri, Oct 26 Fri, Nov 02 at 23:59
Homework 06 Thu, Nov 08 Fri, Nov 16 at 23:59
Homework 07 Sat, Nov 17 Mon, Nov 26 at 23:59
Homework 08 Tue, Nov 27 Wed, Dec 05 at 23:59

Use Canvas to upload your solutions to the assignments by the due date and time.

Submit the solution to each problem as a separate pdf file. You can typeset solutions on a computer or scan / photograph handwritten solutions. You are responsible for making sure that your solutions are readable. Typesetting makes that easier.

If you do not see CSE 311 in your Canvas account, please send an email to the cse311-staff@cs mailing list, and we will work it out with you.


Midterm exam

The midterm exam will be held in class on Wednesday, November 07.

The midterm will cover everything up to the end of ordinary induction in Lecture 16 (but not strong induction). It will be closed book and closed notes. You will get lists of inference and equivalence rules on the exam.

To get an idea of the content and length of the exam, take a look at the following material:

There will be a review session on Sunday, November 04 at 15:00-17:00 in SAV 260.

Final exam

The final exam will be held on Monday, December 10 at 14:30-16:20 and 16:30-18:20 in JHN 102.

In the case of a scheduling conflict, students may take the exam at either time but must email the staff (cse311-staff@cs) by Sunday, December 09 indicating when they will take the exam. Students must bring their UW ID and have it ready to be checked during the exam.

The final exam will cover the entire course, but it will emphasize the material not covered on the midterm. As a rough guide, you can expect two thirds of the final to cover the post midterm material.

To get an idea of the content and length of the exam, take a look at the following material:

There will be a review session on Sunday, December 09 at 15:00-17:00 in GWN 301.


Grading scheme

Homework 50%
Midterm exam 15-20%
Final exam 30-35%

Late policy

Assignments must be turned in by the due date and time in order to contribute to your grade. Assignments will not be accepted late. In case of a severe emergency (e.g., hospitalization), contact the course staff (cse311-staff@cs). Unless otherwise noted, all assignments should be submitted via the course dropbox.

Regrade policy

We will entertain questions about grades only for one week after they are posted in the course grade book. Questions about assignment grades should be written and submitted to the staff via email (cse311-staff@cs).

Grading guidelines

Clarity is important

One of the main goals (in fact, maybe the main goal) of CSE 311 is to be able to learn how to express ideas clearly using mathematical formalism.

Style is important

You may lose points for style. Your proofs and explanations should be clear, well-organized and as concise as possible. It is better to err on the side of including too many details. Unfortunately, a lot of this is subjective. Often, students think of proofs as merely either “right” or “wrong”. This would be true if they were expressed in every last detail in a formal logic but not at the level that you will need to write them here. Writing a proof is more like writing an essay. Along these lines, if you are not able to find a complete answer to a problem, you are better off explaining clearly what you’ve done rather than faking a proof.

A picture is not a proof

Pictures and short pieces of pseudo-code can be helpful, but they are not sufficient. Make sure to label everything. Define all the variables you use. Make sure you’ve explained everything clearly in English.

Review your proofs

Try rewriting your proofs. Writing out your answer fully on a piece of scratch paper before writing up the version to hand in really does make a difference. You are more likely to catch mistakes or exceptions, and your proof will be better organized.

Notation is key

Set up good notation. Many of the exercises are phrased almost entirely in English. It will be your job to rephrase them mathematically when necessary. Your proofs will usually begin with something like, “Let S be the set of students taking CSE 311.” Make sure that you’ve clearly defined any variable you use. Choosing good names for your variables is also important.

Academic integrity

Homework should be written up individually. It is okay to discuss problems with a few other students, but you may not write up solutions in a group, and you may not record anything from your discussions.

If you have any doubt about whether your collaboration was appropriate, include a description of your collaboration with your homework submission.

You may not consult the Internet for problems or key-phrases. This includes Google, MathOverflow, reddit, and any other website. You may consult the internet for ideas, definitions, and understanding general concepts.

For additional information and a more detailed discussion, please refer to the Allen School Academic Misconduct Policy.

Extra credit

Homework assignments will often have extra credit problems. They will be scored separately from the regular problems, and they will have relatively little impact on course grades. The main incentive for doing the extra credit problems is for the challenge of doing the problems. Extra credit will be factored into the grade after course grades have already been calculated.