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
- Their formal and mathematical properties.
- Their hardware realizations.
- Their linguistic realizations.
- 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.
- About me:
- 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…