Instructor: Michael Pelsmajer
Email Address: pelsmajer AT iit DOT edu
[Department web page (and contact information)] [Personal web page]

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

Homework

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

Eventually, there may be some homework assigned using WeBWorK. More on that later.

The book has a free web site with helpful tips, practice quizzes (self-assessments), interactive demos, and more. For example: Common Mistakes in Discrete Math (organized by chapter).

Daily Schedule and Assignments

Monday, January 11: Day 1, 1:50pm in Perlstein Hall, room 109.

Read "Spring 2010 Course information", "To the Student", "General Guidelines for Writing up Math Homeworks", and the beginning of "Common Mistakes in Discrete Math".

Due Wednesday, January 13:

Read, understand, and memorize alternate ways to say, "if p, then q".

Section 1.1: #13,14,17-20

You may need/wish to read other parts of Section 1.1. Also, many students find it terribly helpful to read ahead a bit to be prepared for the next class. On Wednesday we will discuss material from Sections 1.1 and 1.2.

Due Friday, January 15:

Read Examples 3 & 5 from Section 1.2, and more of Sections 1.1 and 1.2 as needed.

Section 1.1: #12, 27d, 31d

Section 1.2: #5, 6, 7a, 8a, 32

(There will be a quiz on Friday, on material from Sections 1.1 and 1.2.)

