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.

The most comprehensive resource for this course is Discrete Mathematics and Its Applications, 7th ed. by Kenneth H. Rosen.
Another useful resource is Building Blocks for Theoretical Computer Science by Margaret M. Fleck, although it does not contain everything we will be covering.
My lecture notes will also be made available shortly after each lecture.

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.