CMSC 27100: Discrete Mathematics (Autumn 2024)

General information

Instructor

Timothy Ng (timng@uchicago.edu)

Lecture sections

Section	Day	Time	Location
2	MWF	10:30–11:20	Stuart 102
3	MWF	11:30–12:20	Stuart 102

Discussion sections

Section	Day	Time	Location
2D03	Wed	4:30–5:50	Walker 302
2D04	Thurs	5:00–6:20	Cobb 302
3D05	Wed	4:30–5:50	Cobb 115
3D06	Thurs	5:00–6:20	Cobb 301

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 and proof techniques common to discrete math. This course provides the mathematical foundations for further theoretical study of computer science, which itself can be considered a branch of discrete mathematics.

Communication

There are a number of different tools we'll be using to communicate about the class.

Course materials: Lecture notes will be made available via this course webpage. The course website also contains basic information about the course (i.e. you can treat it like a syllabus).
Discussion and announcements: We will use Ed Discussion for course discussion and announcements. Restricted course materials will also be posted here.
Coursework and grades: Gradescope will be used for distributing and receiving coursework, such as problem sets and exams.; PrairieLearn will be used for administering discussion session work, such as quizzes and groupwork.
Office hours: Office hours are times when the course staff are available for you. The instructor and teaching assistants will have scheduled office hours in-person. While most students typically use this as an opportunity to ask about coursework, you're welcome to ask about or discuss things that are related directly or indirectly with the course.

Class meetings

Lectures: Lectures are often the first point at which students will be exposed to new ideas and material. They will cover material that is necessary for success in the course. However, lectures alone may not be sufficient for all students. It is not expected that students will master the material learned in lecture without significant review, inquiry, and practice outside of lecture.
Discussions: Discussion sessions are intended to give students an opportunity to practice and get feedback in a more active setting than lecture. Discussion sessions consist of two components: proctored online quizzes and group problem solving. You will need access to a device with internet access.

Course material

The following is a list of topics that will be covered in the course.

Proof and Logic: The language and rules of mathematical reasoning: propositional and predicate logic, proofs, induction
Elementary Number Theory: The structure of the integers: divisibility, modular arithmetic, prime numbers
Combinatorics: Enumerating discrete structures: counting, permutations and combinations, pigeonhole principle, the binomial theorem
Probability Theory: Describing the likelihood of discrete events: probability axioms, independence, expectation, concentration inequalities
Graph Theory: The structure of relations and networks: 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.

The recommended textbook is Mathematics for Computer Science, by Lehman, Leighton, and Meyer. The linked draft of this book is freely available.
Another comprehensive resource for this course is Discrete Mathematics and Its Applications, 8th ed. by Kenneth H. Rosen. An electronic copy is available through the UChicago Library.

Evaluation

Your computed grade in this course will be determined by the following coursework components.

Problem sets, roughly weekly, worth $\frac 1 4$.
Participation in group problem solving, roughly weekly, worth $\frac 1 {12}$.
Quizzes, roughly weekly, worth at most $\frac 1 6$.
One midterm examination, held on Thursday October 31 at Kent 107, worth at most $\frac 1 4$.
One final examination, to be scheduled by the Registrar, worth at least $\frac 1 4$. Furthermore, the portion of the grade not earned apportioned to quizzes and the midterm examination are assigned to the final examination.

Problem sets

Problem sets will be due on Fridays at 8:00 pm (20:00) Central and released at least one week before.

Problem sets will be distributed and submitted via Gradescope.

Submissions must be typed. $\LaTeX$ is the preferred and recommended method for preparing your submission but it is not required. No handwritten submissions of any kind will be accepted—this includes digitally handwritten submissions, such as those prepared on a tablet.
Take the opportunity to learn how to typeset mathematics with $\LaTeX$! In addition to many resources you can find online, all of the $\LaTeX$ commands used in the lecture notes is easily accessible by right-clicking on any formula, and selecting "Show Math As" $\rightarrow$ "TeX Commands" from the context menu.

