[Jump to Most Recent Assignment]

Introduction to Discrete Mathematics, Spring 2012

Instructor: Michael Pelsmajer
Office: E1 206
Office Hours: by appointment (Meaning: I am happy to meet you, but I'm not going to sit around my office, not knowing if anyone is going to show up.) To arrange a meeting, talk to me before or after class, or send an e-mail with a list of convenient times.
Office Phone: 312-567-5344 (but e-mail is better)
E-mail: pelsmajer_(AT)_iit_(DOT)_edu

Teaching Assistant: Jinyu Huang
Office Hours: Friday 4:15pm-6:15pm in E1 129
(Jinyu will take questions by e-mail as well.)
E-mail: jhuang14_(AT)_hawk_(DOT)_iit.edu
Schedule of all Math Teaching Assistants in E1 129
(They should probably be able to help, too.)

[ MATH 230 Standard Syllabus (updated 2006)]
[Spring 2012 Course information]


Suggestions for Writing up Math Homeworks (without LaTeX)
It is expected that you will check your answers to all odd-numbered problems yourself: answers are in the back of the book, while the student solution book has complete solutions for odd-numbered problems.

The book has a web site with nice extra resources. For example: Common Mistakes in Discrete Math (organized by chapter).

Daily Schedule and Assignments

Problems and pages are from 6th edition, except where noted

[Jump to Most Recent Assignment]
Monday, January 9: Day 1, 3:15pm in Siegel Hall room 202.
Read "Spring 2012 Course information", "To the Student" (in the beginning material of the book), "Suggested Guidelines for Writing up Math Homeworks", and the beginning of "Common Mistakes in Discrete Math" (one page carefully, and then skim the Chapter 1 material).
By Wednesday, January 11:
Read, understand, and memorize alternate ways to say, "if p, then q" (page 6).
Section 1.1 (page 16-21): #9,13,14,17ab,18,20
You may need/wish to read other parts of Section 1.1. Also, it can be quite helpful to read ahead a bit to be prepared for the next class.
Due Friday, January 13:
Section 1.1: #12, 27bd, 28d, 31d
Section 1.2: #5,6, 31
No class on Monday, Jan 16
Due Wednesday, January 18:
Section 1.2: 7ab
Section 1.3: #9,10, 12,13,14, 20abcd.
All homework thus far will be collected today!

Due Friday, January 20:
Section 1.3: #7,8, 23, 25, 44
Section 1.4: #9,10, 19,20,21,22, 27,28, 31
Or if you have the 7th edition:
Section 1.4: #7,8, 23,25, 44
Section 1.5: #9,10, 19,20,21,22, 27,28, 31
Due Monday, January 23:
From Section 1.5 (6th edition) or Section 1.6 (7th edition):
Read Definition 1.
Study the first column of Table 1 (and column 2, too) until you understand why they are all valid Rules (but you can skip "Resolution").
#9,10 (but you don't need to explain using rules of inference; it's enough that you draw all the correct conclusions and that you do not draw any extra, unjustifiable conclusions)
From Section 1.6 (6th edition) or Section 1.7 (7th edition):
#1, 5, 15, 17 ("contraposition" is "contrapositive")
Due Wednesday, January 25:
From Section 1.6 (6th edition) or Section 1.7 (7th edition):
Read Examples 4 and 9.
#6, 9,10,11,12,13,14, 16, 24 (don't use "direct proof" for 24)
Homework will be collected today!

Due Friday, January 27:

Due Monday, January 30:

Due Wednesday, February 1:

Due Friday, February 3:

Due Monday, February 6:

Due Wednesday, February 8:

Next up: Cardinality, Section 2.4 (6ed.) or 2.5 (7ed.). Then finish Chapter 2 Sections 3 & 4 (6th edition) or Sections 3–5 (7th edition).

Due Friday, February 10:

Due Monday, February 13:

Due Wednesday, February 15:

Exam 1 will be Friday, February 17. It covers Chapters 1 and 2 (except for topics that we skipped).

Due Monday, February 20:

Due Wednesday, February 23:

Due Friday, February 25:

Due Monday, February 27:

Due Wednesday, February 29:

Due Friday, March 2:

Due Monday, March 5:

Due Wednesday, March 7:

Due Friday, March 9:

Due Monday, March 12:

Due Wednesday, March 14:

Due Friday, March 16:

Due Monday, March 26:

Due Wednesday, March 28:

Due Friday, March 30:

Due Monday, April 2:

Due Wednesday, April 4:

Due Friday, April 6:

Due Monday, April 9:

Due Wednesday, April 11:

Wednesday April 11, 12:45-1:40pm, E1 102:
IIT Math Contest This is not part of Math 230. (Math 230 students are good candidates for this).

Exam 2 will be Friday, April 13. It covers Chapters 3 and 4 (7th edition: 3,4,5) (except for topics that we skipped).

Due Monday, April 16:

Due Wednesday, April 18:

Due Friday, April 20:

Monday, April 23 is Menger Day. Please attend the Menger lecture instead of the usual class. And RSVP (using the link on the Menger Day web page). Also, I highly recommend the Math Club event. And the poster session.

Due Wednesday, April 25:

Due Friday, April 27:

"Due" Monday, April 30:

The final exam will be May 4, 10:30am-12:30pm, in the usual classroom.

Subset Sum Example

I didn't talk as much about ways that an algorithm could be bad.
Here's an example that's not in the book:

Problem: Given a finite sequence of integers a1,a2,...,an, is there a non-empty subset of them whose sum equals zero?

Tiny example: For the list "3,7,-8", there are 7 non-empty subset sums:
  3+7-8, 3+7, 3-8, 7-8, 3, 7, -8,
none of which equals zero.

Attempted algorithm: For each subset, add up the elements and check if they are zero.

But! You haven't explained what order to consider the subsets! (Our example had only 3 elements, but it's less easy if you have a sequence with 10 elements - think about it).

Okay, let's say that you manage to write an algorithm that considers every non-empty subset one at a time (and is otherwise correct)...

But #2 The number of subsets to check is 2^n-1. Exponential functions grow incredibly fast, so your algorithm will be too slow: no one will have the patience to wait for it to finish when n=100 (and worse for larger n - don't even think about tackling a book-full of numbers with this algorithm).

Extended Euclidean Algorithm, version from class

The 6th and 7th edition are not consistent, so I will repeat and rephrase what I presented in class.

At the end, you'll have g = ak + bl using the original "a" and "b".