What is new?

PRESS "REFRESH" to find out!

Final exam posted.

Pre-final review (optional) Saturday, Dec 2, 3:30-5:30pm, Ry-276

TA's pre-final office hour Friday, Dec 1, 3:30-5pm, Ry-276

Final Exam Tuesday, December 5, 10:30-12:30, Ry-251

HW statistics posted

Homework set #18 (DO, CH problems) and material covered posted.

Homework set #17 and material covered posted. Due Thursday, 11-30.

Online Linear Algebra text available both in double column and in single column formats. (Click the "Texts" tab on the banner.)

Homework set #16 and material covered posted. HW includes added graph theory. Due Tuesday, 11-28.

Two sets of statistics posted: HW 1--11 and midterm.

Midterm posted. Solve the problems on your time.

Binary search algorithm handout posted.

Repeated squaring algorithm handout posted.

Applications of CRT to computer science and technology have been added as items 5.27 and 5.28 to the class notes.

Starting Thursday, October 12,

Midterm announced: Thursday, Nov 2. Grading scheme announced. (Click "Grading, tests" on the navigation bar.)

Euclid's algorithm and multiplicative inverse handout posted.

Instructor: László Babai

Class schedule

• Lectures: TuTh 11:00-12:20 Ry 251 (new location! starting Thu, Oct 12)
  First class: Tuesday, Sep 26
  Last class: Thursday, Nov 30 (mandatory)
• Problem session: Wed 4:30-5:30 Ry 276
  Attendance mandatory unless waived by instructor. The main theme is solving problems, especially homework and test problems.
  First problem session: Wednesday, Sep 27.
• Question/answer session with the instructor: Wed 17:30-19:00 Ry 276 (optional)
• TA's office hour: Monday 5:00-6:00 Ry 162 (optional)
• Midterm   Thursday, November 2.
• TA's extra pre-final office hour: Friday, Dec 1, 1:00-2:00pm Ry 162 (optional)
• Pre-final review with instructor (optional): Saturday, Dec 1, 3:30-5:20, Ry-276
• Final Exam: Tuesday, December 5, 10:30-12:30, Ry-251

Questionnaire

Please send email to the instructor with answers to these questions, even if you are only sitting in on the class, did not register, or have an unusual status. Your answers to these questions will help me better to plan the course. Please write "CMSC 37110 data" in the subject.

• Your name
• Your field, area of specialization, and status at the university (e.g. "3rd year math major with minor in economics," or "2nd year TTI-C grad student specializing in pattern recognition," or "PSD Masters student specializing in oceanography" etc.)
• If you are a CS graduate student, who is your advisor?
• Do you expect to graduate this quarter?
• Did you register for this class? (It is ok if you did not, I still want to hear from you.)
• If you did, what type of grade do you seek (letter grade [A-F], P/F, audit)? (You can change your mind about this later.)
• Are you fulfilling a requirement with this class? If yes, please elaborate.
• Please tell me about your math background. Have you had proof-based courses before? Have you been exposed to creative problem solving? If so, tell me in what course(s) or program(s). Tell me about the four most advanced math courses you have taken (name of instructor, title of course, course number if at Chicago, name/location of institution).

Go to top

Course description

This course intends to introduce the students into the ways of mathematical thinking, from intuition to formal statement and proof, through a number of interconnected elementary subjects most of which should be both entertaining and useful in their many connections to classical mathematics as well as to real-world applications.

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 relations will be assumed.

The list of subjects includes quantifier notation, elements of number theory, methods of counting, asymptotic rates of growth, recurrences, generating functions, finite probability spaces, undirected and directed graphs, basic linear algebra, finite Markov Chains (a class of stochastic processes).

Sequences of numbers will be a recurring theme throughout. Our primary interest will be the rate of growth of such a sequence (asymptotic analysis). From calculus, the notion of limits (especially at infinity) is required background. "Asymptotic thinking" about sequences is also the bread and butter of the analysis of algorithms, the subject of a course offered in Winter.

Go to top

Course information

Office hours: by appointment (please send e-mail)

TA: Taylor Friesen          e-mail: friesen@cs(dot)etc.

Office hours:    Monday 5pm-6pm
       Ry-162 ("Theory lounge")

Go to top

Text

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

Instructor's Discrete Mathematics Lecture Notes (PDF)

DM Lecture Notes by Morgan Sonderegger and Lars Bergstrom (PDF) (detailed notes based on the 2007 class, but not proofread by instructor)

Repeated squaring algorithm handout

Euclid's algorithm and multiplicative inverse handout

Instructor's online Linear Algebra text in two-column format and in in single-column format

Lecture notes on linear algebra and spectral graph theory by Madhur Tulsiani and the instructor, REU 2013

Problem sheets from instructor's 2012 REU course, including linear algebra problems and "puzzle problems."

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

Go to top

Grading scheme    Homework 35%   Midterm 20%   Final exam 40%   Class participation 5%

Rules on homework

If you find an error or something that looks suspicious in an assignment, please notify the instructor (by email). If you are the first to point out an error, you may receive bonus points.

There are various categories of homework.

• "DO" exercises are meant to check your understanding of the concepts. Do them on time but do not hand them in. If you fail to slve them, yo may be left behind during the subsequent class. If you encounter any difficulties, try to find a peer who can help. Also, take advantage of the TA's office hours. You may also contact the instructor know by email. Try to solve the "DO" exercises before Wednesday's problem session; they may be discussed at that time.
• "HW" problems are to be handed in before class on their due date, typically the next class. Please typeset your solution in Latex, print the PDF file and hand it in. There is a one-week grace period for those not familiar with Latex -- on Thu Sep 28 and Tue Oct 3 you may hand in your handwritten solution.
• Challenge problems ("CH") don't have a specific deadline except they expire once they have been discussed in class. If you are working on a challenge problem, please send email to the instructor so as to avoid discussion of the problem before you handed in the solution.

  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.

• "Reward problems" are creative problems you are not asked to hand in. You will find their solutions rewarding.

Policy on collaboration

View course material from prior years

Return to instructor's home page

Return to the Department of Computer Science home page

Go to top