CMSC 37110-1: Discrete Mathematics -- Autumn 2007

______________________________________________________________________________________________________________________________________________________________ What's new | Course description | Course info | Text | Grading, tests | Policy on collaboration | Assignments | Statistics _____________________________________________________________________________________________________________________________________________________________

What's new?

Complete Homework, Quiz, and combined (tests plus homework) statistics posted. (Click the "Statistics" tab on the banner.)

Final Exam at   8 am on Tuesday, December 4.

2007 Final Exam

2007 Nov 27 Quiz

2007 Second Midterm

2007 First Midterm

2006 Final Exam

2005 Third Midterm

2006: Selected HW Problems


Old News

The first chapters of the instructor's Linear Algebra lecture notes are available online (Nov 11). Please report any errors by email.

Homework and test statistics have been posted (Oct 28, 9pm). Click "Statistics" on the banner.

Test dates and grade composition posted (click "grading" tab on banner).

Course description has been added (9-28). Click tab on banner.


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.

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 assistants:

Sourav Chakraborty     sourav(at)cs(dot)uchicago(dot)edu.

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

The TAs hold office hours Monday, Wednesday 5:00-6:00pm in Ry-162 (the "Theory Lounge").


Classes: TuTh 9:00 - 10:20 am, Ry-276

Tutorial: Th 4:30 - 5:20 pm, Ry-276. 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. A few copies will be available to share; possibly more copies can be obtained on the web.)

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 frequent Homework (posted), tests, and class participation.

Grade composition: homework 25%, two midterms 16% each, a quiz 8%, final exam 30%, class participation 5%

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 23 Tuesday: first midterm

November 13 Tuesday: second midterm

November 27 Tuesday: quiz

December 4, 8-10am: final exam

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