## 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