12-06 16:10 Statistics posted. Click "Statistics" on the banner.
12-04 1:10 Assignments ORD10 and BON10 posted on Gradescope. Due Dec 7 at 23:00.
12-03 16:37 Fourth (last) batch of new homework problems posted. Due Dec 7.
12-03 14:20 Third batch of new homework problems posted.
12-03 13:10 Second batch of new homework problems posted.
12-01 13:00 12-01 CLASS NOTES from iPad have been posted. Click "CLASS NOTES" on the banner.
12-01 0:35 First batch of new homework problems posted. Due Dec 7.
11-29 17:05 11-29 CLASS NOTES from iPad have been posted.
11-14 5:30 Assignments ORD09 and BON09 posted on Gradescope. Due Nov 28.
11-24 1:30 Homework problems posted. Due Nov 28 and Dec 7.
11-20 1:17 11-17 CLASS NOTES from iPad have been posted.
11-15 13:10 11-15 CLASS NOTES from iPad have been posted.
11-11 2:45 Assignments ORD08 and BON08 posted on Gradescope. Due 11-14.
11-10 16:15 First batch of new homework problems posted. Due Nov 14.
11-10 13:45 Material covered in classes 11-08 and 11-10 and required reading posted. Homework to follow.
11-10 12:50 11-10 CLASS NOTES from iPad have been posted.
11-08 12:55 11-08 CLASS NOTES from iPad have been posted.
11-04 21:30 Assignments ORD07 and BON07 posted on Gradescope. Due 11-07.
11-04 12:50 Third batch of new homework problems posted. Due Nov 7.
11-03 20:25 Second batch of new homework problems posted. Due Nov 7.
11-03 13:18 11-03 CLASS NOTES from iPad have been posted.
11-01 13:08 11-01 CLASS NOTES from iPad have been posted.
10-28 10:30 Assignments ORD06 and BON06 posted on Gradescope. Due 10-24.
10-27 12:45 10-27 CLASS NOTES from iPad have been posted.
10-26 15:00 10-25 "homework, material covered" posted. Updated 10-27 at 9:00. Make sure to look at the 10-27 version. (Date printed under the title.) Homework due 10-31.
10-26 00:30 10-25 CLASS NOTES from iPad have been posted.
10-21 1:05 Assignments ORD5 and BON05 posted on Gradescope. Due 10-24.
10-21 00:15 10-20 "homework, material covered" completed
10-20 21:50 10-18 "homework, material covered" completed
10-20 15:45 10-20 CLASS NOTES from iPad have been posted.
10-19 14:05 First batch of new homework problems posted. Due 10-24.
STUDY the "Euclid's algorithm and multiplicative inverse" handout. Click "Texts" on the banner. Make sure you open the latest version: under the title it should say "Last updated at 12:40pm on 10-19-2022." If you do not see "12:40pm" in this statement, refresh your browser; if this is not sufficient, clear your browser's cache or try another browser.
10-19 00:50 10-18 CLASS NOTES from iPad have been posted. Click "CLASS NOTES" on the banner.
10-15 1:50 Assignments ORD04 and BON04 posted on Gradescope. Due 10-17.
10-14 21:05 New homework problems posted.
10-13 20:10 10-13 CLASS NOTES from iPad have been posted.
10-11 15:15 10-11 CLASS NOTES from iPad have been posted.
10-11 14:50 First batch of new homework problems posted. Due 10-17.
10-07 1:00 Assignments ORD03 and BON03 posted on Gradescope. Last updated 10-07 3:00 (problem 6.112 added as ORD12). Due 10-10 at 23:00.
10-06 15:05 First batch of new homework problems posted. Due 10-10.
10-06 12:45 10-06 CLASS NOTES from iPad have been posted.
10-04 15:30 First batch of new homework problems posted. Due 10-10.
10-04 14:00 10-04 CLASS NOTES from iPad have been posted.
10-04 03:00 ORD02, BON02 graded homework sets posted. Please check instructor's comments.
09-29 15:13 09-29 CLASS NOTES from iPad have been posted.
09-30 13:30, updated 15:20.
2nd homework assignment posted (click "HOMEWORK,
material covered" on the banner). Assigned 09-29 in class, due
Mon 10-03 at 23:00. Solve the ORD problems 2.10-2.60 and
the Bonus problems 2.70 and 2.80. These problems correspond
to the problems stated in class and posted in the class notes
(click "Class notes from iPad" on the banner); the correspondence
is that an extra zero has been added, e.g., problem 2.3 assigned in
class became ORD 2.30 on the "HOMEWORK, material covered" page.
Please typeset your work using the LaTeX template (click "LaTeX
homework template" on the banner) and compile it to PDF.
Submit your PDF on Gradescope. Two assignments have been
created: ORD02 and BON02. ORD02 lists the "ordinary problems"
2.10-2.60, BON02 lists the "bonus problems" 2.70 and 2.80.
Please upload your PDF on both the ORD02 and BON02 sites.
Please link each solution as described on Gradescope.
Deadline: Monday, Oct 3, 23:00.
First homework assignment (assigned in class on Tuesday, Sep 27).
Let $S =\{x\in\zzz\ :\ x+1\mid x-3\}$. Determine the set $S$.
Your answer should be given as an explicit list of the elements of $S$.
Prove your answer. You may use any other exercises stated in class.
Due Thursday, Sep 29 at the beginning of class, handwritten on paper.
Make sure to put your name on the paper.
LaTeX homework template has been posted. In addition to the formatting, the template also includes LaTeX macros useful for the current material (such as non-divisibility and congruence) and it may also be of interest for its mathematical content and style; it contains model proofs. Please test the template asap and send comments to the instructor; this was a first attempt and can surely be improved.
Click here to check whether this is the right course for you.
Homework submission will be on Gradescope, accessible via Canvas.
Homework problems will be posted on this website. They will be organized into weekly assignments on Gradescope. You will have to hand in your homework on Gradescope in PDF prepared by Latex. Your graded work will be returned on Gradescope. Homework is due every Monday by 11:00pm.
The instructor places an emphasis on interaction with the students. One method of feedback during class is the zoom "chat" feature which permits students to respond to the instructor's questions in private.
Outside class, email is the best way to communicate with the instructor.
Instructor: László Babai
Class schedule
Please send email to the instructor with answers to these questions, even if you are only auditing the class, did not register, or have an unusual status. Your answers to these questions will help me to better plan the course. Please write "CMSC 37115 data" in the subject.
While this course will not be identical with the Autumn 2021 course with the same title and course number, the overlap will be significant, and a most valuable source of information about the course content is the Homework, material covered section of the 2021 course website.
This course intends to introduce the students into the ways of mathematical thinking, from intuition to formal statement and proof, via a number of interconnected elementary subjects most of which should be both entertaining and useful in their many connections to computer science.
Through a long series of examples, we practice how to formalize mathematical ideas and learn the nuts and bolts of proofs.
High-school-level familiarity with sets, functions, and numbers will be assumed.
The list of subjects includes
quantifier notation, free and bound variables, sets, setmaker notation, Boolean operations with sets, arithmetic operations with sets of numbers, powerset functions, injective, surjective, bijective functions, their relation to counting, predicates, characteristic functions of sets, counting subsets, relations, equivalence relations,
elements of number theory: divisibility (including divisibility by zero), gcd, Euclid's algorithm, lcm, congruences, Fermat's little theorem, Chinese Remainder Theorem,
polynomials, roots, factorization, complex numbers,
counting, binomial coefficients, finite probability spaces: sample space, probability distribution, events, independence, random variables, expected value, variance, Markov's and Chebyshev's inequalities,
limits, asymptotic rates of growth, asymptotic notation, polynomial growth, exponential growth, recurrences, generating functions,
undirected graphs, degree, paths, cycles, connectedness, trees, bipartite graphs, extremal graph theory, independent sets, cliques, chromatic number, planar graphs, random graphs,
directed graphs, strong connectivity, directed acyclic graphs (DAGS), tournaments, random walks, finite Markov chains.
Sequences of numbers will be a recurring theme throughout. Our primary interest will be their rate of growth (asymptotic analysis). From calculus, we shall review the notion of limits (especially at infinity). "Asymptotic thinking" about sequences is also the bread and butter of the analysis of algorithms.
It is meant for CS PhD students without a strong mathematical foundation. While the topics discussed belong to Discrete Mathematics, the emphasis is not on covering DM in depth but to develop the basic skills of approaching, interpreting, and producing mathematical statements and proofs.
A full score in this class is not equivalent to an "A" in a DM course. For this reason, the grade of "A" will NOT be available in this course. An "A-" will be given not to the top problem solvers but to those who show the greatest progress. If you aspire for a graduate-level "A" grade, please take a course that is more challenging, such as the undergraduate "Honors Discrete Mathematics" course.
One student described their expectation for this class with these words (slightly edited for brevity).
e-mail: laci(at)u.e. (expand abbreviation) and lbabai(at)[Google's mail service]
I have experienced a variety of uncertainties about email. When sending me a message, please use BOTH email addresses to help ensure that I see it.
Office hours: Friday 2:00-3:30pm, JCL 346.
(The previously announced office hours by zoom on Saturday 5:00-6:00pm
have been canceled for lack of attendance).
Please send me email if you wish to have a one-on-one appointment.
TA: Tiago Royer
e-mail: royer(at)u.e. (expand abbreviation)
Your primary text will be your course notes.
So please make sure you don't miss classes.
If you do, try to discuss the class with a peer.
The instructor uses iPad in lieu of the whiteboard;
the iPad notes are posted on this website after each class.
Online resources
DM: Instructor's Discrete Mathematics Lecture Notes (PDF)
FPS: Finite Probability Spaces (updated fragment of DM Chap. 7) (PDF)
Discrete Math Lecture Notes by Morgan Sonderegger and Lars Bergstrom (PDF) (detailed notes based on the instructor's 2007 DM class, but not proofread by instructor)
Euclid's algorithm and multiplicative inverse handout
Repeated squaring algorithm handout
Puzzle problems for challenge and fun
Printed text:
J. Matoušek, J. Nešetříl: "Invitation to Discrete Mathematics," published by Oxford University Press, ISBN# 098502079.
(Note: the second edition of this text appeared in 2009, the third
more recently. You may also use the first edition. The numbering
of chapters has changed.)
Recommended reference (undergraduate text):
Kenneth H. Rosen: Discrete Mathematics and its Applications (n-th edition, n=2,3,4,5,...)
Grading scheme Homework 85% Class participation 15%
Primary method of class participation: zoom "chat".
Homework problems are posted on this website. They are organized into weekly assignments on Gradescope. Problems may be updated. Please make sure to refresh your browser to get the latest version of the homework problems.
Errors may occur, both in class and in the posted version of the problems. Please recheck the website, especially if you suspect an error.
If you find an error or something looks suspicious in an assignment (e.g., it seems too easy or it has already been discussed), please notify the instructor (by email). If you are the first to point out an error, you may receive bonus points. If the error is of a trivial nature (e.g., the statement is false for $n=0$ but true otherwise), you are expected to discover the error, correct the problem, and solve the corrected problem.
Homework help. If you encounter difficulties with an assigned problem, you may contact the instructor by email.
Categories of exercises.
Collaboration on current homework is discouraged but not prohibited. If you do collaborate, state it at the beginning of your solution (give name of collaborator, state nature of collaborationn -- see expmaples in the template). There is no penalty for acknowledged collaboration on homework. The collaboration can involve passing ideas, but not solutions. COPYING is strictly prohibited. Understand the ideas discussed and give your own rendering.
The same applies to other sources such as the Web: give the source (URL), but DO NOT COPY. Understand; then write your own version without looking at the source or your notes. Acknowledge the source, include the URL at the beginning of your solution.
On Gradescope you will find brief descriptions of each problem. This descriptions do NOT constitute the problem statement. You find the authentic statement of each question of the course homepage (click "HOMEWORK and material covered" on the banner).
Please upload one PDF file per week. Upload this file in two copies, one for the "ORD" assignment set and one for the "BON" assignment. IMPORTANT: As you upload your PDF file, follow the instructions to assign pages to each solution. Failing to do so makes grading harder.