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 Predicates and proofs Rosen 1.7, 1.8 (Read/watch) Slides 
10/25 Discussion 4 Review Quiz 4 Due 10/25 11pm 
10/26 Review Slides 
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 Induction Rosen 5.1 (Read/watch) Slides 

6  11/7 Sets Rosen 2.1, 2.2 (Read/watch) Slides 
11/8 Discussion 6 Review Quiz 6 Due 11/8 11pm 
11/9 Induction + Recursion Rosen 5.3, 2.4 (Read/watch) Slides 
Homework 5 Due 11/11 11pm 
7  11/14 (Strong) Induction Rosen 5.2, 5.3 (Read/watch) Slides 
11/15 Discussion 7 Review Quiz 7 Due 11/15 11pm 
11/16 Functions + Cardinality Rosen 2.3, 2.5 (Read/watch) Slides 
Homework 6 Due 11/18 11pm 
8  11/21 Cardinality Rosen 2.5 (Read/watch) Slides 
11/22 Discussion 8 Review Quiz 8 Due 11/22 11pm 
11/23 Thanksgiving holiday 

9  11/28 Infinite sets, relations Rosen 2.5, 9.1 (Read/watch) Slides 
11/29 Discussion 9 Review Quiz 9 Due 11/15 11pm 
11/30 Graphs, equivalence relations Rosen 10.1, 9.5 (Read/watch) Slides 
Homework 7 Due 12/2 11pm 
10  12/5 Modular arithmetic Rosen 4.1, 4.3, 4.5 (Read/watch) Slides 
12/6 Discussion 10 Review Quiz 10 Due 11/15 11pm 
12/7 Review Rosen 10.1, 9.5 (Read/watch) Slides 
Homework 8 Due 12/9 11pm 
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
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;
Sets (Sec 2.1, 2.2):
Videos: Predicate Logic Translation example
Optional extra practice: Rosen 2.1 # 23, 31; 2.2 # 3, 31, 45
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