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.

Due to COVID, all meetings (lectures, discussions, office hours) will be remote on zoom.

Note that this class (CSE20-B) replaces the previous CSE20-A.
- Link: https://ucsd.zoom.us/j/91830617044, or connect with meeting ID 918-3061-7044
- Access to meetings requires login with a @ucsd account
- Password: name of class (3 letters + 2 digits)

- Canvas - reading quizzes
- Gradescope - homework and exams submissions and grades
- Piazza - discussion forums, finding group members

Name | Role | Office hours | |
---|---|---|---|

Shachar Lovett | Professor | slovett@ucsd.edu | W 9:30-10:30am |

Yihang Cheng | TA | yic222@ucsd.edu | Th 10am-12pm |

Yuanjun "Dastin" Huang | TA | yuh036@ucsd.edu | Th 8-10am |

Gaurav Mahajan | TA | gmahajan@ucsd.edu | W 2-3pm |

Ritwik Vatsyayan | TA | rvatsyay@ucsd.edu | F 3-5pm |

Nirmal Agnihotri | tutor | nagnihot@ucsd.edu | Sat 5-7pm |

Benny Cai | tutor | j1cai@ucsd.edu | Tu 9-11am |

Rachel Cai | tutor | rac001@ucsd.edu | Tu 1-3 |

Stefanie Dao | tutor | ctdao@ucsd.edu | Th 3-5pm |

Nora Yinxuan Du | tutor | y5du@ucsd.edu | Sun 9-11am |

Roger Ji | tutor | roji@ucsd.edu | M 2:30pm-4:30pm |

Ethan Lan | tutor | etlan@ucsd.edu | F 5-7pm |

Yiming Zhao | tutor | yiz060@ucsd.edu | Tu 3-5pm |

What | When |
---|---|

Lectures | MWF 11-11:50am |

Discussion B01 | Tu 11-11:50am |

Discussion B02 | Tu 12-12:50pm |

Discussion B03 | W 1-1:50pm |

Discussion B04 | F 1-1:50pm |

This book is on reserve in the library and is also available in hardcopy at the UCSD Bookstore or many online retailers, and there are also options to purchase it as an e-book. Some other

- Essentials of discrete mathematics, David Hunter.
- Discrete Mathematics with Applications, Susanna Epp.
- Fundamentals of Discrete Math for Computer Science: A Problem-Solving Primer, Tom Jenkyns and Ben Stephenson. The book is available for free download from a UCSD internet connection here.

Homeworks are due every week by **Monday 11am**, except for midterm and final weeks.

Submission is online via Gradescope (you should be enrolled already; if not, enroll using your UCSD email and the code 9Y36BR).

Submission is online via Gradescope (you should be enrolled already; if not, enroll using your UCSD email and the code 9Y36BR).

- Homework 1, due 10/12 11am, solution
- Homework 2, due 10/19 11am, solution
- Homework 3, due 10/26 11am, solution
- Homework 4, due 11/10 11am, solution
- Homework 5, due 11/16 11am, solution
- Homework 6, due 11/23 11am, solution
- Homework 7, due 12/02 11am, solution
- Homework 8, due 12/09 11am, solution

- Homework should be solved in
**groups of 3-4 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 attend discussion or office hours).
- Your homework grade will be the average of the best 6 grades (out of 8)

Review quizzes are due every week by **Friday midnight**, except for midterm and final weeks.

- Reading quiz 1, due 10/9 midnight
- Reading quiz 2, due 10/16 midnight
- Reading quiz 3, due 10/23 midnight
- Reading quiz 4, due 11/6 midnight
- Reading quiz 5, due 11/13 midnight
- Reading quiz 6, due 11/20 midnight
- Reading quiz 7, due 11/30 midnight
- Reading quiz 8, due 12/04 midnight

- Reading quizzes are
**individual**. - The goal of the reading quizzes is to test you on the reading material for the week, and make sure that you read and understood all of it. They are not supposed to be specifically challenging or difficult.
- Your review quizzes grade will be the average of the best 6 grades (out of 8)

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

The final grade will be composed as follows:

- Final 30%
- Midterm 30% (best out of 2)
- Homework 30% (best 6 out of 8)
- Reading quizzes 10% (best 6 out of 8)

- 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%

- Week 1: video: [mp4] slides: [pptx] [pdf]
- Week 2: video: [mp4] slides: [pptx] [pdf]
- Week 3: video: [mp4] slides: [pptx] [pdf] (see also [mp4] [pptx] [pdf])
- Week 4: video: [mp4] slides: [pptx] [pdf]
- Week 5: video: [mp4] slides: [pptx] [pdf]
- Week 6: video: [mp4] slides: [pptx] [pdf]
- Week 7: video: [mp4] slides: [pptx] [pdf]
- Week 8: video: [mp4] slides: [pdf]
- Week 9: video: [mp4] slides: [pdf]
- Week 10: video: [mp4] slides: [pdf]

Following are the practice questions for the midterms:

- Practice Midterm 1
- Midterm 1 Review: video: [mp4]
- Practice Midterm 2
- Practice Midterm 2 Solutions
- Midterm 2 Review: video: [mp4]

Lecture | Date | Topic | Assignments | Reading | Slides | Worksheet | Videos |
---|---|---|---|---|---|---|---|

1 | 10/2/2020 | Introduction | Section 2.1, Definition 1 and Definition 7 (and paragraph following each definition) | [pptx] [pdf] | [pdf] | [mp4] | |

