CMSC 27100: Discrete Mathematics (Autumn 2023)

General information

Instructor

Timothy Ng (timng@uchicago.edu)

Lectures

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

Discussions

Section	Day	Time	Location
2D03	Wed	4:30–5:20	Crerar 011
2D04	Thurs	5:00–5:50	Cobb 107
3D05	Wed	3:30–4:20	Cobb 106
3D06	Thurs	4:00–4:50	Ryerson 176

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.
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.
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 and/or online. 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. Quizzes are also administered during discussion sessions.

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
Discrete Probability: 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 most comprehensive resource for this course is Discrete Mathematics and Its Applications, 8th ed. by Kenneth H. Rosen. The course notes are heavily based on this text. Ungraded exercises will be assigned from this text. An electronic copy is available through the UChicago Library, though there are access limitations.
Another comprehensive resource is Mathematics for Computer Science, by Lehman, Leighton, and Meyer. The linked draft of this book is freely available.

Evaluation

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

Problem sets, roughly weekly, worth $\frac 1 4$.
Quizzes, roughly weekly, worth at most $\frac 1 4$.
One midterm examination, worth at most $\frac 1 4$.
One final examination, worth at least $\frac 1 4$.

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.

Please ensure that submissions are legible if handwritten! This includes making sure that your writing is neat as well as ensuring that your photos or scans are of reasonable quality.
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 are easily accessible by right-clicking on any formula, and selecting "Show Math As" $\rightarrow$ "TeX Commands" from the context menu.
Gradescope is designed assuming that submissions are made on sheets of US Letter size paper (8.5 in. $\times$ 11 in.). Submitting one large page can severely degrade the quality of the image that Gradescope displays to the grader.

Collaboration and citation

The purpose of problem sets is to give you the opportunity to practice working through the process of solving problems and writing mathematics and to receive feedback on that process. The work that you hand in to be graded is expected to be your own so that the feedback you receive will be the most useful.

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 use language models to generate your submissions.

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.

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. Section numbers correspond to Rosen 8th ed.

September 27: Discrete math and computer science (5.3–5.4)
September 29: Logic and proof (1.1, 1.4, 1.6, 4.1.2)
October 2: More proof and induction (1.6–1.7, 4.1, 5.1)
October 4: Division (4.1.3, 5.2.5)
October 6: Divisors (4.1.2, 4.3.6)
October 9: Euclid's algorithm (4.3.7)
October 11: Strong induction, prime numbers (5.3.2, 4.3)
October 13: Prime factorization (4.3, 5.2)
October 16: Sets (2.1–2.2, 9.1)
October 18: Modular arithmetic (4.1.4–4.1.5, 9.5)
October 20: Modular inverses, solving congruences, Fermat's little theorem (4.4.2, 4.4.5)
October 23: Chinese remainder theorem, cryptography (4.4.3, 4.6)
October 25: Combinatorics, functions (2.3)
October 27: Basic counting, permutations (6.1, 6.3.2)
October 30: Combinations, generalizing permutations and combinations (6.3.3, 6.5)
November 1: Binomial theorem, pigeonhole principle (6.4, 6.2)
November 3: Midterm exam
November 6: Graphs (10.1-10.3)
November 8: Paths and connectivity (10.4.1-3)
November 10: Connectivity and trees (10.4.4, 11.1)
November 13: Spanning trees (11.4)
November 15: Probability theory (7.1-7.2.4)
November 17: Independence, random variables (7.2.5-7)
November 27: Expectation (7.4.1-3)
November 29: Probabilistic analysis of algorithms (7.4.4-5)
December 1: 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.