12-03 1:48pm Today's notes have been posted (click "SLIDES" on the banner)
12-02 8:10pm Today's notes have been posted
12-01 1:40pm Today's notes have been posted
11-29 8:11pm Statistics posted. Click "Statistics" on the banner.
11-19 0:30am Schedule updates for the rest of the term.
11-27 10am new batch of problems due Tuesday, December 8, 12:30pm and material posted as items 16.50--16.222 on this website.
11-21 5:20pm assignments due Wed Nov 25 3pm posted on Gradescope
11-19 4:30 New batch of homework due Nov 25 and material covered on 11-17 posted.
11-19 2pm Today's notes have been posted
11-18 9:40pm Today's notes have been posted
11-17 1:40pm Today's notes have been posted
11-12 10pm Assignments HW7a, HW7b, HW7c, Bonus7 posted on Gradescope. Due Monday, Nov 16
11-02 9:20pm The TA's office hours have been moved from Friday 7:40 pm to Saturday 7:40 pm, starting this week, Nov 7, due to low-to-zero attendance. Take advantage of these office hours, come prepared with your questions.
10-28 3:45pm Problem set #8 updated, including illustration of the role of the Fundamental Theorem of Equivalence Relations in concept formation and through it, in human and artificial intelligence.
10-1 7:30pm The assignments
have been posted on Gradescope.
The actual problems to which the assignments refer are posted on
this website. The assignments are due Monday at 11:59 pm.
Late submissions will not be accepted. Please let me and
Xifan know immediately, by email, if you encounter any difficulties
with Gradescope, or if you find that a problem does not seem right.
Use the template provided on this website (click "LaTeX homework
template" on the banner). The solutions will be so short, you can
fit several on each page. Do NOT put more than
four problems on a page even if you think there is room.
Do not let a solution spill over to the next page.
REFRESH your browser
to find the up-to-date statement of each problem.
Problems may be updated, more explanation added, as questions
arrive or errors are found. (The time of the update will
always be noted.)
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. Please test the template asap and send comments to the instructor; this was a first attempt and can surely be improved.
9-29 8pm: The video of the 9-29 lecture has been posted on the Canvas/Panopto site.
9-29 4pm: Updated slides of week 1, class 1 posted. Click "SLIDES" on the banner. Solve the DO exercises stated in the slides, by the Wednesday problem session.
Click here to check whether this is the right course for you.
General information. This is an online course, delivered via zoom sessions set up on the Canvas site for the course. 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 and your graded work will be returned there. Home work is due every Monday by 11:59pm. Late homework will not be accepted. Class notes (slides and iPad notes) will be posted on this webite. Video recordings of lectures and problem sessions will be available on the Canvas/Panopto site.
The instructor places an emphasis on interaction with the students. The primary method of feedback during class is the zoom "chat" feature. 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.
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, 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,
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)cs(dot)etc. 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: by appointment (please send e-mail)
TA: Xifan Yu email: (firstname)(at)uchi...etc
Office hours: Saturday 7:40pm - 8:30pm, starting November 7. (The office hours are being moved from the previous Friday evening schedule to Saturday evenings because of the low-to-zero attendance.)
Your primary text will be the course notes (slides, iPad notes). These sources may not be easy to interpret without the verbal explanations given in class and the interaction with the instructor during class. So please make sure you don't miss classes. If you do, try to discuss the class with a peer.
Online resources
LN: Instructor's Discrete Mathematics Lecture Notes (PDF)
FPS: Finite Probability Spaces (updated fragment of LN Chap. 7) (PDF)
DM 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 92% Class participation 8%
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.
Solutions to Challenge problems don't earn you credit toward your grade but they do earn you the instructor's attention, in addition to giving you valuable experience.
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). 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.
Note that you can set your name in your Zoom profile, so you do not have to go with whatever has been assigned. You may include your preferred pronouns after your last name. I recommend that you follow this practice for multiple reasons. If you set yourself a name that cannot be easily matched to your name on record with the University, please let your instructor know.
You are strongly encouraged to attend the classes synchronously and be an active partiticipant. Our Zoom class meetings will be recorded and saved to the cloud to allow students enrolled in this class to review it and to allow students enrolled in this class who cannot participate synchronously to benefit from the class. It is illegal for anyone other than the instructor to record the class or to post a recording or to pass it on to anyone. The recording is intended to be available only to the participants of this class and will not be available after the quarter ends. However, I am not in the position to prevent illegal activity. If you have FERPA concerns, please mask yourself accordingly, e.g., by turning off the video and using an alias.