$\newcommand{\nnn}{\mathbb N}$ $\newcommand{\zzz}{\mathbb Z}$ $\newcommand{\rrr}{\mathbb R}$ $\newcommand{\ccc}{\mathbb C}$ $\newcommand{\fff}{\mathbb F}$ $\newcommand{\eee}{\mathrm e}$ $\newcommand{\vf}{\varphi}$ $\newcommand{\vt}{\vartheta}$ $\DeclareMathOperator{\Div}{\mathrm Div}$ $\DeclareMathOperator{\lcm}{\mathrm lcm}$ $\DeclareMathOperator{\var}{\mathrm Var}$ $\DeclareMathOperator{\cov}{\mathrm Cov}$ $\DeclareMathOperator{\period}{\mathrm per}$ $\DeclareMathOperator{\rank}{\mathrm rk}$ $\DeclareMathOperator{\trace}{\mathrm Tr}$ $\DeclareMathOperator{\span}{\mathrm Span}$ $\DeclareMathOperator{\sgn}{\mathrm sgn}$ $\DeclareMathOperator{\inv}{\mathrm Inv}$ $\DeclareMathOperator{\diam}{\mathrm diam}$

CMSC 37115: Introduction to Mathematical Reasoning via Discrete Mathematics

Autumn 2021


What's new | Questionnaire | Course description | Is this the right course for me? | Contact | Texts | Grading | Rules on homework | Policy on collaboration and web sources | Zoom in class | Submitting homework on Gradescope | HOMEWORK, material covered | LaTeX homework template | Statistics | Instructor's past courses

What is new?

PRESS "REFRESH" to find out!

This page is under construction. Refresh your browser to find the latest material.


December 2 lecture/problem session iPad notes posted.

November 30 lecture iPad notes posted.

November 20 problem session iPad notes posted.

November 13 problem session iPad notes posted.

November 6 problem session iPad notes posted.

October 23 problem session iPad notes posted.


First homework assignment (assigned in class on Tuesday, Sep 28).
Let $B =\{x\in\zzz\ :\ x\mid x-4\}$. Determine the set $B$. Your answer should be given as an explicit list of the elements of $B$. Prove your answer. You may use any DO exercises stated in class.
Due Thursday, Sep 30, at the beginning of class, handwritten on paper. Make sure to put your name on the paper.


*     *     *     *

The assignments will be posted on Gradescope (except for the first assignment, above). The actual problems to which the assignments refer are posted on this website. The assignments are due Monday at 11:00 pm. Please let me 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). (Do NOT use the template on the 2020 website.) The solutions will be so short, you can fit several on each page. Leave ample space between solutions, do not crowd your page, leave room for grader's comments. 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 on this website.)

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 a model proof. 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.


General information. This is an in-person course except for the last week that will be held online (Nov 30 and Dec 2). The course may switch to online if public health directives so require. Even while in-person, the course has a Canvas site that will assist the course in several ways. Office hours will be by zoom, accessible via Canvas. 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


Questionnaire

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.

Go to top


Course description

While this course will not be identical with the Autumn 2020 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 2020 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, 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.

Go to top


Is this the right course for you?

Warning: This is not a Discrete Mathematics course

In spite of the clear title of the course, some students seems to think this is a "graduate level Discrete Mathematics course." Emphatically, it is NOT.

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).

If you share this attitude, this course is for you. If you are not sure whether this is the right course for you, please send me email.

Go to top


Contact information, office hours

Instructor:   László Babai     

    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 zoom, Saturday 5:00-6:00pm.
Please send me email if you wish to have a one-on-one appointment.

Go to top


Text

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.

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,...)

Go to top


Grading scheme    Homework 85%     Class participation 15%

Primary method of class participation: zoom "chat".


Rules on homework

There will be weekly homework assignments, always due Monday 11:00pm. Typeset your homework in LaTeX, compile it with pdflatex which will produce a PDF file, upload the PDF file on Gradescope. A LaTeX homework template is provided. 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.
If you are not familiar with LaTeX, tell the instructor, and you will get grace period up to two weeks to learn it. All homework must be typeset in LaTeX starting Monday, October 12, but I will appreciate if you use LaTeX from day one. Print your name on each sheet.

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.

Policy on collaboration and web sources

Studying in groups is encouraged.

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.

Go to top


Zoom during class

We will be using the Zoom "chat" feature in this class. Please send your answers in private messages to the instructor. A public message denies other students the opportunity to do their own thinking about the problem.

Submitting homework on Gradescope

Log into the Canvas site for this class. On the navigatioon bar to the left, click "Gradescope". You will see two assignments, "ordinary" problems (ORD1) and "bonus" problems (BON1). Click "upload images" even if you have no itention to upload any images. This will allow you to see the details of the assignments (which problem corresponds to what problem on the course website).

Please upload one PDF file per assignment (so typically two PDF files per week). IMPORTANT: As you upload your PDF file, follow the instructions to assign pages to solutions. Failing to do so makes grading harder.

Instructor's home page

Department of Computer Science home page

Go to top