What's new?

Final exam: Monday, December 8, 10:30 - 12:30 (closed book as usual) (32% of course grade)
Take a good night's sleep before the test, do not study till dawn.

Homework statistics posted (click "Statistics")

Quiz-4 and combined test statistics posted (click "Statistics")

Quiz-4 posted (click "Grading, tests" on the banner). Solve the problems without the time pressure before the tutorial (Thu, Dec 4, 4:30pm).

Homework sets #14 and #15 posted. Set #14 includes DO problems stated in class only; due Monday, Dec 1. Set #15 is due Wed, Dec 3.

Last week of classes: Mon, Dec 1: Quiz-4. Tuesday, Dec 2: TA's office hour. (Moved from Thursday.) Tutorial: Thursday, Dec 4, 4:30pm. (Moved from Tuesday.) Last class (Friday, Dec 5) mandatory. Final exam Mon, Dec 8, 10:30 - 12:30.

Homework set #13 posted. DO problems stated in class due Monday, Nov 24; DO problems not stated in class due Tuesday, Nov 25, before the tutorial; HW problems due Wed, Nov 26.

Go to top

Old News

This site is up

Quiz-3 statistics posted. Homework statistics updated to HW#10 (due Nov 12). Click the "Statistics" tab on the banner.

Third quiz posted. Click the "Grading, tests" tab on the banner.

Homework statistics posted. Click the "Statistics" tab on the banner.

Midterm statistics posted. Click the "Statistics" tab on the banner.

No tutorial on Tuesday, Oct 28.

Test statistics posted.

Test dates, grading scheme posted. Click "Grading, tests" on the banner.

Quizzes 1 and 2 posted. Click the "grading, tests" tab on the banner. Solve the Quiz problems at your leisure.

Questionnaire

Please send email to the instructor with answers to these questions, even if you are only sitting in on the course, 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," or "2nd year TTI-C grad student specializing in pattern recognition," or "Student at large specializing in oceanography" etc.)
• Do you expect to graduate this quarter?
• Did you register for this class? (It is ok if you did not.)
• If you did, what type of grade do you seek (letter, 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 classes 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 (title and number of course, name of instructor).

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

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

Teaching assistant:

Raghav Kulkarni    raghav(at)cs(dot)uchicago(dot)edu.

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

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

Tutorial: Tue 4:30 - 5:20 pm, Ry-277. Attendance mandatory unless waived by instructor.

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)

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 text is out of print. If you were unable to get a copy over the internet or otherwise, please tell the instructor; the department has a few spare copies.)

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 (1st quiz 4%, the other three 6% each), class participation (5%) and the final exam (32%).

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.

Test dates

October 8 Wednesday: first quiz (4%)

October 17 Friday: second quiz (6%)

October 27 Monday: midterm (16%)

November 10 Monday: third quiz (6%)

December 1 Monday: fourth quiz (6%)

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

Go to top

Rules on HOMEWORK

Go to top

Policy on collaboration

View the instructor's class material from previous years

Return to the Department of Computer Science home page

Go to top