(Friday's class will discuss Section 1.3)

Monday, Jan 18: MLK Day, no class meeting

Due Wednesday, Jan 20:

From 1.3, read from "Other Quantifiers" through Example 18, p37-39. Read Example 21, p41. Read Examples 23,24, p42-43.

Prove or disprove each of the following (universe of discourse: natural numbers)

1. If n is a multiple of 3 then n is a multiple of 15.
2. If n is a multiple of 15 then n is a multiple of 3.

Section 1.3: #12,13,14,20abcd,23,25

Due Friday, Jan 22:

Study Table 1 in Section 1.4, and read more of 1.4 as needed.

Section 1.4: #1,2,9,19,20,22,28,32. (Remember, odd-numbered problems like #1,9,21,27,31 have answers in the back of the books!)

(All homework will be collected at the start of class.)

(There will be a quiz on Friday, on material from Sections 1.3 and 1.4).

Due Monday, Jan 25:

From Section 1.5, read/think about Definition 1, Table 1, and p70.

Section 1.5: #20 ("Valid" or "Invalid" and explain, briefly, why)

Read Section 1.6 (it's long!). Come to class with questions.

Section 1.6: #6,9,10,11,17 (17a should be "contrapositive")

Due Wednesday, Jan 27:

Optional: (re)read "Vacuous and Trivial Proofs", Example 5, and Example 6, from Section 1.6.

Section 1.6: #13,14,15,16, 19,20,21

From Section 1.7, read p86 through Example 4. Also read "Common Errors..." (p90), Example 8, and Example 9.

Section 1.7: #1,3,4

Due Friday, Jan 29:

Optional: (re)read Examples 9, 12, and 13, from Section 1.6.

Section 1.6: #23,24 - Do not use direct proof.

Section 1.6: #26,27, 32

From Section 1.7, read Examples 6 and 16.

Section 1.7: #27,28, 32.

From Section 1.7, read p91-102.

(All homework will be collected at the start of class.)

(There will be a quiz on Friday.)

Due Monday, Feb 1:

Section 1.7: #9,11,12, 14,17, 20. (For the trickier odd ones, it's okay if you need to "cheat" with the answer key, if you can't figure it out—but try them on your own first.)

Read Section 2.1

Optional: Look through the Chapter 1 section of Common Mistakes in Discrete Math

Special: Redo incorrect or missing solutions to earlier problems for partial credit. This applies all the homeworks collected on January 22. For every incorrect/missing problem, write your original score for that problem (e.g., "3/4") and give a complete solution to each part (e.g., "e" and "g") that was incorrect. Hand in both the corrected problems, paper-clipped to the original graded homework.

Due Wednesday, Feb 3:

Read Section 2.2

Look at Table 1, p124, and compare to Table 5, p24.

Section 2.1: #1,4,9,19ab,23b,29

Section 2.2: #2,3,4,25.

Due Friday, Feb 5:

Section 2.2: #14, 17b, 27, 45

Section 2.3: #1,2,7ab

Read p133-p142 from Section 2.3. (Note: during class, I conflated "codomain" with "range"; sorry.)

(Every Friday, unless otherwise notified: all homework will be collected at the start of class, after which there will be a quiz.)

Due Monday, Feb 8: updated Feb5,5pm

Section 2.3: #10,11,12,13, 18,19

Read p519-525 (stop before "Combining Relations"), from Section 8.1.

Due Wednesday, Feb 10:

Section 8.1: #1abc, 4,5,7

Read p555-558, skipping Example 5.

From "Equivalence Classes and Partitions" (Section 5), read the from the beginning on p559 through Example 12 (but the proof of Theorem 1 can be skipped), then read Theorem 2 through Example 14.

Section 8.5: #2ae,15

Due Friday, Feb 12:

Section 8.5: #39, 41,45

Read p158-160 ("Cardinality", Section 2.4).

(Every Friday, unless otherwise notified: all homework will be collected at the start of class, after which there will be a quiz.)

Due Monday, Feb 15: sort of (since we haven't finished discussing "Cardinality")

Section 2.4: #31,33bcd,35,36,37,40 (optional/interesting/perhaps: #43,45,46,47 - talk to me if you work on these)

Read "Some Important Functions", p142-145, but skip Example 27

Section 2.3: #9,57

Read "Sequences", p150-151 and (less important) "Special Integer Sequences", p151-153

Section 2.4: #3

Review Example 21, p160.

Special: Hand in on Monday, Feb 15

Redo incorrect or missing solutions to earlier problems for partial credit. This applies the three homeworks collected on January 29. For every incorrect/missing problem, write your original score for that problem (e.g., "3/4") and give a complete solution to each part (e.g., "e" and "g") that was incorrect. Hand in both the corrected problems, paper-clipped to the original graded homework.

Due Wednesday, Feb 17:

Section 2.3: #49, 69abd

Read p153-156 of "Summations".

Section 2.4: #5ade, 13,14,15,16,17

Due Friday, Feb 19:

Study!

Exam 1 will be Friday, Feb 19.

Topics will include most of Chapter 1, Chapter 2, and Sections 8.1 and 8.5. From Section 2.3, everything except "Some Important Functions". From Section 2.4, only "Cardinality". If something was skipped in the reading, lectures, and homework, then it will not be on the exam.

Study possibilities: Review quizzes, homeworks, lecture notes, and readings. There are sections at the end of Chapters 1,2, & 8, with reviews of important concepts and supplemental problems. Look through the Chapter 1, 2, & 8 sections of Common Mistakes in Discrete Math . The same web site also has "self-assessments" (sort of like practice quizzes) and more. Finally, be sure to sleep and eat properly.

Due Monday, Feb 22: assigned via email on Feb19

Just read Section 3.1. This is important - it contains introductory things that I won't go over, and hard things that you need to start thinking about now.

Due Wednesday, Feb 24:

Reread Section 3.1: as needed, and to prepare for next class.

Section 3.1: #1, 2, 3, 5, 6, 13, 14, 35.

• For #2, there's something very wrong with each algorithm: I just want you to find and describe it.
• For #3-6, write an algorithm using pseudocode; there is more than one correct possible way to do this.
• For #13 & 14, one step = one line of pseudocode.
• For #13, use the binary search algorithm on page 172.

Due Friday, Feb 26:

Section 3.1: #39, 42, 55

On p15, read Definition 7 and Example 20.

Reread "The Halting Problem", p176-177.

Read p180-184, to prepare for next class.

Due Monday, Mar 1:

Read Section 3.2. (Important topic!)

Do Section 3.2 #1,3,5. (For #5, the book's solution doesn't mention that their first step is to do synthetic division. There are other ways to do it, with different C and k.)

Due Wednesday, Mar 3:

Do Section 3.2 #2abdf, 4, 11, 22abc, 23abd

Hint for dealing with floors/ceilings: Table 1, p144, especially (2).

Due Friday, Mar 5:

Do Section 3.2 #7ab,8ab, 19,20,21

Read Section 3.3.

Spring Break!

Due Monday, Mar 15:

Do Section 3.3 #5, 9, 10, 11, 27

Review Section 3.3 as needed, and read Section 3.4

On Monday March 15, I give an example where worst-case and average-case complexity are differerent, and I'll discuss a framework for understanding complexity. Then we'll start Number Theory (Section 3.4-3.7).

Due Wednesday, Mar 17:

Do Section 3.3 #13

Do Section 3.4 #1, 7, 9, 17

Due Friday, Mar 19:

Section 3.4 #18,19, 21,22

(#21,22 are similar to proof of Theorem 5; they use Theorem 4)

Read Section 3.5

Section 3.5 #3,5,7

Due Monday, Mar 22:

Section 3.5 #1f, 21,23

(Study proof of Theorem 3, p212)

Read The Euclidean Algorithm p227-229

Read p231-235

Due Wednesday, Mar 24:

Section 3.5 #11,13

Section 3.6 #23

Section 3.7 #1

Read p219-222. Look at the rest of Section 3.6, too.

Due Friday, Mar 26:

Section 3.7 #3,4,5,6,7

Hint: #3 and #4 are much easier than #5-7: you only need to verify that the definition of "inverse" is true for those numbers.

Due Monday, Mar 29:

If needed, read Section 3.6 Examples 3 and 5

Section 3.6 #1ab,3ab

Read p263-271, p273-274 (not Example 10), and p278-279 (skip Example 13).

Section 4.1 #3,10a,11a

Due Wednesday, Mar 31:

Section 4.1 #5,6,7, 10b,11b, 19, 21,22,23, 31,33, 47,48

Read p283-287.

You will have a chance to ask questions about the homework during Wednesday's class

Due Friday, Apr 2:

Section 4.1 #28, 32

Section 4.2 #3

Due Monday, Apr 5:

Section 4.2 #5ac, 8, (optional #10), 13, 25 (but no justification needed for #25)

Read Section 4.3, p294-303 except skip Lame's Theorem.

Section 4.3 #1ab,3, 7, 25

Due Wednesday, Apr 7:

Section 4.3 #5[but no proofs], 9, 12, 13, 26ac, 27ac

Start studying for the exam on Friday!

During class on Friday, we will discuss Sections 4.3 and 4.4.

Due Friday, Apr 9:

Study for the exam! Be sure to sleep and eat properly.

Section 4.4 #5,9,45

Homework will not be collected until Monday, Apr 12.

Exam 1 will be Friday, Apr 9.

Topics will include Chapter 3 (only what we covered in class and in reading assignments), Section 4.1 and Section 4.2. From Section 2.3, only "Some important functions" (floor, ceiling, factorial). From Section 2.4, Sequences and Summation notation only (no formulas, no cardinality). (You will not need to procude pseudocode, but you will have to be able to understand it.)

Study possibilities: Review quizzes, homeworks, lecture notes, and readings. Perhaps the Chapter 3 review p257-260 (although it includes material we skipped).

Due Wednesday, Apr 14:

Section 5.1 #1,2,3,4,5, 7,8,9,10,11,12,13, 15,17, 25,26,27,28,29

Read Section 5.1 as needed

Due Friday, Apr 16:

Section 5.1 #23, 30,31, 32,33,34,35

Section 5.2 #1,3,5,29,30

Due Monday, Apr 19:

Section 5.2 #9,17 (see Example 7 for inspiration if needed)

From Section 5.3, read Corollary 2 and its two proofs. You might want to read through the examples in Section 5.3.

Section 5.3 #3, 5abc, 6abcd, 9, 11ab, 13, 15, 19, 25abcde, 27

Optional/Interesting: Section 5.3 #17, 23, 26abc, 30, 31, 34, 37 (#23 Hint: First, just order the men. Then spread them out and insert women into the gaps.)

Due Wednesday, Apr 21:

Section 5.4 #3,4, 6,7,9, 15 (Optional/Interesting: #21,27,29)

Read p393-395

Do the following, if you haven't yet already:

The book's web site has a COUNTING self-assessment (sort of like a practice quiz) that is rather good for reviewing Sections 5.1 and 5.3.

Also, at some point you should read the Chapter 5 portion of Common Mistakes in Discrete Mathematics.

Due Friday, Apr 23:

Section 6.1 #1,3,5,7,9,11,13,15,17, 21,23, 31,33

Due Monday, Apr 26:

From Section 7.1, read Introduction and Examples 3, 7, and 8. (8 is tough.)

From Section 7.3, read Introduction, Theorem 2, then Examples 7 and 9.

Section 7.1 #10,11a,13a,19ab

Section 7.3 #11,13,14,17b,21

Due Wednesday, Apr 28:

Section 5.5 #31,33,35, 41

Due Friday, Apr 23:

Section 5.5 #9ab,11,13

Study for Final Exam

 

Upcoming Topics & Problems:

The final exam has been scheduled by the registrar. It will be May 6, 8am-10am, in the usual classroom.