Contents may differ from the current or most recent offering of the course.
Course Description
Proof methods. Combinatorics: permutations and combinations, discrete probability, recurrence relations. Graphs and trees. Boolean and abstract algebra.
See the course outline for more information.
Course Details
Lecture Time/Place
Tuesday, 12:30pm–1:30pm; Thursday, 11:30am–12:30pm; Friday, 1:30pm–2:30pm.
All lectures are held in Goodwin Hall, room 254.
Textbook
E. Scheinerman, Mathematics: A Discrete Introduction. Cengage Learning, 3rd edition, 2012.
The textbook is available for sale at the campus bookstore. Course notes will also be provided for each lecture.
Marking Scheme
- 50% assignments (12.5% per assignment)
- 25% midterm
- 25% final exam
You must pass the final exam to pass the course.
News
- Apr. 12: The final exam will be written on Apr. 26. See the Exams section below for details. A review session will be held on Apr. 25 at 1pm in Goodwin Hall, room 230. Office hours for the week of the final exam are as follows:
- Taylor: Apr. 23, 1pm–3pm and Apr. 25, 3pm–4pm
- Apr. 5: Notes on Boolean and abstract algebra have been posted. The seventh problem set has also been posted.
- Mar. 31: The second half of the notes on trees has been posted.
- Mar. 25: The first half of the notes on trees has been posted. The sixth problem set has also been posted.
- Mar. 19: Assignment 4 has been posted. It is due by the beginning of class on Apr. 5.
- Mar. 18: The third part of the notes on graph theory has been posted.
- Mar. 12: The first two parts of the notes on graph theory have been posted. The fifth problem set has also been posted.
- Mar. 4: Assignment 3 has been posted. It is due by the beginning of class on Mar. 21.
- Feb. 25: The midterm will be written this week during the Feb. 28 lecture. See the Exams section below for details. The Feb. 26 lecture will serve as a review session. Office hours this week are as follows:
- Taylor: Feb. 26, 1:30pm–3:30pm (note the extended time)
- Xavier: Feb. 26, 8:30am–9:30am (note the changed date/time)
- Leonard: Feb. 27, 10:30am–11:30am
- Feb. 14: Notes on recurrence relations have been posted. The fourth problem set has also been posted.
- Feb. 12: Due to inclement weather, both the lecture and the office hour are cancelled today. Weather permitting, a makeup office hour will be held Feb. 13 at 1:30pm. The due date for Assignment 2 is not affected.
- Feb. 6: The second half of the notes on discrete probability has been posted. These notes contain material that was not covered in lecture (variance and probability distributions). This material is included for enrichment and will not be tested.
- Feb. 1: The first half of the notes on discrete probability has been posted. The third problem set has also been posted.
- Jan. 28: Assignment 2 has been posted. It is due by the beginning of class on Feb. 14.
- Jan. 25: The second half of the notes on combinatorics has been posted.
- Jan. 22: The first half of the notes on combinatorics has been posted. The second problem set has also been posted.
- Jan. 14: Assignment 1 has been posted. It is due by the beginning of class on Jan. 31.
- Jan. 11: Notes on proof techniques have been posted. The first problem set has also been posted. Problem sets are optional and not for marks, but they are great for some additional practice.
- Jan. 7: Welcome to the course! The first lecture is on Tuesday, Jan. 8.
Lectures
| Week | Notes | Readings |
| 1 | Introduction, Review, Proof Techniques | Scheinerman, 1.2–1.6, 4.20–4.22 (Problem set) |
| 2 | Combinatorics: basic techniques, permutations | Scheinerman, 2.8, 3.19, 5.25, 5.27 (Problem set) |
| 3 | Combinatorics (cont’d): combinations, binomial theorem | Scheinerman, 3.17–3.18 |
| 4 | Discrete Probability: definitions, properties, conditionals, RVs | Scheinerman, 6.30–6.33 (Problem set) |
| 5 | Discrete Probability (cont’d): RVs, expectation; Recurrences | Scheinerman, 6.33–6.34, 4.23 (Problem set) |
| 6 | Recurrences (cont’d), Algorithm Analysis (bonus topic) | Scheinerman, 4.23 (optional: 5.29) |
| — | Reading week | — |
| 7 | Review session and midterm; Graphs: definitions | Scheinerman, 9.47–9.48 (Problem set) |
| 8 | Graphs (cont’d): representations, paths/circuits, connectivity | Scheinerman, 9.49, 9.51 |
| 9 | Graphs (cont’d): isomorphisms, planarity, colouring | Scheinerman, 9.52–9.53 |
| 10 | Trees: definitions, properties, representations | Scheinerman, 9.50 (Problem set) |
| 11 | Trees (cont’d): traversals, spanning trees | Scheinerman, 9.50 |
| 12 | Boolean and Abstract Algebra | Scheinerman, 1.7, 8.40 (Problem set) |
Assignments
- Assignment 1, due January 31, 2019
- Assignment 2, due February 14, 2019
- Assignment 3, due March 21, 2019
- Assignment 4, due April 5, 2019
Assignments are due at the beginning of class on the due date. Late assignments will be accepted up to the beginning of the first class following the due date. Late assignments are subject to a penalty of 10% deducted from the earned mark.
Exams
Midterm
Date: February 28, 2019
Time: 11:30am–12:20pm
Place: Goodwin Hall, room 247 (last names A–M) and Goodwin Hall, room 254 (last names N–Z)
Content: All material from lectures up to and including Week 6
Final Exam
Date: April 26, 2019
Time: 7:00pm–9:00pm
Place: Mitchell Hall, gym 5
Content: All material from all lectures
Personnel
Instructor
Taylor J. Smith
Email: tsmith [at] cs [dot] queensu [dot] ca
Office: Goodwin Hall, room 235
Office hours: Tuesday, 1:30pm–2:30pm; Thursday, 12:30pm–1:30pm
Teaching Assistants
Xavier McMaster-Hubner
Email: 17xjem [at] queensu [dot] ca
Office: Goodwin Hall, room 241
Office hours: Monday, 10:30am–11:30am
Leonard Zhao
Email: 16lz1 [at] queensu [dot] ca
Office: Goodwin Hall, room 241
Office hours: Wednesday, 10:30am–11:30am