CSE20 - Discrete Mathematics for Computer Science, Fall 2016

If you ever wondered "What sort of mathematics do I need for computer science?", this course will provide some of the answers. In particular, you will have the opportunity to learn basic concepts about algorithms, computer arithmetic, number systems, Boolean algebras, logic, proofs, program correctness, loop invariants, modular arithmetic, linear and partial orders, recurrences, and induction, among other things. These are some of the essential ingredients in the toolkit of every computer scientist.


Class times


We follow an online book. Please sign up at zyBooks, Enter code UCSDCSE20LovettFall2016, click "Subscribe". The cost to subscribe is set at $48; any applicable returning student discounts will be applied automatically. Subscriptions will be valid through 12/16/16.

Other optional textbooks which cover similar material:


Homework is due on Mondays, except for weeks with midterms. Submission is online via Gradescope (you should be enrolled already; if not, enroll using your UCSD email and the code M458W9).
Instructions: Homework 1, due 10/3 8am (Solution)
Homework 2, due 10/10 8am (Solution)
Homework 3, due 10/17 8am (Solution)
Homework 4, due 10/31 8am (Solution)
Homework 5, due 11/7 8am (Solution)
Homework 6, due 11/21 8am (Solution)
Homework 7, due 11/30 8am (Solution)

Midterm 1 sample proof questions, not for submission

Discussion forums

We use Piazza for discussion forums: any questions that you have on the material, and finding other students for group study and homework.


Please register your i-Clicker here.


The final grade will be composed as follows: A passing grade in the final exam (at least 50%) is required to pass the class. Letter grades will be assigned as follows:


NOTE: Subject to change throughout the quarter
Date Subject Chapter Slides HW
09/23/2016 Introduction, Class logistics slides
09/26/2016 Propositional logic 1.1-1.3 slides
09/28/2016 Truth tables 1.1-1.3 slides
09/30/2016 Necessary, sufficient conditions; converting truth tables to formulas 1.3-1.4 slides
10/3/2016 Quantifiers and paradoxes 1.5-1.8 slides HW1 due
10/5/2016 Inference rules 1.9-1.10 slides
10/7/2016 Direct proofs 2.1-2.2 slides
10/10/2016 Proof by contraposition, proof by cases 2.3-2.4 slides HW2 due
10/12/2016 Proof by contradiction 2.5 slides
10/14/2016 Knights and knaves slides
10/17/2016 Sets 3.1-3.6 slides HW3 due
10/19/2016 Set builder 3.1-3.6 slides
10/21/2016 Graphs 4.1 slides
10/24/2016 Midterm 1 midterm1 review
10/26/2016 Functions 5.1-5.4 slides
10/28/2016 Functions and set sizes 5.1-5.4 slides
10/31/2016 Relations 6.1-6.4 slides HW4 due
11/2/2016 Induction 7.1-7.2 slides
11/4/2016 Induction 7.1-7.2 slides
11/7/2016 Strong induction 7.3 slides HW5 due
11/9/2016 Recursive definitions 7.4 slides
11/11/2016 Veterans day (no class)
11/14/2016 Midterm 2 midterm2 review
11/16/2016 Algorithms 8.1-8.2 slides
11/18/2016 Modular arithmetics 8.3 slides
11/21/2016 Prime factorization, primality testing 8.4-8.5 slides HW6 due
11/23/2016 GCD and Euclid’s algorithm 8.6 slides
11/25/2016 Thanksgiving (no class)
11/28/2016 Number representations 8.7 slides HW7 due
11/30/2016 Fast exponentiation 8.8 slides
12/2/2016 Final review final review
12/6/2016 Final (section B)
12/9/2016 Final (section A)