MPCS 50103—Mathematics for Computer Science: Discrete Mathematics (Winter 2020)
General information
- Instructor
- Timothy Ng (timng@uchicago.edu)
Office hours: MWF 2:30-3:30 pm, Tuesdays 5:00-7:00 pm, or by appointment, JCL 203
- Teaching assistant
- Fernando Granha Jeronimo (granha@uchicago.edu)
Office hours: Mondays 5:00-6:00 pm, JCL 207
- Lectures
- Wednesdays 5:30-8:30, Ryerson 276
- Course webpage
- https://cs.uchicago.edu/~timng/50103/w20/
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, naive set theory
- Elementary Number Theory
- Divisibility, modular arithmetic, prime numbers, induction
- 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
- Graphs, paths, connectivity
Communication
There are a number of different ways we'll be communicating about the course.
- Canvas will be used for announcements and confidential materials (solutions, grades).
- Piazza will be used for questions and general discussion about course material.
- Gradescope will be used for assignment submission and grading.
- For confidential concerns, please e-mail me.
The Piazza and Gradescope sites for this course are accessible from Canvas. You should be automatically enrolled in Canvas, as well as Piazza and Gradescope, once you access these sites from Canvas.
Resources
There are a number of useful resources.
Evaluation
Your final grade is based on the following graded components:
- weekly problem sets worth 40% in total,
- one midterm test, worth 20%,
- a final examination, worth 40%.
Lectures
- January 8
- Introduction, logic, proof
- January 15
- Sets, divisibility, greatest common divisors, Euclid's algorithm
- January 22
- Modular arithmetic, induction
- January 29
- Prime numbers, Fermat's little theorem, cryptography, basic combinatorics
- February 5
- Permutations, combinations, and generalizations
- February 12
- Midterm test, binomial theorem, pigeonhole principle, probability theory
- February 19
- Probability theory, Bayes' theorem, independence, expectation
- February 26
- Variance, graphs, graph isomorphism, bipartite graphs, matchings
- March 4
- Paths, connectivity, trees
- March 11
- Recurrence relations, Q&A
- March 18
- Final exam
Problem sets
- Students are expected to write up solutions to problem sets individually, but may work together. Be sure to list all of your collaborators and acknowledge any sources beyond course materials that you may have used.
- Problem sets will be posted on Wednesdays and will be due on the following Wednesday at 5:00 pm (17:00).
- We will be using Gradescope for assignment submission. Gradescope is accessible from Canvas. You should be automatically enrolled in Gradescope. If you aren't enrolled in Gradescope, please let me know immediately.
- Please ensure that submissions are legible. See this guide for submitting on Gradescope.
- No late submissions will be accepted.
- Problem Set 1
- Due Wednesday January 15
- Problem Set 2
- Due Wednesday January 22
- Problem Set 3
- Due Wednesday January 29
- Problem Set 4
- Due Wednesday February 5
- Problem Set 5
- No due date
- Problem Set 6
- Due Wednesday February 19
- Problem Set 7
- Due Wednesday February 26
- Problem Set 8
- Due Wednesday March 4
- Problem Set 9
- Due Wednesday March 11
- Problem Set 10
- No due date
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.