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.
Instructors
 Prof: Shachar Lovett, email: slovett@ucsd.edu, office hours: Monday 56pm, Wednesday 56pm, CSE 4234
 TAs:
 Stephanie Chen, email:syc078@ucsd.edu, office hours: Monday 3:304:30pm, CSE 3217; Wednesday 3:304:30pm, CSE 4262
 Kaave Hosseini, email: skhossei@ucsd.edu, office hours: Thursday 122pm, CSE 4217
 Shaida Masoumi, email: tmasoumi@ucsd.edu, office hours: Thursday 12pm, Friday 45pm, CSE 4109
 Sankeerth Rao, email: skaringu@ucsd.edu, office hours: Thursday 10am12pm, CSE 4217
 Christopher Tosh, email:ctosh@ucsd.edu, office hours: Wednesday 24pm, CSE 3217
 Jiapeng Zhang, email: jiz173@ucsd.edu, office hours: Tuesday 911am, CSE 4217
Class times
 Section A: class MWF 1010:50am, Center 212; discussion W 88:50pm, Center 105
 Section B: class MWF 1111:50am, Center 119; discussion M 55:50pm, Center 212
Textbook
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:
 Essentials of discrete mathematics, by Hunter.
 Discrete Mathematics and Its Applications, by Rosen.
 Discrete Mathematics with Applications, by Epp.
 Fundamentals of Discrete Math for Computer Science: A ProblemSolving Primer, by Jenkyns and Stephenson.
The book is available for free download from a UCSD internet connection
here.
Homework
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 should be solved in groups of 34 students (you can change groups for different homeworks).
 Submit only one submission per group.
 No collaboration or discussion outside the groups is allowed (but if you are stuck on a problem, please come to discussion or office hours).
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.
iClicker
Please register your iClicker here.
Grading
The final grade will be composed as follows:
 Final exam: 40% (must pass to pass class)
 Midterms: 30% (2 midterms; best out of two)
 Homework: 20% (7 homeworks; 2 lowest grades dropped)
 Participation + Challenge activities (in textbook): 5% (3 misses allowed)
 Participation in class (using iclicker): 5% (3 misses allowed)
A passing grade in the final exam (at least 50%) is required to pass the class. Letter grades will be assigned as follows:
 A range (A,A,A+): 88.0%  100%
 B range (B,B,B+): 75.0%  87.9%
 C range (C,C,C+): 60.0%  74.9%
 D: 50.0%  59.9%
 F: below 50.0%
Schedule
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.11.3 
slides 
09/28/2016 
Truth tables 
1.11.3 
slides 
09/30/2016 
Necessary, sufficient conditions; converting truth tables to formulas 
1.31.4 
slides 
10/3/2016 
Quantifiers and paradoxes 
1.51.8 
slides 
HW1 due 
10/5/2016 
Inference rules 
1.91.10 
slides 
10/7/2016 
Direct proofs 
2.12.2 
slides 
10/10/2016 
Proof by contraposition, proof by cases 
2.32.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.13.6 
slides 
HW3 due 
10/19/2016 
Set builder 
3.13.6 
slides 
10/21/2016 
Graphs 
4.1 
slides 
10/24/2016 
Midterm 1 

midterm1 review 
10/26/2016 
Functions 
5.15.4 
slides 
10/28/2016 
Functions and set sizes 
5.15.4 
slides 
10/31/2016 
Relations 
6.16.4 
slides 
HW4 due 
11/2/2016 
Induction 
7.17.2 
slides 
11/4/2016 
Induction 
7.17.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.18.2 
slides 
11/18/2016 
Modular arithmetics 
8.3 
slides 
11/21/2016 
Prime factorization, primality testing 
8.48.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) 

