# Resources

## Table of Contents

## A Guide to CSE 311

Welcome to CSE 311! We hope you’re excited to learn about so many exciting new topics this quarter. CSE 311 is often the first upper level CS class many people take. The workload, content, and problem-solving in this course might be different than previous courses you’ve taken before. We’ve put together a compilation of resources to help you succeed in this course.

The first set of resources are things you’ll refer to often throughout the course. These include things like how to utilize LaTeX in 311, proof techniques for this course, and skills that will be useful throughout the quarter.

The second set of resources will consist of handouts, reference sheets, and guides for particular concepts throughout the course. As we go through all the concepts in this course, the resources will be updated regularly!

If there are any resources you’d like to see on here or any questions you have, feel free to reach out to course staff!

## General Course Resources

### Good Skills to Develop Through CSE 311

#### Problem Solving:

- Try to start homeworks early and working through problems with peers
- Be open to asking questions and try to communicate with TAs and peers
- When stuck on a problem, try to review material and example about this problem then maybe you can get some idea about this problem

#### Communication:

- Come to section weekly and meet and discuss problems with students and TAs there
- Post questions on Ed. When you have a question, you can always post the question on Ed and if you have a personal question, you can post a private question.
- Come to Office hours. In office hours, you can talk to TAs and professors directly and this may help you solve your problems. Communication is important and if you have any questions and thoughts about this course please do not hesitate to tell us.

#### Collaboration:

Please talk to each other and work with each other. Forming study groups and meeting with them regularly might be a good choice. Always ensure that collaboration is within our guidelines:

- Do not take away any notes or screenshots during your discussion.
- Take a 30 minute break before writing up your solution individually.
- Cite the names of all of your collaborators somewhere in your writeup.

#### How to get “unstuck”:

A general rule of thumb for when you feel really stuck on a problem. Work on a problem for ~30 min. If you can’t figure it out, take a break and come back to it. Work on it for ~30 min. If you still can’t figure it out, work on it for ~30 min with a study partner. If you still can’t get it, come to Office Hours and TAs will be happy to help you out.

### Tips and Techniques to Navigating Proofs

- Proof techniques from this course.
- Proof tips for navigating difficult proofs in general.

### Guides to LaTeX for CSE 311

You are not required to typeset your homework solutions; however, it is an easy way to improve the legibility of your documents. Many Allen School students learned to typeset in this course. LaTeX has often been used in other courses such as CSE 312, CSE 446, and more!

LaTeX is the standard tool for typesetting mathematical materials. While it takes some time to learn, it will likely pay for itself in the long run. You can even use LaTeX in places like Ed and Facebook Messenger!

These resources may be helpful for you to get started with LaTeX:

Resource | Description |
---|---|

LaTeX Tutorial | |

LaTeX Workshop Slides | A comprehensive “workshop” on what LaTeX is, how to structure a LaTeX document, and common typesetting options. |

311 LaTeX master template | Template LaTeX file that is a great structure to follow for CSE 311 assignments. |

## Concept-Specific Resources

### I. Propositional Logic

(include topics like Propositional Logic, Translation from English to formal Logic, Logical Circuits, Boolean Algebra, etc.)

Resource | Description | Topic |
---|---|---|

Translation Tips Reference Sheet | Tips on how to translate English into formal logic. | Propositional Logic, Translation between English and Formal Logic |

Logical equivalences reference sheet (slides version) | Definitions of logical equivalences (Commutativity, Associativity, De Morgan’s Laws, etc.) | Equivalences |

Boolean algebra reference sheet | Reference sheet containing axioms and theorems useful for boolean algebra. | Boolean Algebra |

### II. Predicate Logic

(include topics like Predicates, Quantifiers, Inference proofs, etc.)

Resource | Description | Topic |
---|---|---|

Inference rules reference sheet (slides version) | Reference sheet containing axioms and rules for doing inference proofs (modus ponens, direct proof, intro/elim, etc.). | Inference Rules |

### III. Sets & Number Theory

(include topics like Sets, Proof by Cases, Modular Arithmetic, Primes and GCD, etc.)

Resource | Description | Topic |
---|---|---|

Sets reference sheet | Reference sheet containing common sets, containment, equality, subsets, and Set Operations | Sets |

English proof style guide | A guide to forming English Proofs, from creating your introduction, to choosing your proof style, to concluding your proof. | English Proofs |

Number theory reference sheet | Reference sheet containing definitions and theorems related to number theory (prime, composite, GCD, mod, etc.) | Division Theorem, Modular Arithmetic, Primes and GCD |

Modular Exponentiation | A guide on how to utilize a quick modular exponentiation algorithm. | Modular Arithmetic |

### IV. Induction

(include topics like Induction, Strong Induction, Structural Induction, etc.)

Resource | Description | Topic |
---|---|---|

Induction templates | Templates to follow when forming arguments for induction, strong induction, and structural induction. | Induction, Strong Induction, Structural Induction |

## Textbook

There is an **optional** textbook relevant to the first 6–7 weeks of the course:

Rosen, Kenneth H. 2007.

Discrete Mathematics and Its Applications. 6th ed. Boston: McGraw-Hill Higher Education. Available at UW Libraries.

Rosen’s text is useful if you like to read ahead or want a resource with many practice problems. Here is a list of relevant chapters, but it might be slightly out of order.

Older (and newer) editions are likely to have most or all of the same content, but the section numbers may be shifted.

## Other Readings

If you would like readings, but do not wish to invest in a textbook (or just want a different perspective), we have some suggested alternatives:

- MIT OpenCourseWare’s textbook. Written in a traditional textbook style.
- Margaret Fleck’s Building Blocks textbook. Written in a conversational style and more like a transcript of a lecture than a textbook.
- Discrete Mathematics on Wikibooks. Useful for quick reviews and references.
- Older CSE 311 websites. You might be able to find different problems and presentations.

Wikipedia has thorough articles on most topics we discuss, but they often go very deep very quickly, making them sometimes hard to read.

With all of these resources, be careful that definitions and notations frequently differ between authors in subtle ways. Even simple sentences do not always mean what you think they mean.