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

Instructors

Role Name Email Office hours
Instructor (sections A,B) Prof. Shachar Lovett slovett@ucsd.edu M,F 10-11, CSE 4234
Instructor (section C) Prof. Miles Jones mej016@ucsd.edu W 10-11, 2-3, CSE 2128
TA Kaave Hosseini skhossei@ucsd.edu T 4-6, CSE 4217
TA Sankeerth Rao skaringu@ucsd.edu Th 2-4, CSE 4217
TA Amer Sinha amsinha@ucsd.edu M 12-2, CSE basement B260a
TA Yan Shu yashu@ucsd.edu F 12-2, CSE basement
TA Yunli Wang yuw258@ucsd.edu T 10-12, CSE basement B275
TA Jiapeng Zhang jiz173@ucsd.edu Th 4-6, CSE 4217
Tutor Rachel Ann Keirouz rkeirouz@ucsd.edu Th 11-1, CSE basement
Tutor Qing Huang qih008@ucsd.edu M 12-1 and 5-6, 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:

Homework

Homework is due on Tuesdays, except for weeks with midterms. Homework should be solved in groups of 3-4 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: A passing grade in the final exam (at least 50%) is required to pass the class. Letter grades will be assigned as follows:

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.1-1.3 slides slides
09/30/2015 Truth tables 1.1-1.3 slides,slides slides,slides
10/2/2015 Necessary, sufficient conditions; from truth tables to formulas 1.3-1.4 slides slides
10/5/2015 Quantifiers and paradoxes 1.5-1.8 slides slides
10/7/2015 Derivation rules 1.9-1.10 slides slides
10/9/2015 Direct proofs 2.1-2.2 slides slides
10/12/2015 Proof by contraposition, proof by cases 2.3-2.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.1-3.6 slides slides
10/23/2015 Set builder 3.1-3.6 slides slides
10/26/2015 Graphs 4.1 slides slides
10/28/2015 Functions 5.1-5.3 slides slides
10/30/2015 Functions and set sizes 5.1-5.3 slides slides
11/2/2015 Relations 6.1-6.3 slides slides
11/4/2015 Induction 7.1-7.2 slides slides
11/6/2015 Induction 7.1-7.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.4-7.5 slides
11/16/2015 Midterm 2
11/18/2015 Algorithms 8.1-8.2 slides
11/20/2015 Modular arithmetics 8.3 slides
11/23/2015 Prime factorization, primality testing 8.4-8.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)