In this class, you will answer these questions by careful mathematical modeling, problem solving, and clear and precise communication.
Week  Tuesday  Wednesday  Thursday  Homework 

0  9/28 First lecture! Intro & Algorithms Sec 3.1, App 3 (Read/watch) Slides Lec B, Slides Lec A 
Start of quarter Due 10/13 for credit  
1  10/3 Number Systems Sec 4.1, 4.2 (Read/watch) Slides Lec B, Slides Lec A 
10/4 Discussion 1 Review Quiz 1 Due 10/4 11pm 
10/5 Circuits Rosen 1.2, 1.1, 1.3 (Read/watch) Slides Lec B, Slides Lec A 
Homework 1 Due 10/6 11pm PDF, source, style 
2  10/10 Propositional logic Rosen 1.1, 1.3 (Read/watch) Slides Lec B, Slides Lec A 
10/11 Discussion 2 Review Quiz 2 Due 10/11 11pm 
10/12 Equivalences Rosen 1.3 (Read/watch) Slides Lec B, Slides Lec A 
Homework 2 Due 10/14 11pm PDF, source, style 
3  10/17 Predicate logic Rosen 1.4, 1.5 (Read/watch) Slides Lec B, Slides Lec A 
10/18 Discussion 3 Review Quiz 3 Due 10/18 11pm 
10/19 Proof strategies Rosen 1.6, 1.7, 1.8 (Read/watch) Slides 
Homework 3 Due 10/21 11pm PDF, source, style 
4  10/24 Proof by contradiction Rosen 1.7, 1.8 (Read/watch) Slides Lec B, Slides Lec A 
10/25 Discussion 4 Review Quiz 4 Due 10/25 11pm 
10/26 Review Practice midterm Slides Lec B, Slides Lec A 
Homework 4 Due 10/28 11pm PDF, source, style image 1 image 2 image 3 image 4 
5  10/31 Midterm Covers up to and including 1.8 
11/1 Discussion 5 Review Quiz 5 Due 11/1 11pm 
11/2 Sets and Summations Rosen 2.1, 2.2, 2.4 (Read/watch) Slides Lec B, Slides Lec A 

6  11/7 Induction Rosen 5.1 (Read/watch) Slides Lec B, Slides Lec A 
11/8 Discussion 6 Review Quiz 6 Due 11/8 11pm 
11/9 Induction + Recursion Rosen 5.3, 2.4 (Read/watch) Slides Lec B, Slides Lec A 
Homework 5 Due 11/11 11pm PDF, source, style 
7  11/14 (Strong) Induction Rosen 5.2, 5.3 (Read/watch) Slides Lec B, Slides Lec A 
11/15 Discussion 7 Review Quiz 7 Due 11/15 11pm 
11/16 Functions + Cardinality Rosen 2.3, 2.5 (Read/watch) Slides Lec B, Slides Lec A 
Homework 6 Due 11/18 11pm PDF, source, style image 
8  11/21 Cardinality Rosen 2.5 (Read/watch) Slides Lec B, Slides Lec A 
11/22 Discussion 8 Review Quiz 8 Due 11/22 11pm 
11/23 Thanksgiving holiday 

