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.

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

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
  1. Natural numbers
  2. Logic
  3. Proof
  4. Indirect Proof
  5. Induction
January 18
Lecture 2: Set theory basics
  1. Sets
  2. Set operations
  3. Functions
Lecture 3: Number Theory
  1. Divisibility
  2. Division
  3. Divisors
January 25
Lecture 4: Strong Induction
  1. Fibonacci Numbers
  2. Analysis of Euclid's algorithm
Lecture 5: Prime Numbers
  1. Prime Numbers
  2. The Fundamental Theorem of Arithmetic
Lecture 6: Modular Arithmetic I
  1. Equivalence modulo $m$
  2. Multiplicative inverses modulo $m$
February 1
Lecture 7: Modular Arithmetic II
  1. Chinese Remainder Theorem
  2. Fermat's Little Theorem
  3. Bonus/Optional: Cryptography
Lecture 8: Combinatorics I
  1. Combinatorics
  2. Permutations
  3. Combinations
February 8
Lecture 9: Combinatorics II
  1. Permutations and Combinations with Repetition
  2. The Binomial Theorem
  3. The Pigeonhole Principle
Lecture 10: Probability I
  1. Probability Theory
  2. Conditional Probability
February 15
Lecture 11: Probability II
  1. Bayes' Theorem
  2. Independence
  3. Random Variables
Lecture 12: Probability III
  1. Expectation
  2. Variance
February 22
Lecture 13: Graph Theory
  1. Graphs
  2. Isomorphism
Lecture 14: Paths and Connectivity
  1. Walks, paths, cycles
  2. Eulerian and Hamiltonian paths
  3. Connectedness
March 1
Lecture 15: Trees
  1. Trees and connectivity
  2. Rooted and binary trees
Lecture 16: Matchings
  1. Bipartite graphs and matchings
  2. Maximum matchings
March 8
Lecture 17: Asymptotics and Recurrences
  1. Asymptotics
  2. Recurrence relations
  3. Divide and conquer
  4. 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.