McGill Discrete Structures I
Math 240, Winter term 2017
Office hours: Tuesday 3:00-4:30 in Burnside 1B39 - new tutorial location, or
Time: Monday, Wednesday, Friday at 11:30-12:30
Location: MAAS 112
Alexandre Brandts-Longtin, Burnside 1032
Office hours: Wednesday 1:00-2:30
Tuesday 1235-1335 in BURN 1B24
Friday 1435-1525 in RPHYS 114
Remaining Quiz Dates (all in class)
Wednesday March 8. Friday March 24. Monday April 10.
Remaining Graded Assignment Due Dates
Friday March 17. Tuesday March 28.
The course outline can be found here.
There is no required textbook for the course but students may find the following books helpful.
- Discrete Mathematics, Elementary and Beyond by L. Lovász, J. Pelikán, and K. Vesztergombi
- Discrete Mathematics and its Applications by K. H. Rosen
- Book of Proof by R. Hammack (freely downloadable
- Discrete Structures, Logic and Computability by Hein
- Discrete Mathematics by N. L. Biggs
Course grades will be based upon assignments (20%), quizzes - best 4 of 5 (20%), and a final exam (60%).
Burnside 911, 12:00-17:00 Monday-Friday
No late assignments will be accepted.
Assignments are due in the Math Office at 4:30 PM on their due date.
A LATEX template for the assignments can be found
There will be no midterm this year. Instead there will be a sequence of 5 quizzes. Here are past midterms which may be useful in preparing for quizzes or the final exam.
Midterms from previous years (for practice): here
What we've done so far
- Wednesday 4 January: intro to propositional logic; propositions; logical operators; truth tables. Equivalence.
- Recommended reading for propositional logic: see Hammack Chapter 2.
- Friday 6 January: Rules of Logic (propositional calculus). Intro to Set Theory. What is a discrete set?
- The rules of logic given in class are listed here.
- Formal definition of discreteness is beyond the scope of this course, but here is a link if you are interested in some more details.
- Monday 9 January: Set theory. Venn diagrams. Connections between logic and set theory. Set Identities. Cartesian products. Power Sets (next day).
- Chapter 1 from Hammack has loads of information and worthwhile reading it all.
- Wednesday 11 January: The conditional statement. We defined this operator by its truth table and discussed how the mathematical statement is interpreted in English.
``P implies Q''. ``Q only if P'' etc. The biconditional statement.
- See Chapters 2.3 and 2.4 from Hammack.
- Friday 13 January: Verified a tautology by truth table, and then verified a different tautology by rules of logic (inference). Mathematical Proofs. What is a valid proof?
Proofs can have several general structures or formats:
Direct Proofs: We proved a real polynomial has the form P(x)=x Q(x) if P(0)=0. Contrapositive proofs: We proved Pigeonhole Principle. Proofs by contradiction (deferred to next day). .
- See Chapters 4 and 5 from Hammack - strongly recommended.
- Monday 23 January: Predicate calculus. Universal and Existential Quantifiers. Basic examples of why they are useful.
- We considered in detail (so-called) DeMorgan's Law for Quantifiers. Table 2 in Rosen, Section 1.4.
- Wednesday 25 January: Quantifiers continued. Turning English into Symbolic Form. Unpacking Symbolic form into English. Negating Doubly-Quantified Statements.
- Rosen gives a lot of examples and exercises. We did Example 14 from Section 1.5.
- Friday 27 January: Mathematical induction. Examples of induction and strong induction. Quiz handed back.
- Rosen gives a lot of examples in Section 5.1 and 5.2 including the use of strong induction for prime number factorization.
- See also Hammack Chapter 10 for a succinct intro.
- Monday 30 January: Proofs by Minimal Counterexample. Unique Prime Factorizations.
- Recommended reading: Lovasz-Pelikan-Vesztergombi 6.1 and 6.2.
- Wednesday 01 February: Finished Prime Factorization proof. Mysterious Facts and Questions about Primes.
- Thursday 02 February. Assignment 2 posted.
- Solve the Twin Primes Conjecture? Consider a new career.
- Friday 03 February: Prime Number Theorem. Divisors of an integer.
- Recommended reading: Chapter 6 LPV
- Monday 6 February: GCDs and Euclid's Algorithm.
- Wednesday 8 February: Running time of Euclid's Algorithm. Intro to Modular arithmetic.
- Friday 10 February: Quiz. Modular Arithmetic.
- LPV continues to be a good source for reading on the topics this week.
- Monday 13 February: What is an inverse Mod n? Existence for n prime. Prime Fields.
- Wednesday 15 February: Computing Inverses using Euclid's Algorithm. Solving Modular Equations. [Suggested Reading: Section 6.8 LPV]
- Friday 17 February: Fermat's Little Theorem. Tricks for Computing Congruences with Large Exponents.
- Monday 20 February: Testing Primes. Fermat Test. Miller-Rabin Test. [ Suggested reading: Section 6.10 LPV ]
- Wednesday 22 February: Final details on making Miller-Rabin Efficient. Fast Exponentiation. Intro to Cryptography. Quiz 2 returned.
- Friday 24 February: A Cryptosystem for Saving a move in Chess. [ Suggested reading: Section 15.3 LPV ]
- Monday 06 March: RSA Cryptosystem.
- Wednesday 08 March: Quiz 3. Functions. Injections, bijections.
- Assignment 3 Due at 4:30PM.
- Friday 10 March: Counting via Bijections. Counting ordered sequences and subsets. (See Rosen 6.1 for exercises and discussion.)
- Monday 13 March: Counting unordered sequences and subsets. (See Chapter 6.3 of Rosen). How large is $n$! (Stirling's Formula)
- Wednesday 15 March: Snow Day. Classes Cancelled.
- Friday 17 March: Binomial Theorem. Counting Partitions (Multinomial Coefficient). Pascal's Triangle. See Rosen Chapter 6.4.
- Chapter 1 of LPV and Rosen Chapter 6 have much of what we discussed this week.
- Monday 20 March: Pigeon Hole Principle. Rosen 6.4 or LPV 2.4.
- Wednesday 22 March: Monotone subsequences. Inclusion-Exclusion.
- Friday 24 March: Quiz 4.
- Monday 27 March: More Inclusion-Exclusion. Euler's Totient Function.
The Musician Example.
- Wednesday 29 March: Introduction to Graph Theory. Basic definitions. Handshaking Lemma.
- Friday 31 March: Proved Theorem on Existence of Euler Circuits. Introduced Chinese Postman Problem. [suggested reading ch. 12 LPV]
- Monday 3 April: Outline of How to Solve Chinese Postman Problem? Hamilton Cycles.
- Wednesday 5 April: Hamilton Cycles in Graphs with minimum degree n/2. Travelling Salesman Problem. Local-Swap Algorithms.
- Friday 7 April: Matchings and Stable Sets.
- Monday 10 April: Final Quiz.