General information
- Instructor
- Robert Rand (rand@uchicago.edu)
Office hours: Mon 2:30-3:30, JCL 313 - Teaching Assistants
- Neng Huang (nenghuang@uchicago.edu)
Office hours: Tue 4:30-5:30, JCL 257 - Alexa Pomerantz (alexapomerantz@uchicago.edu)
Office hours: Fri 3:00-4:00, JCL 257 - Discussion Sections ("Labs")
- 3L03: Wed 4:30-5:20, Cobb 425 (Rand)
- 3L04: Wed 7:30-8:20, Cobb 119 (Huang)
- 3L05: Thu 4:30-5:20, Cobb 402 (Pomerantz)
- 3L06: Thu 6:30-7:20, Cobb 103 (Huang)
Overview
Discrete mathematics is the study of discrete mathematical structures. This includes things like integers and graphs, whose basic elements are discrete or separate from one another. This is in contrast to continuous structures, like curves or the real numbers. We will investigate a variety of topics in discrete math and the proof techniques common to discrete math. This course provides the mathematical foundation for further theoretical study of computer science, which itself can be considered a branch of discrete mathematics.
Topics
- Logic and Set Theory
- Propositional logic, predicates, and quantification, natural deduction, naive set theory
- Elementary Number Theory
- Induction, Divisibility, modular arithmetic, prime numbers
- Combinatorics
- Counting, permutations, combinations, pigeonhole principle, inclusion-exclusion, binomial theorem, generating functions, recurrences, asymptotics
- Discrete Probability
- Probability, independence, correlation, random variables, expectation, variance
- Graph Theory (tentative)
- Directed and Undirected Graphs, Representations, Traversal
Communication
We will use Canvas for announcements and for non-public materials. We will use Ed for general course communication. General questions about the course should be posted to Ed rather than emailed to course staff. You can access Ed through Canvas.
Materials
There is no required textbook for this course, but we recommend that students purchase Discrete Mathematics and Its Applications by Kenneth H. Rosen (7th or 8th edition).
Evaluation
Your final grade is based on the following graded components:
- problem sets worth 40% in total,
- a midterm exam worth 25%,
- a final examination worth 35%.
Midterm
The midterm will take places on Friday, October 29th.
Lectures
- Lecture 1: Propositional Logic
- Lecture 2: Natural Deduction
- Lecture 3: Predicate Calculus
- Lecture 4: Set Theory
- Lecture 5: Relations and Functions
- Lecture 6: Divisibility
- Lecture 7: Greatest Common Divisors
- Lecture 8: Modular Arithmetic
- Lecture 9: Induction
- Lecture 10: More Induction
- Lecture 11: Strong Induction
- Lecture 12: Fundamental Theorem of Arithmetic
- Lecture 13: Intro to Combinatorics
- Lecture 14: The Pidgeonhole Principle
- Lecture 15: Permutations and Combinations
- Lecture 16: The Binomial Theorem
- Lecture 17: Generalized Combinations
- Lecture 18: Probability Theory
- Lecture 19: Bayes' Theorem and Independence
- Lecture 20: Random Variables, Trials, and Expectation
- Lecture 21: Markov and Chebyshev's Inequalities
- Lecture 22: Large Numbers and Practical Applications
- Lecture 23: Recurrence Relations
- Lecture 24: Graph Theory
- Lecture 25: Graph Isomorphism and Bipartite Graphs
- Lecture 26: Matchings, Paths, and Connectivity
Problem sets
- Students are welcome to discuss the problem sets with fellow students and post general questions to Ed. However, the solutions should be your own.
- Problem sets will be released every Friday and due the following Friday.
- Students can use up to three extensions to submit work the following Monday. Please conserve these extensions (I'd recommend not using them at all if possible).
- We will be using Gradescope for assignment submission. You should receive an email notifying you that you've been enrolled by the end of the first week. If you haven't been enrolled or joined the class after the first week, please contact the instructor.
- Please ensure that submissions are legible. See this guide for submitting on Gradescope.
- Problem Set #1 (TeX) (Due Friday, October 8)
- Problem Set #2 (TeX) (Due Friday, October 15)
- Problem Set #3 (TeX) (Due Friday, October 22)
- Problem Set #4 (TeX) (Due Friday, October 29)
- Problem Set #5 (TeX) (Due Friday, November 05)
- Problem Set #6 (TeX) (Due Friday, November 12)
- Problem Set #7 (TeX) (Due Friday, November 19)
- Problem Set #8 (TeX) (Due Friday, December 3)
- Optional Exercises #1 (TeX)
- Optional Exercises #2 (TeX)
Academic integrity
It is your responsibility to be familiar with the University’s policy on academic honesty. Instances of academic dishonesty will be referred to the Office of the Provost for adjudication. Following the guidelines above on collaboration and citation should be sufficient, but if you have any questions, please ask me.
Accessibility
Students with disabilities who have been approved for the use of academic accommodations by Student Disability Services (SDS) and need reasonable accommodation to participate fully in this course should follow the procedures established by SDS for using accommodations. Timely notifications are required in order to ensure that your accommodations can be implemented. Please meet with me to discuss your access needs in this class after you have completed the SDS procedures for requesting accommodations.