9  11/28 Infinite sets Rosen 2.5 (Read/watch) Slides Lec B, Slides Lec A 
11/29 Discussion 9 Review Quiz 9 Due 11/29 11pm 
11/30 Graphs, equivalence relations Rosen 10.1, 9.1, 9.3, 9.5 (Read/watch) Slides Lec B, Slides Lec A 
Homework 7 Due 12/2 11pm PDF, source, style 
10  12/5 Modular arithmetic Rosen 4.1, 4.3, 4.5 (Read/watch) Slides Lec B, Slides Lec A 
12/6 Discussion 10 Review Quiz 10 Due 12/6 11pm 
12/7 Review Rosen 10.1, 9.5 (Read/watch) Slides Lec B, Slides Lec A 
Homework 8 Due 12/9 11pm PDF, source, style 
Exam week  PostSurvey Linked here 
Final exam 12/16 11:30am2:30pm 
Welcome to CSE20! 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.
Upon successful completion of this course, you will be able to:
We are looking forward to working with you this quarter.
Announcements and Q&A are through Piazza (sign up link: piazza.com/ucsd/fall2017/cse20).
Our office hours and locations can be found in the calendar above.
Send regrade requests to cse20regrades@eng.ucsd.edu, following the instructions here
For private questions to Prof. Minnes, you can reach me at minnes@eng.ucsd.edu
The required textbook for this course is
This book is on reserve in the library and is also available in hardcopy at the UCSD Bookstore or many online retailers.
There are not many differences between the 7th edition and other recent editions, so you may be able to save some money by purchasing an older edition of the textbook. All posted reading assignments refer to the chapter and section numbers of the 7th edition. This guide lists the corresponding sections in the 5th and 6th editions.
Online Self Assessments and Extra Examples from the book are here.
A useful but optional supplementary resource is
Algorithms (Sec 3.1, Appendix 3): Def 1 of algorithm (p191), Properties of algorithms (p193)
Videos: Greedy Algorithm example
Optional extra practice: Rosen 3.1 # 53, 55, 57
Number systems (Sec 4.1, 4.2): Def 1 of divides (p238), Theorem 2: the division algorithm (p239), Def 2 of div and mod (p239), Thm 1: base b expansion of n (p246), Algorithm 1: constructing base b expansion (p249)
Videos: Definition, Notation, Bounds, Conversion examples, Hexadecimal arithmetic
Optional extra practice: Rosen 4.1 # 9, 21, 23 and Rosen 4.2 # 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23
Circuits (Sec 1.2, 1.1, 1.3): Figure 1 basic logic gates (p21), Tables 13 (p4) defining basic logical operators
Videos: None for this class session.
Optional extra practice: Rosen 1.1 #7, 27, 29, 31, 41 and Rosen 1.2 # 9 and Rosen 12.3 #1,3,5
Propositional connectives (Sec 1.1): Tables 1,2,3,4,5,6 (definitions) and Table 8 (precedence)
System specifications and consistency (Sec 1.2): Examples 4 and 5 (page 18)
Videos: Propositional Logic Translation examples, truth table examples
Optional extra practice: Rosen 1.1 #7, 27, 29, 31, 41; 1.2 # 9, 17, 25, 27, 29, 31, 41, 43; 12.3 #1,3,5; 1.3 #16, 1630
Predicates and quantifiers (Sec 1.4, 1.5): Sec 1.4: Definition of predicates on p. 37 and Example 1, Definition 1, Definition 2, Table 1 and Table 2. Sec 1.5: Example 4 on page 59, Table 1, Example 14 on page 63.
Videos: Predicate Logic Translation example
Optional extra practice: Rosen 1.4 # 13, 17, 19, 29, 31, 37, 39; 1.5 #9, 13, 25, 31
Proof strategies (Sec 1.6, 1.7, 1.8): Sec 1.6 Table 2 (rules of inference with quantifiers). Sec 1.7 introduction (pp 8082), Definition 1 (evens and odds), "A little proof strategy: p. 85, Definition 2 (rational number). Sec 1.8 Exhaustive Proofs (pp. 93).
Videos: Proofs Introduction TL;DR, Direct Proof Example, Contrapositive Proof Example
Optional extra practice: Rosen 1.6 # 15, 17; 1.7 #1, 5, 15, 35; 1.8 #3, 13, 14, 15
More Proof strategies (Sec 1.6, 1.7, 1.8): Proofs by contradiction (p.86).
Videos: Contradiction TL;DR, Proof by Contradiction Example
Optional extra practice: Rosen 1.8 # 9, 25, 29, 35
Sets and Summations (Sec 2.1, 2.2, 2.4): Definition 1 of 2.1 (p. 116), the empty set (p. 118), Definition 3 (p. 119), Definition 6 (p. 121), Definition 8 (p. 123). Definitions 1 through 5 of Section 2.2 (pp. 127129). Generalized union in Definitions 6 and 7 of p. 133. Summation notation on pp. 162163
Videos: Four sets examples
Optional extra practice: Rosen 2.1 # 23, 31; 2.2 # 3, 31, 45; 2.4 #29, 33
Induction (Sec 5.1): Principle of Mathematical Induction (p. 313), Example 1 (p. 316), Example 3 (p. 318).
Videos: Induction TL;DR, Example: Induction for Identity, Example: Induction for construction
Optional extra practice: Rosen 5.1 # 3, 5, 7, 11, 19, 21, 51, 55;
Recursive definitions and structural induction (Sec 5.3): .
Videos: Structural induction example
Optional extra practice: Rosen 5.3 # 23, 25, 27, 33, 37, 39; 2.2 # 47, 49
Strong induction (Sec 5.2): Definition (p. 334), Example 2 (p. 336), Example 4 (p. 337)
Videos: Induction variants TL;DR, Example: Strong induction for Nim
Optional extra practice: Rosen 5.2 # 7, 11, 25, 29;
Functions and Cardinality Sec 2.3 Definition 1 (p. 139), Example 3 (p. 140), Definition 5 (p. 141), Definition 7 (p. 143), Figure 5 (p. 144). Sec 2.5 Definition 1 (p. 170), Definition 3 (p. 171).
Videos: Proving properties of functions: two examples
Optional extra practice: Rosen 2.3 #21; 2.5 # 1, 3, 11, 17, 19, 33
Cardinality (Sec 2.5): Example 3 (p. 172), Example 4 (p. 172), Example 5 (p. 173)
Videos: Set of positive rationals is countable
Optional extra practice: Rosen 2.5 # 13, 15, 17
Binary Relations Sec 9.1: Definition 1 (p. 573), Definition 2 (p. 575), Example 4 (p. 575), Example 5 (p. 575), Definition 3 (p. 576), Definition 4 (p. 577), Definition 5 (p. 578); Sec 9.3: Definition 1 (p. 594), Example 7 (p. 594); Sec 9.5: Definition 1 (p. 608), Example 3 (p. 609), Definition 3 (p. 610), Example 9 (p. 610), Theorem 2 (p. 613), Example 14 (p. 614)
Videos: Proving properties of relations: two examples
Optional extra practice: Rosen 9.1 # 3, 7; 9.5 # 1, 7, 13, 35, 37
Modular arithmetic Sec 4.1: Definition 3 (p. 240), Corollary 2 (p. 242)
Optional extra practice: Rosen 4.1 # 27, 33, 47