CSE 20: Discrete Mathematics for Computer Science

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
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 Post-Survey
Linked here
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.
  • Reason about modular arithmetic.
  • 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.

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