CSE20 - Discrete Mathematics for Computer Science, Fall 2020


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.

Remote meetings

Due to COVID, all meetings (lectures, discussions, office hours) will be remote on zoom. We use the following websites:
Note that this class (CSE20-B) replaces the previous CSE20-A.

Instructors

NameRoleEmailOffice hours
Shachar LovettProfessorslovett@ucsd.eduW 9:30-10:30am
Yihang ChengTAyic222@ucsd.eduTh 10am-12pm
Yuanjun "Dastin" HuangTAyuh036@ucsd.eduTh 8-10am
Gaurav MahajanTAgmahajan@ucsd.eduW 2-3pm
Ritwik VatsyayanTArvatsyay@ucsd.eduF 3-5pm
Nirmal Agnihotritutornagnihot@ucsd.eduTh 5-7pm
Benny Caitutorj1cai@ucsd.eduTu 9-11am
Rachel Caitutorrac001@ucsd.eduTu 1-3
Stefanie Daotutorctdao@ucsd.eduTh 3-5pm
Nora Yinxuan Dututory5du@ucsd.eduSun 9-11am
Roger Jitutorroji@ucsd.eduM 2:30pm-4:30pm
Ethan Lantutoretlan@ucsd.eduF 5-7pm
Yiming Zhaotutoryiz060@ucsd.eduTu 3-5pm

Lectures and discussions

WhatWhen
LecturesMWF 11-11:50am
Discussion B01Tu 11-11:50am
Discussion B02Tu 12-12:50pm
Discussion B03W 1-1:50pm
Discussion B04F 1-1:50pm

Textbook

Required textbook: Discrete Mathematics and its Applications, Kenneth Rosen, McGraw Hill, 7th edition.

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 optional textbooks which cover similar material:

Homework

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).
Instructions:

Reading quizzes

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

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.

Grading

The final grade will be composed as follows: Letter grades will be assigned as follows:

Discussion resources

Schedule

NOTE: Subject to change throughout the quarter
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]
11 10/26/2020 Universal generalization Homework 3 due by 11am Section 1.5 Table 1 (p. 60) [pptx] [pdf] [pdf]
12 10/28/2020 More proof strategies [pptx] [pdf] [pdf]
13 10/30/2020 Review session before midterm Midterm 1 [pptx] [pdf] [pdf]
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)
15 11/4/2020 Induction Section 5.3 Definition of Structural Induction
16 11/6/2020 More Induction Review quiz 4 due by midnight
17 11/9/2020 Mathematical Induction Homework 4 due by 11am Section 5.1 Example 1 (p. 316)
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)
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)
20 11/18/2020 Cardinality Definitions 1,2,5,7,8 Section 2.3
21 11/20/2020 Countably infinite sets Review quiz 6 due by midnight Definition 3, Example 1 Section 2.5 (p. 171)
22 11/23/2020 Uncountable sets Homework 6 due by 11am Example 5 Section 2.5 (pp. 173-174)
23 11/25/2020 More cardinality
11/27/2020 No class (Thanksgiving) Review quiz 7 due by midnight
24 11/30/2020 (Equivalence) Relations Homework 7 due by 11am Definitions 1-5 Section 9.1 (pp. 574-578) -Binary Relation, Relation on a Set, Reflexivity, Symmetry, Transitivity
25 12/2/2020 Modular arithmetic Definitions 1, 3 Section 9.5 (p. 609), Definition of partition, Section 9.6 (p. 612)
26 12/4/2020 Relations and clustering Review quiz 8 due by midnight
27 12/7/2020 TBD Homework 8 due by 11am
28 12/9/2020 TBD
29 12/11/2020 Final review Midterm 2
12/15/2020 Final