# Introduction

• Discrete Mathematics
• Instructor: Greg Baker, ggbaker@sfu.ca.
• Call me “Greg”. Seriously.
• Or I'll probably respond to 君睿 (Jūnruì) if that's easier for you.
• Office hours: Mondays 9:40–10:40 in Zijingang, West 1, room 413.
• TA: Xin Wang, xinwang(at)zju.e.c. Office hours: ???
• Course web site: http://www.cs.sfu.ca/~ggbaker/zju/math/
• Announcements will be posted there (unless I can find somewhere better).
• Course textbook: Discrete Mathematics and its applications, Kenneth H. Rosen, 6th edition.
• I will be following the topic-order in the book, at least initially.
• Do you have other editions? I'll do my best to adapt.
• I will post these notes, but not necessarily before lecture.
• There will be examples and topics covered in lecture that aren't in these notes. You are responsible for them on tests as well.
• Can we find a better (i.e. later) time for this lecture? Monday/Wednesday?
• Topics:
• Logic and proofs
• Sets, functions, sequences, sums
• Algorithms, integers, matrices
• Induction and recursion
• Counting/combinatorics
• Relations
• Graphs and trees
• But what's the course really about?
• Sadly, not computer science. But, it's stuff that all of CS relies on.
• Computer science is [according to Schneider & Gersting, An Invitation to Computer Science] “the study of algorithms, including
1. Their formal and mathematical properties.
2. Their hardware realizations.
3. Their linguistic realizations.
4. Their applications.”
• This course is preparation to work on those things (especially 1).
• If you're more into applications, this course might not be exciting. Trust me, it's important.
• Marks:
• Weekly assignments: 20%
• Some questions from the textbook, some not.
• Each counts equally. (each 20%/14 weeks?)
• Assigned Thursday, due Monday Thursday.
• There are to be completed individually. It's okay to discuss concepts with others, but don't copy directly or discuss details.
• Midterm exam/quizzes: 30%
• Would you rather one midterm or more (two? three?) smaller tests?
• Final exam: 50%
• Two hours, covers whole course.
• Sunday June 30, 14:00–16:00.
• Grew up near Ottawa, Canada.
• Undergrad (in math + CS) near there at Queen's University in Kingston.
• Masters in CS at SFU.
• Then they hired me for some reason. It's a really, really good job.

# “Discrete” Mathematics

• What is “discrete” math? How is it different that… whatever the alternative is?
• The opposite is “continuous”.
• In mathematics, continuous means that things can always be divided more finely.
• e.g. the real numbers are continuous. There is always a value between two others: between 1 and 2 is 1.5 (and others).
• e.g. the rational number are continuous. Between 4/5 and 8/3 is 11/7 (and others).
• e.g. a circle is continuous: pick any two points on the circle and I can find one between them.
• In discrete mathematics, there are certain fixed values.
• e.g. the integers are discrete. There is no integer between 1 and 2.
• e.g. the alphabet is discrete. There is no letter between A and B.
• In discrete mathematics, we can ask questions like:
• How many integers are there between 4 and 9? 4.
• What is the next letter after Q? R.
• In continuous mathematics, those questions don't have answers (or at least not very satisfying ones).
• How many real numbers are there between 4 and 9? Lots. [Or $$\aleph_1$$ if you really want an answer.]
• What is the next rational number after 5/7? Ummm…