CSE 20 - Fall 2022

All notes (blank+annotated) and worksheet are available on Canvas under the "Files" folder. Please read through the notes and worksheet and have them with you as you watch the lecture recording for better note-taking. Please submit the completed worksheet to Gradescope within 24 hours after each scheduled class meeting for participation point.

Class meeting podcasts are available at: https://podcast.ucsd.edu/

Notes: homework assignments, worksheets, and midterm exams are available and due on Gradescope. All times are Pacific Time

Topic 1 - Algorithms and Number Systems

Readings:

Algorithms (Sec 3.1, Appendix 3): Def 1 of algorithm (p191), Properties of algorithms (p193).
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)

Lecture Schedule:

Day 01 - Friday 09/23 - Intro to Algorithm
Day 02 - Monday 09/26 - Number Systems part 1
Day 03 - Wednesday 09/28 - Number Systems part 2

Homework 1 due Friday October 07 at 11:59pm

Midterm 1 (covering topics from days 01-03) from 10am Saturday, October 08 to 10am Sunday, October 09

Topic 2 - Logic

Readings:

Circuits (Sec 1.2, 1.1, 1.3): Figure 1 basic logic gates (p21), Tables 1-3 (p4) defining basic logical operators
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)
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.

Lecture Schedule:

Day 04 - Friday 09/30 - Circuits and Propositions
Day 05 - Monday 10/03 - Logical Equivalent
Day 06 - Wednesday 10/05 - The Normal Forms + Predicates and Quantifiers
Day 07 - Friday 10/07 - Predicates and Quantifiers (cont.)
Day 08 - Monday 10/10 - Nested Quantifier

Homework 2 due Friday, October 21 at 11:59pm

Midterm 2 (covering topics from days 04-08) from 10am Saturday, October 22 to 10am Sunday, October 23

Topic 3 - Proof Strategies

Readings:

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), Proofs by contradiction (p.86).
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
Induction (Sec 5.1): Principle of Mathematical Induction (p. 313), Example 1 (p. 316), Example 3 (p. 318)
Strong induction (Sec 5.2): Definition (p. 334), Example 2 (p. 336), Example 4 (p. 337)

Lecture Schedule:

Day 09 - Wednesday 10/12 - Proof Strategies
Day 10 - Friday 10/14 - Intro to Set
Day 11 - Monday 10/17 - Intro to Sets (cont.)
Day 12 - Wednesday 10/19 - Proof by Induction
Day 13 - Friday 10/21 - Proof by Strong Induction

Homework 3 due Friday, November 04 at 11:59pm

Midterm 3 (covering topics from days 09-13) from 10am Saturday, November 05 to 10am Sunday, November 06

Topic 4 - Functions, Sets, and Cardinality

Readings:

Recursive definitions and structural induction (Sec 5.3)
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
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), (Sec 2.5): Example 3 (p. 172), Example 4 (p. 172), Example 5 (p. 173)

Lecture Schedule:

Day 14 - Monday 10/24 - Recursive Definitions of Sets and Functions
Day 15 - Wednesday 10/26 - Proof by Structural Induction
Day 16 - Friday 10/28 - Functions and Properties of Functions
Day 17 - Monday 10/31 - Cardinality
Day 18 - Wednesday 11/02 - Countable Sets
Day 19 - Friday 11/04 - Uncountable Sets
Day 20 - Monday 11/07 - Pigeon-Hole Principle & Counting Functions

Homework 4 due Friday, November 18 at 11:59pm

Midterm 4 (covering topics from days 14-20) from 10am Saturday, November 19 to 10am Sunday, November 20

Note: the topics from Day 20 - Counting Functions will not be asked on exams. However, Pigeon-Hole Principle will be a topic on both Exam 4 and the Final Exam.

Topic 5 - Binary Relations and Modular Arithmetic

Readings:

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)
Modular arithmetic and Cryptography Sec 4.1: Definition 3 (p. 240), Corollary 2 (p. 242)

Lecture Schedule:

Day 21 - Wednesday 11/09 - Binary Relation
Friday 11/11 - Veteran's Day - no class
Day 22 - Monday 11/14 - Posets and Hasse's Diagram
Day 23 - Wednesday 11/16 - Intro to Modular Arithmetic
Day 24 - Friday 11/18 - Modular Inverses
Day 25 - Monday 11/21- Intro to Cryptography - Affine Cipher
Day 26 - Wednesday 11/23 - Diffie-Hellman and RSA Counting Binary Relations
Friday 11/25 - Thanksgiving Holiday - no class
Day 27 - Monday 11/28 - Counting Binary Relations

Homework 5 due Friday, December 02 at 11:59pm

Review and Final Exam

Day 28 - Wednesday 11/30 - Final Review - Part 1 (materials from Blocks 1, 2, 3)
Day 29 - Friday 12/02 - Final Review - Part 2 (materials from Block 4 and 5)

Class meeting podcasts are available at: https://podcast.ucsd.edu/

Topic 1 - Algorithms and Number Systems

Readings:

Lecture Schedule:

Homework 1 due Friday October 07 at 11:59pm

Midterm 1 (covering topics from days 01-03) from 10am Saturday, October 08 to 10am Sunday, October 09

Topic 2 - Logic

Readings:

Lecture Schedule:

Homework 2 due Friday, October 21 at 11:59pm

Midterm 2 (covering topics from days 04-08) from 10am Saturday, October 22 to 10am Sunday, October 23

Topic 3 - Proof Strategies

Readings:

Lecture Schedule:

Homework 3 due Friday, November 04 at 11:59pm

Midterm 3 (covering topics from days 09-13) from 10am Saturday, November 05 to 10am Sunday, November 06

Topic 4 - Functions, Sets, and Cardinality

Readings:

Lecture Schedule:

Homework 4 due Friday, November 18 at 11:59pm

Midterm 4 (covering topics from days 14-20) from 10am Saturday, November 19 to 10am Sunday, November 20

Topic 5 - Binary Relations and Modular Arithmetic

Readings:

Lecture Schedule:

Homework 5 due Friday, December 02 at 11:59pm

Review and Final Exam

Final Exam (covering all topics from the course): 11:30am to 2:30pm, December 05 - Location: WLH 2001 (same as our lecture hall)