Collaboration and citation

The purpose of problem sets is to give you the opportunity to practice working through the process of solving problems and to receive feedback on that process. The work that you hand in to be graded is expected to be your own. Why is this important?

When you submit a piece of work, you are claiming that it is a product of your understanding of the material.
Your work is subject to critique. It is important that your work represents your understanding so that the feedback you receive will be useful.
Authorship is not only about receiving credit for work, but also accountability. You should not submit any work for which you do not want to be held responsible for.

Be sure to acknowledge your collaborators and any sources beyond course materials that you may have used.

If you choose to work with others, you must list your collaborators. You may only work with other students in the class. Your collaboration should be to a degree that your writeups are substantially different. It is not acceptable that solutions are largely copies of each other.
You should not look up solutions to assigned problems, online or otherwise. This includes question and answer forums, homework websites, and other publicly available materials from other courses in the department or at other institutions. Be aware that if you can find a solution online, the course staff can too.
Since the purpose of the problem sets is to give you the opportunity to practice working through the process of solving problems and writing mathematics, you should not try to use language models to generate your submissions, whether in part or in whole.
If you use a source beyond course materials, the source must be a published source—either a book or journal article—and full citation must be given.
If you are not sure about whether something is permissible, you should err on the side of caution and ask the instructor.

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 College Community Standards for adjudication. Following the guidelines above on collaboration and citation should be sufficient, but if you have any questions, please ask me.

Resubmission

Part of the learning process is identifying and correcting mistakes. After your submissions have been graded and returned to you, you will have the opportunity to use the feedback you receive to revise and resubmit your work.

Instructions for preparing your revisions will be provided after the first problem sets have been graded and returned.

Regrade requests

You may submit a regrade request in the event of an error by the grader. That is, if the feedback provided by the grader is a factual error, you may request a review of the grading. Please indicate the source of the error in this case.

We will not consider regrade requests concerning disagreement with a grader’s evaluation of your work. In such cases, you should consider the feedback that was given and apply it towards revision and resubmission of your work.

Lectures

Lecture notes are put up after class. Readings are taken from Lehman, Leighton, and Meyer.

September 30: Discrete mathematics and computer science (7.1)
October 2: Induction, logic (5.1, 1.1–1.3, 3.1, 3.6)
October 4: Proof, Divisbility (1.4–1.6, 3.6, 9.1)
October 7: Induction again, Division (5.1, 9.1)
October 9: Divisors and the greatest common divisor (9.2)
October 11: Computing the GCD (9.2, 5.2)
October 14: Strong induction (5.2, 9.3)
October 16: The fundamental theorem of arithmetic (5.2.3, 9.4)
October 18: Sets (4.1–2, 4.4)
October 21: Modular arithmetic (9.6–9.7, 9.9)
October 23: Solving congruences, Fermat's little theorem (9.9–9.10)
October 25: Chinese remainder theorem, Cryptography (9.11, Problem 9.61)
October 28: Combinatorics, counting, functions (4.3, 4.5, 8.1, 15.1)
October 30: Product and sum rules, permutations (15.2–15.3)
November 1: Division rule, combinations (15.4–15.6)
November 4: Combinatorial proof, the pigeonhole principle (15.8, 15.10)
November 6: Graphs (12.1–12.2, 12.4)
November 8: Colourings (12.6)
November 11: Connectivity (12.7–12.8)
November 13: Bridges and trees (12.10-12.11)
November 15: Matchings (12.5)
November 18: Probability theory (17.3, 17.5)
November 20: Conditioning (18.2–18.4)
November 22: Independence, random variables (18.7, 19.1–19.3)
December 2: Binomial distributions, expectation (19.3–19.5)
December 4: Probabilistic analysis of algorithms
December 6: Wrap-up, Q&A

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 the instructor.

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 the instructor to discuss your access needs in this class after you have completed the SDS procedures for requesting accommodations.