CMSC 27100: Discrete Mathematics (Autumn 2019)

This page is intended for Sections 3 and 4 only.

General information

Instructor: Timothy Ng (timng@uchicago.edu)
Office hours: Tuesdays 2:00-3:30 pm, Thursdays 1:00-2:30 pm, or by appointment, JCL 203
Teaching assistants: Bruno Barbarioli (barbarioli@uchicago.edu)
Office hours: Mondays 4:00-5:00 pm, JCL 205; Zihan Tan (zihantan@uchicago.edu)
Office hours: Thursdays 2:30-3:30 pm, JCL 205
Lectures: Section 3: MWF 11:30-12:20, Wieboldt 408; Section 4: MWF 2:30-3:20, Ryerson 277
Discussion sessions: Wed. 3:30-4:20, Cobb 107; Thurs. 3:30-4:20, SS 302; Thurs. 4:30-5:20, SS 302; Fri. 2:30-3:20, Cobb 403
Course webpage: https://cs.uchicago.edu/~timng/271/a19/

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: Undirected and directed graphs, paths, connectivity

Communication

We will use Canvas for announcements and for non-public materials. We will use Piazza for general course communication. General questions about the course should be posted to Piazza rather than emailed to course staff. You can access Piazza through 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:

problem sets less the lowest graded problem set, worth 40% in total,
a midterm test, worth 25%,
a final examination, worth 35%.

Lectures

October 2: Introduction, propositional logic
October 4: Predicate logic, set theory
October 7: Set operations, relations and functions
October 9: Divisibility
October 11: Greatest common divisors, Euclid's algorithm
October 14: Modular arithmetic
October 16: Chinese remainder theorem, prime numbers, induction
October 18: Prime numbers, fundamental theorem of arithmetic
October 21: Induction
October 23: More induction: strong induction, Frobenius instances, Fibonacci numbers
October 25: Even more induction: inductive definitions, strings/words
October 28: Basic combinatorics
October 30: The pigeonhole principle, permutations
November 1: Permutations and combinations
November 4: Midterm Q&A
November 6: Midterm exam
November 8: The binomial theorem
November 11: Generalizing permutations and combinations
November 13: Probability theory
November 15: Independence, Bernoulli trials
November 18: Expectation
November 20: Variance, Bayes' theorem
November 22: Bayes' theorem, Graph theory
November 25: Graph isomorphism, bipartite graphs
November 27: Matchings, paths, connectivity
December 2: Recurrence relations
December 4: More linear recurrences and wrap-up

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.
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.
No late submissions will be accepted.
The lowest problem set grade will be omitted from the final grade calculation.

Problem Set 1: Due Wednesday October 9
Problem Set 2: Due Friday October 18
Problem Set 3: Due Friday October 25
Problem Set 4: Due Friday November 1
Problem Set 5: No due date.
Problem Set 6: Due Friday November 15
Problem Set 7: Due Friday November 22
Problem Set 8: Due Friday November 29
Problem Set 9: Due Wednesday December 4

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.