General information

Instructor

Robert Rand (rand@uchicago.edu)
  Office hours: Thursday 1:00 - 2:00 pm (JCL 313)

Teaching Assistants

Youngchan Cho (youngchan@uchicago.edu)
  Office hours: Friday 4:00 - 5:20 pm (JCL 257)

Grace Williams (gcwill@uchicago.edu)
  Office hours: Friday 1:00 - 2:20 pm (JCL 257)

Ryan Wandsnider (rjwandsnider@uchicago.edu)
  Office hours: Monday 4:40-6:00 (JCL 257)

Review Sections ("Labs")

Wed 3:30-4:20, Cobb 112 (Youngchan)

Thu 4:00-4:50, Cobb 402 (Grace)

Bonus review section: Wed 4:30-5:20, JCL 354 (Ryan)

Website

www.rand.cs.uchicago.edu/cmsc271/winter23/index.html

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, natural deduction, naive set theory

Elementary Number Theory

Induction, Divisibility, modular arithmetic, prime numbers

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 (time permitting)

Directed and Undirected Graphs, Representations, Traversal

Communication

We will use Canvas, Ed, and Gradescope. The pages specific to this course are linked below. When communicating with the course staff, please use the appropriate channel, and only use email for exceptional situations.

Canvas

Non-public materials (e.g. problem sets) will be posted on Canvas. Some timely announcements may be sent via Canvas.

Ed

We will use Ed for general course communication, most often for help on problem sets. Please post clarification questions publicly so other students can see them, and questions that may contain partial solutions privately.

Gradescope

We will use Gradescope for problem set submissions and for returning graded papers. We will also use Gradescope to communicate regarding regrade requests.

Written Resources

You are not required to purchase a textbook for this course. All problem sets will be self-contained. I will post notes after each lecture, and will serve as an official record of the topics covered.

The notes for this class were largely written by Timothy Ng and extended by me and David Cash.

Learning the material in this course deeply will require doing several examples and exercises. Thus I highly recommend you get access to a copy of the following resources. Readings from these resources will be posted to the course schedule. Specific exercises from these books will also be recommended but not required.

Discrete Mathematics and Its Applications, 7th/8th ed. by K.H. Rosen.

The most comprehensive resource for this course. Other editions are also fine, but be careful to check that the content aligns. This text has many exercises.

Building Blocks for Theoretical Computer Science, Version 1.3b by M.M. Fleck

This book is freely available. It is less comprehensive, but covers its content very well. It doesn't have traditional exercise sections, but the study problems are nice.

Introduction to Probability, 2nd ed. by J.K. Blitzstein and J. Hwang

This only covers combinatorics and probability, but it does so wonderfully, and it's free!

Evaluation

Your final grade is based on the following graded components:

• problem sets worth 40% in total,
• a midterm exam worth 25%,
• a final examination worth 35%.

Midterm

The midterm exam will tentatively take place on February 7th (UPDATED!) from 6:30 to 8:30 pm in the Kersten Physics Teaching Center Room 106. If you have an unmovable conflict please email me ASAP.

Lectures

All of the lecture notes, as well as the corresponding chapters in the recommended textbooks, will be posted on the schedule page, which we recommend you bookmark.

Problem sets

• Students are welcome to discuss the problem sets with fellow students and post general questions to Ed. However, the solutions must be entirely your own.
• Problem sets will be released every Monday and due the following Monday.
• Students can use up to two extensions to submit work by the end of Friday. Please conserve these extensions (I'd recommend not using them at all if possible).
• 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. (LaTeX is recommended, but not required.) See this guide for submitting on Gradescope.

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.