CSE 20: Discrete Mathematics for Computer Science --- FALL 2017 ARCHIVED SITE: DEPRECATED

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 cse-20-regrades@eng.ucsd.edu, following the instructions here

For private questions to Prof. Minnes, you can reach me at minnes@eng.ucsd.edu

Textbook

The required textbook for this course is

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.

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

Fundamentals of Discrete Math for Computer Science: A Problem-Solving Primer, Jenkyns and Stephenson The full pdf of this book is available for free download from a UCSD internet connection here.

Pre-class reading and videos, and optional extra practice questions

Week 0

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

Week 1

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 1-3 (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

Week 2

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 #1-6, 16-30

Week 3

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 80-82), 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

Week 4

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

Week 5

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. 127-129). Generalized union in Definitions 6 and 7 of p. 133. Summation notation on pp. 162-163

Videos: Four sets examples

Optional extra practice: Rosen 2.1 # 23, 31; 2.2 # 3, 31, 45; 2.4 #29, 33

Week 6

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

Week 7

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

Week 8

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

Week 9

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

Week 10

Modular arithmetic Sec 4.1: Definition 3 (p. 240), Corollary 2 (p. 242)

Optional extra practice: Rosen 4.1 # 27, 33, 47