CSE20  Discrete Mathematics for Computer Science
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.
PLEASE FILL THE
ANONYMOUS FEEDBACK
ON THE CLASS. WE WANT TO HEAR WHAT YOU THINK.
Class times
 Section A: class MWF 22:50, Center 113; discussion W 55:50, Ledden auditorium
 Section B: class MWF 33:50, Center 113; discussion M 99:50, Center 105
 Section C: class MWF 88:50, Center 105; discussion M 44:50, Center 212
Instructors
Role 
Name 
Email 
Office hours 
Instructor (sections A,B) 
Prof. Shachar Lovett 
slovett@ucsd.edu 
M,F 1011, CSE 4234 
Instructor (section C) 
Prof. Miles Jones 
mej016@ucsd.edu 
W 1011, 23, CSE 2128 
TA 
Kaave Hosseini 
skhossei@ucsd.edu 
T 46, CSE 4217 
TA 
Sankeerth Rao 
skaringu@ucsd.edu 
Th 24, CSE 4217 
TA 
Amer Sinha 
amsinha@ucsd.edu 
M 122, CSE basement B260a 
TA 
Yan Shu 
yashu@ucsd.edu 
F 122, CSE basement 
TA 
Yunli Wang 
yuw258@ucsd.edu 
T 1012, CSE basement B275 
TA 
Jiapeng Zhang 
jiz173@ucsd.edu 
Th 46, CSE 4217 
Tutor 
Rachel Ann Keirouz 
rkeirouz@ucsd.edu 
Th 111, CSE basement 
Tutor 
Qing Huang 
qih008@ucsd.edu 
M 121 and 56, CSE basement B275 
Textbook
We use an online book. Please sign up at
zyBooks, Enter code UCSDCSE20Fall2015, click "Subscribe".
The cost to subscribe is set at $40; any applicable returning student discounts will be applied automatically. Subscriptions will be valid through 01/02/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 Tuesdays, except for weeks with midterms. Homework should be solved in groups of 34 students. Submission is online via
TED,
one submission per group. No collaboration or discussion is allowed outside the groups.
Discussion forums
Please use
TED
for discussion forums: any questions that you have on the material, and finding other students for group study and homework.
Grading
The final grade will be composed as follows:
 Final exam: 40%
 Midterms: 30% (best out of two)
 Homework: 20% (2 lowest grades dropped)
 Online quizzes: 5% (3 misses allowed)
 Clicker participation: 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: 88.0%  100%
 B: 75.0%  87.9%
 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 (sections A/B) 
Slides (sections C) 
09/25/2015 
Introduction, Class logistics 

slides 
slides 
09/28/2015 
Propositional logic 
1.11.3 
slides 
slides 
09/30/2015 
Truth tables 
1.11.3 
slides,slides 
slides,slides 
10/2/2015 
Necessary, sufficient conditions; from truth tables to formulas 
1.31.4 
slides 
slides 
10/5/2015 
Quantifiers and paradoxes 
1.51.8 
slides 
slides 
10/7/2015 
Derivation rules 
1.91.10 
slides 
slides 
10/9/2015 
Direct proofs 
2.12.2 
slides 
slides 
10/12/2015 
Proof by contraposition, proof by cases 
2.32.4 
slides 
slides 
10/14/2015 
Proof by contradiction 
2.5 
slides 
slides 
10/16/2015 
Knights and knaves; midterm review 

slides 
slides 
10/19/2015 
Midterm 1 


10/21/2015 
Sets 
3.13.6 
slides 
slides 
10/23/2015 
Set builder 
3.13.6 
slides 
slides 
10/26/2015 
Graphs 
4.1 
slides 
slides 
10/28/2015 
Functions 
5.15.3 
slides 
slides 
10/30/2015 
Functions and set sizes 
5.15.3 
slides 
slides 
11/2/2015 
Relations 
6.16.3 
slides 
slides 
11/4/2015 
Induction 
7.17.2 
slides 
slides 
11/6/2015 
Induction 
7.17.2 
slides 
slides 
11/9/2015 
Strong induction 
7.3 
slides 
slides 
11/11/2015 
Veterans day (no class) 


11/13/2015 
Recursive definitions; midterm review 
7.47.5 
slides 
11/16/2015 
Midterm 2 


11/18/2015 
Algorithms 
8.18.2 
slides 
11/20/2015 
Modular arithmetics 
8.3 
slides 
11/23/2015 
Prime factorization, primality testing 
8.48.5 
slides 
11/25/2015 
GCD and Euclidâ€™s algorithm 
8.6 
slides 
11/27/2015 
Thanksgiving (no class) 


11/30/2015 
Number representations 
8.7 
slides 
12/2/2015 
Fast exponentiation 
8.8 
slides 
12/4/2015 
Final review 


12/7/2015 
Final (section C) 


12/9/2015 
Final (section A) 


12/11/2015 
Final (section B) 