2 | 10/5/2020 | Sets and recursive definitions | Section 5.3, Definition 1 (Strings), Example 5 (p. 349), and Example 7 (p. 350) | [pptx] [pdf] | [pdf] | [mp4] | |

3 | 10/7/2020 | Number representation | Section 4.2, Examples 1 and 2 (pp. 246-247) | [pptx] [pdf] | [pdf] | [mp4] | |

4 | 10/9/2020 | Storing numbers in computes | Review quiz 1 due by midnight | [pptx] [pdf] | [pdf] | [mp4] | |

5 | 10/12/2020 | Signed representation and arithmetic | Homework 1 due by 11am | Section 4.2 definition of One's, Two's complement (p. 256). Section 1.2 definition of logic gates and circuits (pp. 20-21). | [pptx] [pdf] | [pdf] | [mp4] |

6 | 10/14/2020 | Truth tables and circuits | Section 1.1 definition of truth table and Tables 1-5 (pp. 4-6). | [pptx] [pdf] | [pdf] | [mp4] | |

7 | 10/16/2020 | Compound propositions | Review quiz 2 due by midnight | Section 1.3 Definitions 1 and 2 | [pptx] [pdf] | [pdf] | [mp4] |

8 | 10/19/2020 | Conditionals | Homework 2 due by 11am | Section 1.1 Definition 5, Definition 6, Example 11 | [pptx] [pdf] | [pdf] | [mp4] |

9 | 10/21/2020 | Predicates and quantified statements | Section 1.4 Definitions 1 (p. 40) and 2 (p. 42), Table 2 (p 47), Examples 21-22 (pp. 47-48) | [pptx] [pdf] | [pdf] | [mp4] | |

10 | 10/23/2020 | Nested quantifiers | Review quiz 3 due by midnight | Section 2.1 Definitions 8 and 9 (p. 123). Section 1.5 Example 1 (p. 57) and Example 4 (p. 59) | [pptx] [pdf] | [pdf] | [mp4] |

11 | 10/26/2020 | Universal generalization | Homework 3 due by 11am | Section 1.5 Table 1 (p. 60) | [pptx] [pdf] | [pdf] | [mp4] |

12 | 10/28/2020 | More proof strategies | [pptx] [pdf] | [pdf] | [mp4] | ||

13 | 10/30/2020 | Review session before midterm | [pptx] [pdf] | [pdf] | [mp4] | ||

10/31/2020 | Midterm 1 | ||||||

14 | 11/2/2020 | Sets: general definitions and proofs | Section 2.1, Definitions 1-3 (pp. 116-119), Definitions 6-8 (pp. 121-123); Section 2.2 Definitions 1-5 (pp. 127-129) and Table 1 (p. 130) | [pptx] [pdf] | [pdf] | [mp4] | |

15 | 11/4/2020 | Induction | Section 5.3 Definition of Structural Induction | [pptx] [pdf] | [pdf] | [mp4] | |

16 | 11/6/2020 | More Induction | Review quiz 4 due by midnight | [pptx] [pdf] | [pdf] | [mp4] | |

17 | 11/9/2020 | Mathematical Induction | Homework 4 due by 11am | Section 5.1 Example 1 (p. 316) | [pptx] [pdf] | [pdf] | [mp4] |

11/11/2020 | No class (Veterans day) | ||||||

18 | 11/13/2020 | Strong induction | Review quiz 5 due by midnight | Section 5.2 Example 4 (pp. 337-338) | [pptx] [pdf] | [pdf] | [mp4] |

19 | 11/16/2020 | Primes and Rationals | Homework 5 due by 11am | Section 4.3 Example 2 Section (p. 258), Section 1.7 Example 9 (p. 86) | [pptx] [pdf] | [pdf] | [mp4] |

20 | 11/18/2020 | Cardinality | Definitions 1,2,5,7,8 Section 2.3 | [pptx] [pdf] | [pdf] | [mp4] | |

21 | 11/20/2020 | Countably infinite sets | Review quiz 6 due by midnight | Definition 3, Example 1 Section 2.5 (p. 171) | [pptx] [pdf] | [pdf] | [mp4] |

22 | 11/23/2020 | Uncountable sets | Homework 6 due by 11am | Example 5 Section 2.5 (pp. 173-174) | [pptx] [pdf] | [pdf] | [mp4] |

23 | 11/25/2020 | Reals vs Rationals | Uncountable sets (pp. 173-176) | [pptx] [pdf] | [pdf] | [mp4] | |

11/27/2020 | No class (Thanksgiving) | ||||||

24 | 11/30/2020 | Proof workshop | Review quiz 7 due by midnight | [pdf] | [mp4] | ||

25 | 12/2/2020 | Relations | Homework 7 due by 11am | Definitions 1-5 Section 9.1 (pp. 574-578) -Binary Relation, Relation on a Set, Reflexivity, Symmetry, Transitivity | [pptx] [pdf] | [pdf] | [mp4] |

26 | 12/4/2020 | Equivalence Relations | Review quiz 8 due by midnight | Definitions 1, 3 Section 9.5 (p. 609), Definition of partition, Section 9.6 (p. 612) | [pptx] [pdf] | [pdf] | [mp4] |

27 | 12/7/2020 | Clustering | Homework 8 due by 11am | [pptx] [pdf] | [pdf] | [mp4] | |

28 | 12/9/2020 | Equivalence Relations (contd) | [pptx] [pdf] | [pdf] | [mp4] | ||

29 | 12/11/2020 | Final review | [pptx] [pdf] | [mp4] | |||

12/12/2020 | Midterm 2 | ||||||

12/15/2020 | Final |