CMSC 37110-1: Discrete Mathematics

Autumn 2010

What is new?

PRESS "REFRESH" to find out!

Multiple STATISTICS posted: Q4, HW total, all tests so far, ALL-BUT-FINAL with approximate grade equivalents. Click "Statistics" on the banner.

Fourth quiz posted. Click "Grading, tests" on the banner. Solve the problems on your own time.

PRE-FINAL TUTORIAL Monday, Dec 6, 4:30pm. Bring your questions!

Homework set #13 posted. This set consists of "DO" exercises only, due Tuesday, Nov 30, before the tutorial.

Homework set #12 posted. Due Monday, Nov 29.

Homework set #11 posted. Due Monday, Nov 22.

Homework posted in PDF, in addition to being posted, as before, in HTML. Click "Homework in PFD" on the banner. Some browsers make it hard to see the current version of a previously seen PDF file; to see you have the latest version, please compare it with the HTML file. The purpose of posting it in PDF is that some browsers have difficulty interpreting the jsMath formulas embedded in the text. If you have no trouble reading the formulas in HTML, you do not need to check the PDF file. Please report any difficulties reading the formulas in the HTML file. Note that the hyperlinks don't work in the PDF version.

HOMEWORK FOR MONDAY, Nov 15:Solve Problem 2 of Quiz-3 (almost all graphs have much larger chromatic number than clique number). (Posted as Homework set #9.)

Quiz-3 statistics and cumulative test statistics posted. Click "Statistics" on the banner.

Third quiz posted. Click "Grading, tests" on the banner. Solve the problems by Tuesday, before the tutorial. (Do not hand in.) You may hand in solutions to the bonus problems for extra homework credit at twice the bonus point value stated on the quiz. Due Monday before class. (Not required.)

2007 lecture notes by Morgan and Lars posted - check it out! Click "Texts" on the banner.

Homework set #9 posted. Due Monday, Nov 8.

Homework set #8 posted. Due Friday, Nov 5.

Midterm statistics and cumulative test statistics posted. Click "Statistics" on the banner.

Midterm posted. Click "Grading, tests" on the banner and then "midterm." Solve the problems by Tuesday, before the tutorial. (Do not hand in.)

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 "student at large 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

Old news

Homework set #7 posted. Due Friday, Oct 29.

MIDTERM RESCHEDULED to Friday, Oct 29.

Homework set #6 posted. Due Monday, Oct 25 and Wed, Oct 27.

TA's office hours moved from Thu 4:30 to Thu 6pm.

Quiz 2 statistics posted. Press "Statistics" on the banner.

Quiz 2 posted. Click "Grading, tests" on the banner.

If you have not done so yet, please answer the questionnaire.

Quiz 1 statistics posted. Click "Statistics" on the banner.

There will be no written homework for Monday, Oct 11. Review the test; solve what you missed. Review all the earlier "DO" exercises.

Quiz-1 has been posted. Click "Grading, tests" on the banner.

Practice problems for the test have been posted (HW set #2). Click "homework" on the banner. The test will be Friday.

Test dates have been posted. Click "Grading, tests" on the banner. FIRST QUIZ Friday, October 8.

Homework set #1 has been posted. Click "homework" on the banner. Problems due Monday and Wednesday.

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, number theory, methods of counting, 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

Instructor: László Babai Ryerson 164 e-mail: laci(at)cs(dot)uchicago(dot)edu.

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

Teaching assistant:

Denis Pankratov pankratov(at)cs(dot)uchicago(dot)edu.

The TA holds office hours Thursday 6 - 7 pm in Ry-162 (the "Theory Lounge").

Classes: MWF 11:30 - 12:20, Ry-277

Tutorial: Tue 4:30 - 5:20 pm, Ry-277. Attendance mandatory unless waived by instructor. The main theme is solving problems, especially homework and test problems.

LAST CLASS: Friday, December 3. Attendance mandatory.

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.

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)

Instructor's Linear Algebra lecture notes (PDF)

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

Grades are based on homework (25%), a midterm (16%), four quizzes (6% each), class participation (5%) and the final exam (30%).

The tests are closed-book; no notes permitted. Calculators are permitted for basic arithmetic (multiplication, division) but not for more advanced functions such as g.c.d. Calculators will seldom be of any use: the problems tend to involve very little numerical calculation.

Test dates

October 8 Friday: first quiz (6%)

October 15 Friday: second quiz (6%)

October 29 Friday: midterm (16%)

November 10 Wednesday: third quiz (6%)

December 1 Wednesday: fourth quiz (6%)

December 3, Friday: LAST CLASS. Attendance mandatory.

December 8 Wednesday, 10:30 - 12:30: final exam (30%)

Go to top

Rules on HOMEWORK
Unless otherwise stated, homework is always due the next class (before class). Please check the website for updates. The problems will be posted shortly after class. However, errors may occur, so please recheck the website, especially if you suspect an error. 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. "DO" problems are meant to check your understanding of the concepts. Do them but do not hand them in. If you encounter any difficulties, please check with the TA during office hours. Challenge problems don't have a specific deadline except they cease to be problems 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 the problem being discussed 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 respect, in addition to giving you valuable experience.
Go to top
Policy on collaboration
Studying in groups is strongly 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. DO NOT COPY someone else's solution: after the discussion, throw away any written records. 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.
View the instructor's class material from previous years

Return to the Department of Computer Science home page

Go to top