| General Information | Homework | Lecture Notes | Other Resources |

This course provides an introduction to basic discrete mathematics with an emphasis on algorithms. Topics include sets and functions, algorithms, induction, enumeration, probability, relations, graphs, and trees.

Lecture | MWF 12:00pm-12:50pm Engineering Hall 106B1 |
---|---|

Textbook | Kenneth H. Rosen.Discrete Mathematics and Its Applications, 7th edition |

Instructor | Andrew Hardt Office: CAB 69B Email: ahardt@illinois.edu Office Hours: MF 1:00pm-1:50pm, CAB 69B |

More Details | Syllabus | Gradescope | If you can't access the Gradescope course, email me |

Homework assignments are weekly, due at **11:59pm on Sundays via Gradescope**. Using LaTeX for your homework is encouraged, and you will receive 1 bonus point for each homework you typeset using LaTeX.

Here is a short LaTeX tutorial video.

- Homework 1 (TeX file) -- due Sun. 9/1 at 11:59pm (Solutions)
- Homework 2 (TeX file) -- due Sun. 9/8 at 11:59pm (Solutions)
- Homework 3 (TeX file) -- due Sun. 9/15 at 11:59pm (Solutions)
- Homework 4 (TeX file) -- due Sun. 9/22 at 11:59pm (Solutions)
- Homework 5 (TeX file) -- due Sun. 10/6 at 11:59pm (Solutions)
- Homework 6 (TeX file) -- due Sun. 10/13 at 11:59pm (Solutions)
- Homework 7 (TeX file) -- due Sun. 10/20 at 11:59pm (Solutions)
- Homework 8 (TeX file) -- due Sun. 11/3 at 11:59pm (Solutions)
- Homework 9 (TeX file) -- due Sun. 11/10 at 11:59pm

- Solutions to Quiz 1
- Solutions to Quiz 2
- Solutions to Quiz 3
- Solutions to Quiz 4
- Solutions to Quiz 5
- Solutions to Quiz 6
- Solutions to Quiz 7

- Lecture 1 (8/26): Syllabus, course overview
- Lecture 2 (8/28): Subset, power set, Cartesian product, etc. (Video, LaTeX tutorial)
- Lecture 3 (8/30): Set operations, proof techniques
- Lecture 4 (9/4): Functions
- Lecture 5 (9/6): Injectivity, surjectivty, inverse functions; Introduction to algorithms
- Lecture 6 (9/9): Searching and sorting algorithms
- Lecture 7 (9/11): Big-O notation (Extra Video)
- Lecture 8 (9/13): Mathematical Induction
- Lecture 9 (9/16): Strong Induction
- Lecture 10 (9/18): Counting Basics
- Lecture 11 (9/20): More Counting, and the Pigeonhole Principle
- Lecture 12 (9/23): Midterm 1 Review
- Lecture 13 (9/27): Permutations and Combinations
- Lecture 14 (9/30): Binomial coefficients and identities
- Lecture 15 (10/2): Generalized permutations and combinations (Last example)
- Lecture 16 (10/4): Introduction to probability
- Lecture 17 (10/7): Conditional probability, independence, Bernoulli trials
- Lecture 18 (10/9): Bayes' Theorem
- Lecture 19 (10/11): Recurrence relations
- Lecture 20 (10/14): Solving linear recurrence relations (Video)
- Lecture 21 (10/16): Inclusion-exclusion
- Lecture 22 (10/18): Applications of inclusion-exclusion
- Lecture 23 (10/21): Relations
- Lecture 24 (10/23): Midterm 2 Review
- Lecture 25 (10/28): Representing relations
- Lecture 26 (10/30): Equivalence relations
- Lecture 27 (11/1): Equivalence relations (cont.)
- Lecture 28 (11/4): Introduction to graphs
- Lecture 29 (11/6): More on graphs
- Lecture 30 (11/8): Adjacency/incidence matrices, and graph isomorphism

**Midterm Exam 1:** *Wednesday, 9/25 in class* (Solutions)

**Midterm Exam 2:** *Friday, 10/25 in class* (Solutions)

**Midterm Exam 3:** *Wednesday, 11/20 in class*

**Final Exam:** *Thursday, 12/19 -- 1:30pm-4:30pm, Location TBD*

**Problem Sessions:** *Thursdays, 10:00am-11:30am, Everitt Laboratory 2101 (through 10/17, then in Armory 329)*

- Practice Problems 1 (Solutions)
- Practice Problems 2 (Solutions)
- Gradeline calculator -- only works in Google Sheets

- Overleaf, a cloud-based LaTeX editor
- Detexify, a web app for identifying the LaTeX command(s) for various symbols
- Guidelines for Good Mathematical Writing, by Francis Su