Discrete Structures 1 | Math 240

Content.by section

Final Exam Topics | Books and Notes | Assignments | VIEW MY FINAL GRADE | Miscellaneous

Class Average Final Grade : 73.5

general.information

Instructor : Jacques Verstraete Room 1219 x3831
Class times : Mondays, Wednesdays, Fridays 11.35am.
Class location : 1B24 Burnside Hall
First Class : Wednesday September 6th
My e-mail : jbav at math dot mcgill dot ca
Office Hours : 1.30-3:30 Monday, Wednesday
or by appointment
Help Desk : Burnside 911 1:00-5:00.

Final exam.topics

Here is a pdf file of Final Exam Topics (Book Numbering) with numbering from the yellow book.
Another file of Final Exam Topics (Online Numbering) has numbering from the online notes.
Here is a Summary of techniques you should know from the course.
The final exam is on December 22nd 2006 at 9am, and will be three hours long.
A review session will be held in 1B24 from 6PM TO 8PM on Wednesday 20th December.

Here are the midterm materials and a practice final.

Here is a practice final exam
Solutions to practice final exam
1st Practice midterm | 1st Practice midterm solutions | 2nd Practice midterm | Midterm | Midterm solutions

books+notes

I will be closely following the textbook entitled Discrete Mathematics, Elementary and Beyond (Springer-Verlag) by Lovasz, Pelikan and Vesztergombi. This book is be on hold in the Rosenthall Library (Burnside 11th Floor). You can also download it here (but the chapter numbering is very different):

Course Notes (pdf file)
The first few lectures follow the rough notes on logic which are posted below, as well as some modules below:

Logic Notes (pdf file) | Notes on Stirling's Formula (pdf file) | Notes on Counting (pdf file) | Notes on Recurrence Equations (pdf file) | Notes on Modular Arithmetic (pdf file) | Notes on Cryptography (pdf file) | Notes on Coding Theory (pdf file) (Not Examinable) | Euler Tour Applet | Kruskal MST and TSP Applet | Euler's Formula | Generating Functions

assignment.files

Check.grades

The formula for computing your final grade is 20% on Assignments 20% on Midterm 60% on Final. I will be taking Assignments 1 - 5 for your assignment grade, and assignment 6 will not be marked. Please check the accuracy of your reported grades in the file below. In any place where a grade was missing, there is a zero. If you see this and you actually have a grade, please email me as soon as possible to correct the error (email jbav at math dot mcill dot ca).

Grades (webpage)

If your grade is written in red, it is likely that you will have to work very hard to pass the course. I recommend going through the assignments thorougly, the midterm material, and reading through the notes carefully. Please see me during office hours for further assistance.

course.outline

Click here for the pdf file of the course outline.

Mathematical foundations of logical thinking and reasoning. Sequences and sets. Mathematical language and proof techniques. Functions and relations. Elementary number theory. Combinatorial enumeration. Introduction to graph theory.

Basic Logic | Quantifiers, logical symbols, truth tables.
Sequences and sets | Binary operations, counting sequences and permutations, choosing objects with and without replacement, binomial coefficients, Pascal Triangle, functions and bijections, relations.
Proof Techniques | Multiplication principle. The pigeonhole principle and averaging, mathematical induction, proof by contradiction, inclusion-exclusion, counting in two different ways, comparing and estimating numbers, Stirling's Formula, Birthday Paradox.
Integers, Divisors, Primes | Primes and factorization, Fermat's little theorem, Euclidean division algorithm, modular equations, public key cryptography and RSA algorithm.
Enumeration | Basic generating functions, counting compositions of integers, counting partitions*, recurrence equations, Fibonacci numbers.
Graphs and Trees | The handshaking lemma, paths cycles and connectivity, eulerian and hamiltonian graphs, Travelling Salesman Problem, Matchings*, Cayley's Theorem.

academic.integrity

McGill University values academic integrity. Therefore all students must understand the meaning and consequences of cheating, plagiarism and other academic offences under the code of student conduct and disciplinary procedures -- see www.mgill.ca/integrity for more information.

useful.links

Handbook of student rights and responsibilities
McGill Home Page
McGill Math Home Page
Acrobat Reader
Programs and Demos
More Books
Amazon.ca