Class 18 notes posted (12-03 8pm). Some HW assigned on Tuesday, 11-26
is due Thursday, 12-05.
Remember: Problem session Wed, 12-04, 4:30pm,
last class Thu, 12-05. Attendance counts
toward "class participation" score, included in grade.
HW17 posted (17.1-17.23 posted 11-27, 11am, the rest posted 11-28, 10:30pm)
HW 1-15 statistics posted (11-25)
HW16 posted (11-22, 4am) Due Tuesday, 11-26.
HW15 posted (11-20, 1am) Due Thursday, 11-21.
HW 1-12 statistics posted (11-16)
HW14 posted (11-16, 2:20pm) Due Tuesday, 11-19.
HW13 posted in full (11-12, 10pm -- 11-13, 1:30am) Due Thursday, 11-14.
HW12 posted (11-9, 1pm-4:30pm). Due Tuesday, 11-12.
HW 1-8 statistics posted (10-30 8:10pm)
"Divisor Game" added to the material of Class 1.
HW1 - material of first class posted. Please periodically review past class materials, make sure you can still solve the older problems and recall the definitions.
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, 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.
e-mail: laci(at)cs(dot)etc. and lbabai(at)[Google's mail service]
Office hours: by appointment (please send e-mail)
TA: Jesse Stearn
e-mail: [firstname]a[lastname](at)uchi...
Office hours: Mon 5:00pm-6:00pm JCL 205
Your primary text will be your course notes, so please make sure you don't miss classes. If you do, you should copy somebody's class notes and discuss the class with them.
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 2007 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; I will post the correspondence.)
Recommended reference (undergraduate text):
Kenneth H. Rosen: Discrete Mathematics and its Applications (n-th edition, n=2,3,4,5,...)
Grading scheme Homework 90% Class participation 10%
Unless otherwise stated, all homework is due next class. Hand it in before class.
Homework is stated in class and will also be posted on the website. In case posting is delayed, do the homework as assigned in class. If there is a discrepancy between homework stated in class and posted on this site, the posted version rules. Additional problems, not stated in class, may also be assigned in the posting. Please make sure to refresh your browser to get the latest version of the homework.
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 probelm, try to find a peer who can help. Also, take advantage of the TA's office hours. You may also contact the instructor by email. On Piazza, you may ask for clarifications of problems, but please do not ask for a solution before the due date of the problem. DO NOT POST solutions of HW problems on Piazza before their due date.
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.