1. Instruction team 2. Course logistics
(a) Syllabus (b) Textbook
(c) Grading criteria
3. What is Discrete Math? 4. Course content
COMS W3203 Discrete Mathematics
Canvas and will use:
• Canvas (courseworks) for the official announcements.
• Piazza as a discussion forum. Don’t be shy for asking! You can also post privately.
• Gradescope and canvas for HW submission.
• No website.
• Syllabus. Please read.
COMS W3203 Discrete Mathematics
1. Explain, Proof-read your work.
2. LATEX it: We want to see your HW returned in LATEX.
3. Homework 1 on LaTeX: required, and counts as one homework.
4. LaTeX resources:
(a) Using Overleaf/ShareLaTeX
(b) Installing a TEX distribution in your local machine (c) LaTeXiT
(d) Science & Engineering Library
COMS W3203 Discrete Mathematics
Academic honesty
Academic integrity will be strictly enforced.
• Columbia University Guide to Academic Integrity: https://www.college.columbia.edu/academics/ academicintegrity
• Department of Computer Science Academic Honesty Pol- icy:
http://www.cs.columbia.edu/education/honesty
COMS W3203 Discrete Mathematics
1. Mathematics: a discrete introduction. Scheinerman, . BrooksCole, 2013. Third Edition.
2. Full of practice questions with solutions or hints of solutions at the end.
COMS W3203 Discrete Mathematics
Introduce yourself!
• Please introduce yourself to your neighbors.
COMS W3203 Discrete Mathematics
What is this class about?
• This class is an introductory class in Discrete Mathematics with two primary goals:
1. Teach fundamental discrete math concepts.
2. Teach how to write proofs – How to think and write clearly.
• You will see most of the topics covered again/used in later CS courses. This course introduces them.
COMS W3203 Discrete Mathematics
Testing out
• For some of you, the topics will be completely new, others not.
• If for you, it is a lot of deja-vu, like 80% of the course content,
consider testing out.
• See my announcement for more information.
• This class is meant to start from scratch.
• Statistics from previous semesters.
• “I am good in math already, so I should do well!” Let’s talk about this…
COMS W3203 Discrete Mathematics
What is Discrete Math?
COMS W3203 Discrete Mathematics
What is Discrete Math?
• Mathematics can be roughly divided into discrete math (DM) and continuous math (CM).
• Analogy: DM is similar to a digital watch, only discrete time is displayed (where there is no split second).
• CM is similar to an analog watch displaying a continuous time.
COMS W3203 Discrete Mathematics
What is Discrete Math?
• DM deals with integers, puzzles, proof writing and induction.
• CM deals with real numbers to model real world phenomenon along with notions like continuity, derivatives, limits, differen- tial equations, etc.
• CM is older than DM
• DM flourished in the era of computers and has been very use- ful in applications such as scheduling airlines, communication, crypto systems, encoding movies and songs, databases, secu- rity, computer networks, etc.
COMS W3203 Discrete Mathematics
Course content
• Logic: Propositional logic, truth tables, Boolean algebra, inference.
• Proofs: if-then proof, contradiction, by cases, counter example
• Collections (set theory) Lists, sets, operations, factorial, cardinality, quantifiers
• Relations Relations, equivalence, partitions
• More proofs Smallest counter example, proof by induction
• Counting Multiplication theorem, Anagrams, permutations, binomial co- efficients, Pascal triangle, Inclusion-Exclusion
• Functions Functions, properties (injection, surjection, bijection), compo- sition, inverse
• Graph Theory graphs, degrees, handshaking theorem, trees, planar graphs.
• Number Theory Dividing, Greatest common divisor, modular arithmetic,
prime numbers, RSA public key encryption.
• Probability Sample space, events, random variables, independence, Bayes rule, conditional probability, expectation, variance.
COMS W3203 Discrete Mathematics
Course content
Most of the topics are essential for applications in computer science and engineering
COMS W3203 Discrete Mathematics
• Emphasis: Logical thinking and mathematical notation. You will learn:
– Use formal symbols in propositional logic.
– Find the truth value of an expression/statement. – Make inference.
• Keywords: Propositional logic, truth tables, Boolean algebra, theorems, truth, circuits, proofs, inference.
COMS W3203 Discrete Mathematics
• Teasers:
– It is sunny and 91F. How to interpret this statement?
– It is not cold. How to interpret this statement?
– Salad or fries come with the chicken. How to interpret this
statement?
– If you know how to swim, then you will be hired as a life- guard.
– If you know how to swim, then you will be hired as a life- guard. You know how to swim, therefore you will be hired as a life-guard.
– Let’s play Wumpus!
COMS W3203 Discrete Mathematics
• So you learned how to write mathematical statement in logic.
• Then, you will learn how to:
– think and write clearly, that is write a mathematical essay that shows without doubt that a statement is True.
– use different proof techniques.
• keywords: if-then proof, proof by contradiction, by cases,
counter example.
• Teaser: For every integer n, n2 + n + 41 is a prime number. Is this true?
COMS W3203 Discrete Mathematics
Collections
• You will learn how to deal with lists or collections of objects and how to count them.
• keywords: Lists, sets, operations, factorial, cardinality, quanti- fiers.
– What is in your backpack?
– How many license plates are possible if we use six characters, the first 3 are upper case and the last 3 are digits 0-9.
COMS W3203 Discrete Mathematics
• You will learn how to connect things with relationships, their properties, equivalence relations and equivalence classes.
• keywords: Relations, equivalence, partitions, equivalence classes.
• Teaser: The ’=’ on integers is a relation of equality: – Reflexive: any integer is equal to itself
– Symmetric
– Transitive
COMS W3203 Discrete Mathematics
More proofs
• You will learn how to do more proofs!
• keywords: Smallest counter examples and proof by induction.
– Chain reaction of dominos. – Induction machine
1+3+5+7=9+7=16′
Induc&on(Machine(
COMS W3203 Discrete Mathematics
• Whenever we have a question: How many …? we are dealing with a counting problem.
• You will learn how to count, e.g., the number of k-element subsets if an n-element set (choose). Crucial in Probability!
• keywords: binomial coefficients, pascal triangle, inclusion- exclusion, counting multisets
How many ways there are to choose 4 courses out of 10 pos-
sibilities?
10 = 210 4
COMS W3203 Discrete Mathematics
• You will learn how functions also play an important role in discrete math.
• keywords: Discrete functions, properties, composition
• Teaser: Pigeonhole principle
In a class of 163 students, must at least two or more have the same birthday?
COMS W3203 Discrete Mathematics
• You will learn how functions also play an important role in discrete math.
• keywords: Discrete functions, properties, composition
• Teaser: Pigeonhole principle
In a class of 163 students, must at least two or more have the same birthday?
No. There are 366 possible birthday. Each student could have a distinct birthday. (there are more holes than pigeons)
COMS W3203 Discrete Mathematics
Number Theory
• You will learn how the oldest branches of mathematics is cen- tral in the world of cryptography and todays computer security.
• Keywords: Dividing, Greatest common divisor, modular arith- metic, prime numbers, RSA public key encryption.
Every even integer greater than 2 can be expressed as the sum of 2 primes.
Example: 24 = 11 + 13
Is this true?
COMS W3203 Discrete Mathematics
Number Theory
• You will learn how the oldest branches of mathematics is cen- tral in the world of cryptography and todays computer security.
• Keywords: Dividing, Greatest common divisor, modular arith- metic, prime numbers, RSA public key encryption.
Every even integer greater than 2 can be expressed as the sum of 2 primes.
Example: 24 = 11 + 13
Is this true?
An unsolved mystery: Golbach conjecture 1742!
COMS W3203 Discrete Mathematics
Graph Theory
• You will learn how to represent relationships with graphs of vertices and edges. Very useful to model many problems in CS and engineering.
• Keywords: graphs, vertex, edge, degree, tree, planar graph, connectivity.
• Teaser: The problem of seven bridges: (textbook page 333)
Is there a tour we can take over the city so as we traverse each bridge only once?
COMS W3203 Discrete Mathematics
Graph Theory
Source: Image from Wikipedia The four color problem.
The regions in any map can be colored in 4 colors so as adja- cent regions have different colors.
COMS W3203 Discrete Mathematics
Probability
• You will learn how to cast counting problem in the language of probability. In life, we like to analyze how likely things happen.
• keywords: Sample space, events, random variables, distribu- tion, independence, Bayes, conditional probability, expectation, variance.
• Teaser: PowerBall Lottery: Five white balls 1 to 69 red power- ball 1 to 26. The jackpot – won by matching all five white balls in any order and the red Powerball worth $1.6B.
1. How many different outcomes are there for the five white
balls (if order doesn’t matter)?
COMS W3203 Discrete Mathematics
By next lecture…
Please read Appendix D in the textbook for a list of what we will assume in this class.
COMS W3203 Discrete Mathematics
• Mathematics: a discrete introduction. Scheinerman, . 2013
• Wikipedia for the 4 color problem picture.
COMS W3203 Discrete Mathematics
Questions?
COMS W3203 Discrete Mathematics