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

The BIG questions

How do we decide (and prove) what's true?

How do we use mathematical facts and properties to solve problems and build new systems?

What's impossible? And what can we say about it?

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

## Weekly Schedule

Week Tuesday Wednesday Thursday Homework
0 9/28
First lecture!
Intro & Algorithms
Slides Lec B, Slides Lec A
Start of quarter Due 10/13 for credit
1 10/3
Number Systems
Slides Lec B, Slides Lec A
10/4
Discussion 1
Review Quiz 1
Due 10/4 11pm
10/5
Circuits
Slides Lec B, Slides Lec A
Homework 1
Due 10/6 11pm
PDF, source, style
2 10/10
Propositional logic
Slides Lec B, Slides Lec A
10/11
Discussion 2
Review Quiz 2
Due 10/11 11pm
10/12
Equivalences
Slides Lec B, Slides Lec A
Homework 2
Due 10/14 11pm
PDF, source, style
3 10/17
Predicate logic
Slides Lec B, Slides Lec A
10/18
Discussion 3
Review Quiz 3
Due 10/18 11pm
10/19
Proof strategies
Slides
Homework 3
Due 10/21 11pm
PDF, source, style
4 10/24
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
Slides Lec B, Slides Lec A
6 11/7
Induction
Slides Lec B, Slides Lec A
11/8
Discussion 6
Review Quiz 6
Due 11/8 11pm
11/9
Induction + Recursion
Slides Lec B, Slides Lec A
Homework 5
Due 11/11 11pm
PDF, source, style
7 11/14
(Strong) Induction
Slides Lec B, Slides Lec A
11/15
Discussion 7
Review Quiz 7
Due 11/15 11pm
11/16
Functions + Cardinality
Slides Lec B, Slides Lec A
Homework 6
Due 11/18 11pm
PDF, source, style
image
8 11/21
Cardinality
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
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
Slides Lec B, Slides Lec A
12/6
Discussion 10
Review Quiz 10
Due 12/6 11pm
12/7
Review
Slides Lec B, Slides Lec A
Homework 8
Due 12/9 11pm
PDF, source, style
Exam week Post-Survey
Final exam
12/16 11:30am-2:30pm

## Syllabus

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:

• Describe and trace simple algorithms using English and pseudocode.
• Identify and prove (or informally justify) termination and correctness of some algorithms.
• Define and use classical algorithms and algorithmic paradigms e.g. Euclidean algorithm, greedy optimization.
• Use multiple representations of numbers to illustrate properties of the numbers and develop algorithms.
• Understand the logical structure and meaning of a sentence expressing a property, fact, or specification.
• Reason about the truth or falsity of complicated statements using Boolean connectives, quantifiers, and basic definitions.
• Relate boolean operations to applications, e.g. logic puzzles, set operations, combinatorial circuits.
• Prove propositional equivalences.
• Apply proof techniques, including direct proofs and proofs by contradiction.
• Distinguish valid from invalid arguments.
• Prove program correctness using loop invariants and pre-conditions /post-conditions.
• Use mathematical induction to prove statements about mathematical identities and inequalities.
• Apply structural induction to prove statements about recursively defined objects.
• Identify and be able to prove basic properties of sets, functions, and relations.
• Distinguish between finite, countable, and uncountable sets.

## CSE 20 instructional team

We are looking forward to working with you this quarter.

Our office hours and locations can be found in the calendar above.

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

## 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)

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)

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.

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).

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).

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).

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)

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).

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)

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)

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