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.
- 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)
We use the following websites:
- Canvas - reading quizzes
- Gradescope - homework and exams submissions and grades
- Piazza - discussion forums, finding group members
Note that this class (CSE20-B) replaces the previous CSE20-A.
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:
- 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).
- 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
Instructions:
- 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)
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 |
|