## Logistics

### Contact

- 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 |

### Textbook

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.

## Lectures

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.

## Sections

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] |

## Assignments

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.

## Exams

### 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:

- a set of practice problems and solutions;
- a previous midterm and solutions.

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:

- a set of practice problems and solutions;
- a previous final and solutions.

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

## Grading

### 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*.