Course information (with Syllabus)
Very useful: Common Mistakes in Discrete Math (organized by chapters of the textbook).
A big focus of the course is learning to do proofs. Two nice quick overviews: by Heil and by Gallian
Instructor: Michael Pelsmajer
Email: pelsmajer[AT]iit[DOT]edu
Office Hours: Flexible. To arrange a meeting, talk to me before or after class, or send an e-mail with a list of convenient times. (You can also just stop by, and if I'm not too busy, I'm happy to talk.)
Office: Engineering 1 Building, Room 206 (312.567.5344 but email is usually better)
Teaching Assistant: Hansen Ha
Email: hha3[AT]hawk[DOT]iit[DOT]edu
Office Hours: Wednesdays 2pm-5pm in E1 129
Two other Teaching Assistants are especially good at helping Math 230 students, and they are both happy to help.
Gergely "Greg" Balint
Office Hours: Wednesdays 3:30pm-4:30pm and Thursdays 11:30am-1:30pm in E1 129.
Christodoulos "Chris" Mitillos
Office Hours: Sundays 2-4pm and Mondays 11am-12pm in E1 129 (after Feb.2)
| Date | Problems assigned today |
|---|---|
| Monday, January 14 |
All tthe worksheet problems (handed out during class today).
#3, 7,8,9,10 from either Section 6.1 (7th edition) or Section 5.1 (6th edition) #14, 26ab, 27 from either Section 6.3 (7th edition) or Section 5.3 (6th edition) |
| Wednesday, January 16 |
7th edition: #27,29,31,45 from Section 6.1 and #8,13,19abd,33,39 from Section 6.3
6th edition: #25,27,29 from Section 5.1 and #8,13,19abd,33,39,40 from Section 5.3 And two homemade problems: We will decorate a fan by placing a row of 5 stickers along each blade. (Click for picture.) X1. How many ways are there to place 10 different stickers on a 2-bladed fan? X1. How many ways are there to place 15 different stickers on a 3-bladed fan? |
| Friday, January 18 |
Read the "To the student" section (at the front of the book).
Read (and fill in the blanks) of page 3, from today's worksheet Read about Pascal's Triangle (in section 5.4 or 6.4). 7th edition: #17,25,46ab,48,49 from Section 6.1, #31abc,32ab from Section 6.3, and #3,4,12,29 from Section 6.4 6th edition: #17,23,40ab,42,43 from Section 5.1, #31abc,32ab from Section 5.3, and #3,4,12,29 from Section 5.4 |
| Monday, January 21 | (NO CLASS) |
| Tip: Briefly indicate your reasoning. If you can't quite put your finger on the "why", your answer is probably incorrect. | |
| Wednesday, January 23 |
Read about Graph Models in Section 10.1 of 7th edition or 9.1 of 6th edition
#15,16, 21 in section 10.1/9.1 #3,7 in section 10.2/9.2 #34,35,36,37,38, 61,62 in section 10.3/9.3 #3,4,5,6 in section 10.4/9.4 #1,2 in section 11.1/10.1 |
| Friday, January 25 |
#20f,23,24,28 in section 10.2 of 7th edition or
#20f,23,24,27 in section 9.2 of 6th edition
Read about Tree Models in Section 11.1 of 7th edition or 10.1 of 6th edition |
| Monday, January 28 |
Read, understand, and memorize alternate ways to say, "if p, then q" (page 6).
#13,14*, 17,18*, 21, 23,24* in Section 1.1 of 7th edition or #9,10*, 13,14*, 17, 19,20* in Section 1.1 of 6th edition (Do all problems, but only starred problems are to be written up and handed in.) |
| Wednesday, January 30 |
#9,11, 16*, 27a, 31bef in Section 1.1 of 7th edition or
#5,7, 12*, 23a, 27bef in Section 1.1 of 6th edition
#5,6*,7 from Section 1.3 of 7th edition or from Section 1.2 of 6th edition (Do all problems, but only starred problems are to be written up and handed in.) |
| Friday, February 1 |
#11 in Section 1.3 of 7th ed. or Section 1.2 of 6th ed. (Hint: when is an implication false?)
#7,9,10*,11,12*,13,14*,15, 33abcd in Section 1.4 of 7th ed. or Section 1.3 of 6th ed. (Do all problems, but only starred problems are to be written up and handed in.) |
| From now on, do all problems, but only starred problems are to be written up and handed in. | |
| Monday, February 4 |
#8*, 17 in Section 1.4 of 7th ed. or Section 1.3 of 6th edition
#1, 9, 10abcdef*, 19, 20*, 25ab, 27, 28abcde* in Section 1.5 of 7th ed. or Section 1.4 of 6th edition Give examples/counterexamples as justification whenever possible. |
| Wednesday, February 6 |
From Section 1.6 (7th edition) or Section 1.5 (6th edition):
Look at the first column of Table 1 and think about why each (except for "Resolution") is valid (perhaps reason with a truth table, as in the lecture). #1,2*, 9abcd, 10abdf*. For #9 and #10, don't name the Rules of Inference; just find the valid conclusions, and don't give any unjustifiable conclusions. From Section 1.7 (7th edition) or Section 1.6 (6th edition), #1, 6*, and read the section. |
| Friday, February 8 |
From Section 1.7 (7th edition) or Section 1.6 (6th edition),
#5, 9,10, 13, 15,16*, 25 #38*,39 (7th ed) or #32*,33 (6th ed) from Chapter 1 Supplementary Exercises |
|
You may feel that sometimes we are giving detailed proofs for facts that are fairly obvious. For instance, many facts about even and odd numbers are easy to see, and it seems wrong that I insist that you have to argue everything using only "2k" and "2k+1".
I kind of agree! But the point is to practice proofs, precise thinking and careful justification. The reason we use simple concepts like even/odd is so that we can avoid all confusions except for those having to do with logic. Play along, use only the most basic facts in your proofs, in order to benefit from this part of the course. Soon enough it will get harder and I won't insist that simple things are justified in excruciating detail. But you'll need to have a good grasp of logic and proofs in order to thrive when that time comes. |
|
| Monday, February 11 |
From Section 1.8 of 7th ed.,
do #1, 7, 29,30*, 33, 34* and read Example 6
or, from Section 1.7 of 6th ed., do #1, 5, 27,28*, 31, 32* and read Example 6 Sometime this week: look through the Chapter 1 tips here. |
| Wednesday, February 13 |
#26*,27, 32*,33 in Section 1.7 of 7th ed. or Section 1.6 of 6th edition
From Section 1.8 of 7th ed., read Example 13 and do #10*, 19, and 26* or, from Section 1.7 of 6th ed., read Example 13 and do #8*, 17, and 24* |
| Friday, February 15 |
#11,12* from Section 1.7 in 7th ed. or from Section 1.6 in 6th ed.
#13,14*, 38 from Section 1.8 in 7th ed. or #11,12*, 36 from Section 1.7 in 7th ed. |
| Don't forget, there are graduate students teaching assistants that specialize in discrete math! | |
|
"Redoable" problems: each problem that you got a 3 or less on is eligible.
Section 1.5/1.4 #28abcdeghij(all parts now), Section 1.6/1.5 #10abcdef(all parts now), and Section 1.7/1.6 #6, 16. Due Wednesday, February 20 (update: will accept Friday Feb.22 as well) |
|
| Monday, February 18 |
From Section 2.1,
7th ed. #1,2ab*,7,11,19,20* or
6th ed. #1,2ab*,5,9,17,18*
Exam Prep: Identify topics/questions that you do not yet understand. Ask during class Wednesday. |
| Wednesday, February 20 |
From Section 2.2, read the definitions of "disjoint" and "complement" and the section on Generalized Unions and Intersections
Do #3, 25, 27 (7th or 6th ed.) Prepare for the exam |
| Friday, February 22 |
From Section 2.1, #27, 29,30*, 35 (7th ed) or #23, 25,26*, 29 (6th ed)
From Section 2.2, #15b, 29 (7th or 6th ed) Prepare for the exam |
| Exam 1 on |
|
| Wednesday, February 27 |
From Section 2.3 (7th ed), #1,2*, 8abcdef*, 9abcdef, 10*, 11, 12*, 13, 15ab, 23, 31a, 32*, 59
Or, from Section 2.3 (6th ed), #1,2*, 8abcdef*, 9abcdef, 10*, 11, 12*, 13, 15ab, 19, 27a, 28*, 55 |
| Friday, March 1 | Read through subsections "Sequences", "Special Integer Sequences", and "Summations" from Section 2.4. (Since you have seen sequences and summations in calculus, we can move quickly, |
| Monday, March 4 |
From 7th edition, Section 2.4 #3,5bef, 9abcde, 29, 30*, 32*, 33bd
From 6th edition, Section 2.4 #3,5bef, 9abcde, 13, 14*, 16*, 17bd And read Cardinality (Section 2.5 in 7th edition, Section 2.4 in 6th edition); the goal is to get confused (which we will alleviate next class), so don't stop if you get stuck |
Quiz Wednesday, too! |
|
| Wednesday, March 6 |
From 7th edition, Section 2.5 #1abdf, 2abdf*, 4*, 15, 17, 28*, 29, and Problem X*: show that the union of two countably infinite sets is countably infinite. (Note: we skipped everything in Section 2.5 after Example 5.)
From 6th edition, Section 2.4 #31, 32*, 34*, 35, 37, 42*, 43, and Problem X*: show that the union of two countably infinite sets is countably infinite. |
| Friday, March 8 |
From Chapter 9 in 7th edition or Chapter 8 in 6th edition:
From Section 1 #1abd From Section 3 #1, 18*, 23 |
| Monday, March 11 |
From Chapter 9 in 7th edition or Chapter 8 in 6th edition:
From Section 1 #4*, 6*, 7 From Section 5 #2*, 27, 41, 43, 44*, 46* From Section 6 Read Definition 1 and Examples 1-4, then do #3, 4*, 5, 6*. (For fun and intuition, look at the last two problems of the section, where xRy if there is a strictly ascending path from x to y in the diagram.) |
| Wednesday, March 13 and Friday, March 15 |
From Section 3.1 #1, 2*, 3, 6*, 7, 8*, 13, 14*. Also 60* (6th ed) or 64* (7th ed.).
For #2, don't worry about whether or not you are hitting all the "characteristics". Rather: there's something very wrong with each algorithm. Find and describe it. |
| Monday, March 25 |
From Section 3.2, read Examples 2,3,4, and do #3, 5,6*, 11
And study countable/uncountable topic for the quiz Wednesday. |
| Wednesday, March 27 | From Section 3.2 #9,10* (without using Theorem 1) and either (6th ed.) #30*,31 or (7th ed) #36*,37 |
| Friday, March 29 | From Section 3.2 #1, 2*, 22*, 23 (6th edition) or #1, 2*, 28*, 29 (7th edition) |
|
"Redoable" problems: each problem that you got a 2 or less on is eligible.
(originally assigned Wed.Mar.6:) Section 2.5 #28 (7th ed) or 2.4 #42 (6th ed); Section 3.1 #6, 8; Section 3.2 TBA Due Monday, April 8 |
|
| Monday, April 1 |
From Section 3.2, # 26*, 27 (7th ed) or #20*, 21 (6th ed)
From Section 3.3, #9, 13, 29, 33 (7th ed) or #5, 7, 19, 23 (6th ed). Note: the algorithms needed for 9/5, 19/29, and 33/23 are in the back of the book. |
| Wednesday, April 3 | From Section 3.3, read "Understanding the Complexity of Algorithms" |
| Friday, April 5 |
From Section 4.1 (7th ed), read the proof of Corollary 1, and do #1, 2*, 3, 4*, 7, 9, 21ab, 26*, 29.
From Section 3.4 (6th ed), read the proof of Corollary 1, and do #1, 2*, 3, 4*, 7, 9, 17ab, 18*, 19. |
| Monday, April 8 |
Compute (992 mod 32)3 mod 15 and (34 mod 17)2 mod 11 using Theorem 5/Corollary 2.*
From Section 4.1 do #34*, 35 (7th ed.) or from Section 3.4 do #20*, 21 (6th ed.) |
| Exam 2 on Wednesday, April 10. | |
| Friday, April 12 |
Find these sums of binary numbers: 1000111+1110111, 1000000001+1111111111.*
Find the sums of these base-3 numbers: 112+210, 2112+12021, 20001+1111, 120021+2002.* From Section 4.2 (7th ed) do #1a, 2a*, 3, 6a*, 7ac, or from Section 3.6 (6th ed) do #1a, 2a*, 3, 4a*, 5ac. |
| Monday, April 15 |
From Section 4.3 (7th ed.) do #1, 3, 5, 25
or from Section 3.5 (6th ed.) do #1, 3, 5, 21 |
| Wednesday, April 17 |
(7th ed.) From Section 4.3 do #14*, 15, 27, 28, 30*, 32cd*, 35
(6th ed.) From Section 3.5 do #10*, 11, 23, 24, 26*, and from Section 3.6 do #24cd*, 25. |
| Friday, April 19 |
Read Section 5.1 (7th ed.) or 4.1 (6th ed.) up through the first few examples (at least).
Read Section 5.2 (7th ed.) or 4.2 (6th ed.) up through example 2 (at least). |
| Monday, April 22 | MENGER DAY: Instead of class, go to the Math Club meeting and/or the Menger lecture. |
| Wednesday, April 24 | From Section 5.1 (7th ed.) or 4.1 (6th ed.) do #5, 6*, 7, 11, 20*, 21, 24*, 28*, 32*, 37 |
| Friday, April 26 | From Section 5.2 (7th ed.) or 4.2 (6th ed.) do #10*, 13, 14*, 17, 30*. (For #30, obviously it's false, but where exactly is the flaw in the argument?) |
| Monday, April 29 | From Section 5.3 (7th ed.) or 4.3 (6th ed.), READ the proof of Theorem 2, READ from the beginning through Example 2, READ the definition of Fibonacci Numbers, and DO #1,7. |
| Wednesday, May 1 |
From Section 5.3 (7th ed.) or 4.3 (6th ed.) do #5ad, 25, 26*, 27
From Section 6.2 (7th ed.) do #3,5,9,31, or from Section 5.2 (6th ed.) do #3,5,9,29 X.* In 2010 the census counted 8,008,278 people in New York City. Assume that no one has more than a million hairs on their head and that no one is perfectly bald. Show that there had to be at least nine people in NYC in 2010 with the exact same number of hairs on their head. |
| Friday, May 3 | Optional: Read Examples 10,11,12 and Theorem 3 and its proof, from Section 5.2 (6th ed.) or 6.2 (7th ed.) |
| "Redoable" problems: You can redo any induction/strong induction problem, and it will be regraded and returned to you before the final. | |
