MPCS 50103—Mathematics for Computer Science: Discrete Mathematics (Winter 2021)
General information
- Instructor
- Timothy Ng (timng@uchicago.edu)
- Teaching assistants
- Benjamin Caldwell (caldwellb@uchicago.edu)
- Leonardo Nagami Coregliano (lenacore@uchicago.edu)
- Links
-
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.
Communication
This class is being offered remotely and largely asynchronously. There are a number of different ways we'll be communicating about the class.
- Course materials
- Lecture notes and links to lecture videos will be made available via this course webpage. The course website also contains basic information about the course (i.e. you can treat this like a syllabus).
- Discussion and announcements
- We will use Campuswire for course discussion and announcements. Restricted course materials and Zoom meeting information for synchronous sessions will also be posted here.
- Problem sets and grades
- We will use Gradescope for distributing and receiving coursework, such as problem sets and exams. Your grades will also be available here.
Class meetings
Lectures will be asynchronous and provided weekly as a set of videos on Mondays. There will be a synchronous tutorial session on Wednesdays at 5:30 pm Central. These sessions supplement the lecture videos and students are responsible for the material covered in these sessions. The synchronous sessions will be recorded.
Topics
- Proof and Logic
- Propositional and predicate logic, proofs, induction
- Elementary Number Theory
- Divisibility, modular arithmetic, prime numbers
- Combinatorics
- Counting, permutations, combinations, pigeonhole principle, binomial theorem, recurrences, generating functions
- Discrete Probability
- Probability, independence, correlation, expectation, variance
- Graph Theory
- Graphs, paths, connectivity, trees
Text
There is no required textbook for this course and lecture notes will be provided. However, there are a number of alternate resources. Note that definitions may differ across these. When in doubt, your primary source for definitions should be the lecture notes.
Evaluation
Your computed grade in this course will be determined by the following coursework components.
- An open-book final exam (timing to be decided). Let $F$ be the grade earned on the final exam. The weight of the final exam depends on the completion of other coursework.
- Weekly problem sets worth 50% in total.
- Half of this grade (25%) is from the initial submission of your solutions for each problem set. Let $P_1$ be the the grades earned on the initial submission for problem sets.
- The other half of this grade (25%) is from the revised submission of your solutions for each problem set. Let $P_2$ be the the grades earned on the initial submission for problem sets.
- Biweekly personal reflections each worth 1%. Let $R$ be the number of completed reflections.
- Weekly open-book quizzes, worth 15% in total. Let $Q$ be the the grades earned on quizzes.
There is no midterm exam. Let $S = (1\% \times R) + (15\% \times Q)$. Then your computed grade will be obtained via the following formula:
\[S + (P_1 \times 25\%) + (P_2 \times 25\%) + (F \times (50\% - S)).\]
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 released on Mondays and will be due on the following Monday at 8:00 pm (20:00) Central.
- Please ensure that submissions are legible. See this guide for submitting on Gradescope.
- Students will receive a grade and feedback on their initial submission. Students will then have the opportunity to submit a revised submission, which directly addresses the graders' feedback, to earn a higher grade. The grades for the initial and revised submissions are each worth half of the final problem set grade. If no revision is submitted, the grade for the initial submission will be used for both halves.
Quizzes
The weekly quizzes will be made available with each set of lecture videos. These are open-book short answer quizzes that will be completed online and will be graded automatically. These are meant for you to gauge your understanding of the lecture material.
Lectures
- January 4
- Introduction and course information
- January 11
- Lecture 1: Logic, Proof, and Induction
- Natural numbers
- Logic
- Proof
- Indirect Proof
- Induction
- January 18
- Lecture 2: Set theory basics
- Sets
- Set operations
- Functions
- Lecture 3: Number Theory
- Divisibility
- Division
- Divisors
- January 25
- Lecture 4: Strong Induction
- Fibonacci Numbers
- Analysis of Euclid's algorithm
- Lecture 5: Prime Numbers
- Prime Numbers
- The Fundamental Theorem of Arithmetic
- Lecture 6: Modular Arithmetic I
- Equivalence modulo $m$
- Multiplicative inverses modulo $m$
- February 1
- Lecture 7: Modular Arithmetic II
- Chinese Remainder Theorem
- Fermat's Little Theorem
- Bonus/Optional: Cryptography
- Lecture 8: Combinatorics I
- Combinatorics
- Permutations
- Combinations
- February 8
- Lecture 9: Combinatorics II
- Permutations and Combinations with Repetition
- The Binomial Theorem
- The Pigeonhole Principle
- Lecture 10: Probability I
- Probability Theory
- Conditional Probability
- February 15
- Lecture 11: Probability II
- Bayes' Theorem
- Independence
- Random Variables
- Lecture 12: Probability III
- Expectation
- Variance
- February 22
- Lecture 13: Graph Theory
- Graphs
- Isomorphism
- Lecture 14: Paths and Connectivity
- Walks, paths, cycles
- Eulerian and Hamiltonian paths
- Connectedness
- March 1
- Lecture 15: Trees
- Trees and connectivity
- Rooted and binary trees
- Lecture 16: Matchings
- Bipartite graphs and matchings
- Maximum matchings
- March 8
- Lecture 17: Asymptotics and Recurrences
- Asymptotics
- Recurrence relations
- Divide and conquer
- Linear recurrences
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.