Instructor: Robert Ellis  Office: E1 Bldg, Rm 105C  Email: 
Lectures 
MWF 1010:50am  Life Sciences 152 
Office Hours 
W 11amnoon & 1:302:30pm  Office phone 5675336 
Appointments and emailed questions are welcome  
Textbook 
Rosen, Discrete Mathematics and its Applications, 6th edition, McGraw Hill 
First day handout (pdf) (course contract & exam schedule)
IIT Math 230 sections schedule
Quiz keys: Quiz 1A, 1B, 2A, 2B Exam keys: 1A, 1B, 2A, 2B
Final Exam Version A, Version B
5suit poker homework key
Due Date  Reading & Suggested problems ^{3, 1}  TurnIn Assignment ^{2} 

F 5/9 10am in class 
Homework 14. Extendeddeck poker worksheet and key. You must staple separate paper with justification for probabilities. Work must be easily readable or no credit. Note: You may add the type "5 of a Kind" if you wish. Whatever you choose, counting the number of hands of a given type must be justified and consistent.  
W 5/7 
Read: Section 5.4, Section 5.5 through Theorem 3, Section 6.1, and
Section 8.1 through p.522. We are skipping Section 5.5 past Theorem 3, Section 5.6, Sections 6.26.4, and Chapter 7 

F 5/2 10am in class 
Read through p.360, especially Example 12 on page 352 which we
started in class. Work through the selfassessment on recursive definitions. See also The ErdősSzekeres Theorem for longest subsequences Section 5.1: 3, 11, 17, 21, 27, 33, 39, 51, 55; Challenge: 44, 45, 58, 62 Section 5.2: 5, 9, 19b, 21 (show Example 12 is "sharp"!), 33, 37 (see Example 10); Challenge: 2628, 36 (Ramsey Theory); 38 (possible nonexistence in Ex. 37), 41 (approximating irrationals with rationals)  Homework 13.
Wherever appropriate, give explanations instead
of just writing the answer. Section 4.4: 32, 33, 44 Section 5.1: 4, 14, 24a, 38 
W 4/30 
Read all of Section 5.1, and Section 5.2 through p349. Suggested exercises. Section 4.4: 2835, 45, 47. Critical for CS majors and minors: 5055 and Wikipedia animated demo for Quicksort Section 5.1: 1, 9, 13, 19, 25 
Homework 13.
Wherever appropriate, give explanations instead
of just writing the answer. Section 4.4: 32, 33, 44 Section 5.1: 4, 14, 24a, 38 
M 4/28 10am in class 
Read through the end of Section 4.4. The modular exponentiation
algorithm is optional. Suggested Exercises: Section 4.4: 1, 5, 9, 15, 19, 23, 25, 33, 37 Challenge: 26, 27 (fast exponentiation), 41 
Homework 12.
Wherever appropriate, give explanations instead
of just writing the answer. Section 4.2: 4, 8, 12, 32 Section 4.3: 4bc, 8ac, 12, 24ac, 32a, 48, 50 Section 4.4: 2, 6, 24, 32 
F 4/25 10am in class 
EXAM 2 is Friday 4/25  EXAM 2 is Friday 4/25 
M 4/21 
Do the selfassessment on mathematical induction Read through the end of 4.3. Section 4.2: 17 odd (pick 1 or 2), 17, 29 Challenge. Section 4.2: 18, 20, 22 (discrete geometry), 30 (strong induction flaw), 4143 (equivalence of wellordering, induction, and strong induction) Section 4.3:19 odd (pick 2), 13, 17, 19 Challenge. Section 4.3: 15, 16. 

F 4/18 10am in class 
Lecture Notes: Notes for 4.1 and 4.2 are posted in the "Course
Documents" section of
Blackboard. Have you done any suggested problems for M 4/14 yet? This are critical for your understanding of induction. Be sure to do 47 & 49. Bring your questions to office hours and for 20 minutes after class. 
Homework 11.
Wherever appropriate, give explanations instead
of just writing the answer. Section 4.1: 4 (answer steps carefully), 12, 20, 32, 38, 48 (give a careful explanation), 66 (give a careful explanation, perhaps drawing a diagram; requires you to understand 65) 
M 4/14 
Read 4.1 and 4.2 through the top of page 288. Section 4.1: 317 odd (pick a couple); 1923 odd (pick at least one); 31, 33 (pick one); 3943 odd (pick one); Important to try: 47 and 49; pie fight & tiling: 71, 73 Challenge. 51, 57, 59, 6557, 75 

F 4/11 10am in class 
Homework 10.
Wherever appropriate, give explanations instead
of just writing the answer. Section 3.4: 22 Section 3.5: 4de, 8 (similar to the Q=p1*p2*...*pn + 1 proof of infinitely many primes), 10 (See p.216 for definition), 20b, 22b, 28bc Section 3.6 (show steps!): 2b, 4b, 6, 8b, 24b, 26 (posted 4/7) 

W 4/9 
We will skip the following material: In Section 3.6, read about base
expansion and know Theorem 1, and know the Euclidean Algorithm material, but skip
the rest. Also skip Sections 3.7 and 3.8. Treat 3.7 and 3.8 as
optional reading; you will see it eventually. Read Section 4.1 through page 273. Suggested Problems. Sect. 3.6: 117 odd, 2327 odd Challenge: Cantor Expansions 4648 

M 4/7 10am in class 
Read through p.229, the Euclidean Algorithm. Suggested Problems. Sect. 3.5: Routine: 1, 3, 5, 11, 13, 17, 21, 23, 25; Requires some thought: 15, 19, 29, 31 Challenge: 6, 7, 9, 33, 3537 
Homework 9.
Wherever appropriate, give explanations instead
of just writing the answer. Section 3.2: 4 (use original definition), 6 (use limit method in notes), 18 (use either original or limit method), 22abc, 36 (prove or give c/ex) Section 3.3: 4, 8, 12ab (best case means smallest number of operations given input of size n) Section 3.4: 4, 8, 10acf, 18 (posted 3/31) 
F 4/4 
Optional Reading: Hashing functions, p.205 Read though p.212 in 3.5. P.213 "Distribution of primes" through p.215 "The Twin Prime Conjecture" are optional Discover the next Mersenne Prime on your own computer! See the GIMPS page. SelfAssessment on growth of functions Suggested Problems. Sect. 3.4: 3, 5, 7, 11 (This is Thm.3, and one direction was proved in class), 13 (case analysis on n mod k), 23 Challenge. Sect. 3.4: 2730 (hashing and pseudorandom numbers), 3335 (ISBN book codes) 

W 4/2 
Read Section 3.4: The Integers and Division Optional Reading: The Caesar Cypher, RSA (public key encryption) 

M 3/31 10am in class 
Homework 8.
Wherever appropriate, give explanations instead
of just writing the answer. Section 3.1: 12 (use pseudocode), 24 (pseudocode or concise sentences), 26, 34 (step=value of i), 38, 46, 52ab, 54ab, 56 (find a counterexample to greedy=optimal) (posted 3/24) 

F 3/28 
Read Section 3.3, or pp58 of xeroxed handout on 3.3.  
W 3/26 10am in class 
Reading: Through p.190. Halting problem optional. Interactive applets: Master changemaking and sorting through the interactive applets called "Making change" and "Sorting Algorithms". Section 3.1: 135 odd (pick several), 39, 41, 53. Challenge: 37, 43, 49, 5859; Read "The Halting Problem" and work 6062. Related material: the greedy algorithm, the British coin system, and (challenging) the minimum spanning tree. 
Homework 7.
Wherever appropriate, give explanations instead
of just writing the answer. Section 2.4: 4bd, 8, 14bd, 16b, 18ad, 24, 28, 32 (For the uncountable sets, just state "uncountable") (posted 3/10) Section 3.1: 4, 10 (write pseudocode for both) (posted 3/10) 
W 3/12 
Exam 1, Sections 1.12.3 Practice test here 
Exam 1, Sections 1.12.3 
F 3/7 
Read through p173. Start studying for Exam 1: *Chapter 1 and Chapter 2 selfassessments, *Homeworks 16, *Lecture material and examples. The exam will require writing proofs, and will have short answer or multiple choice like Quiz 1. Section 2.4: 19 odd, 1321 odd, 27; Challenge: 11, 25 
Homework 6.
Wherever appropriate, give explanations instead
of just writing the answer. Section 2.3: 6abd, 8cgh, 14ae (give proof), 16c, 20, 24 (for invertible, need 11 and onto), 26c (posted 2/29) Section 2.3: 34, 36b, 37 (yes, an odd one), 38b, 48a, 52, 62, 68 (posted 2/29) 
M 3/3 
Section 2.3: 1127 odd


F 2/29 10am in class 
Work the selfassessment "Concept
of a function" (floor and ceiling functions defined on pp.142143) Section 2.3: 19 odd 
Homework 5.
Wherever appropriate, give explanations instead
of just writing the answer. Section 2.1: 30, 34d, 36 (posted 2/22) Section 2.2: 4, 10b (hint: vacuous proof in one direction), 16e by formal proof, 18e by membership table, 30 (yes or no plus informal explanation) (posted 2/22) Section 2.2: 34, 48d (write proofs of equality), 55bc (yes, an odd problem) (posted 2/25) 
W 2/27 
Section 2.2: 39, 43, 45, 51, 57 (why would we use successors?)
Challenge. Section 2.2: 5963 

M 2/25 
Quiz on Monday 2/25. Read through p138. Work the self assessment on sets Section 2.1: 2335 odd. Section 2.2: 1, 3, 9, 13, 15, 19, 2531 odd 

F 2/22 10am in class 
Quiz Monday 2/25. 10am sharp Greenwich mean time  20 minutes,
10 questions on Ch 1, based heavily on Chapter
1 selfassessment applets. Sect. 2.1: 2335 odd Sect. 2.2: 111 odd Read! the correct solution to S1.4 #44 on there being at most 2 real roots for a quadratic polynomial. Grading Error. Everyone will be refunded 3 points on Homework 2 for problem 18f, which was graded incorrectly. The correct answer is the disjunction of negated P(x_i)'s. Tricky gcd(p,q) definition. In the proof that the square root of 2 is irrational, one step requires assuming p and q have no common factor other than 1; i.e., gcd(p,q)=1. I incorrectly inferred that "2 does not divide p and 2 does not divide q". The correct inference is that "either 2 does not divide p or 2 does not divide q". After all, gcd(4,31)=1, but 2 divides 4 doesn't it? See pp8081 to review the proof.  Homework 4.
Wherever appropriate, give
explanations instead
of just writing the answer. Section 1.6: 10, 16, 22, 30, 34, 38 (Hint: 0^2=0) (posted 2/14) Section 1.7: 4, 8, 12, 18, (posted 2/14) Section 1.7: 28, 32 (posted 2/18) Section 2.1: 2b, 8 (give a reason for the false ones only), 14, 18, 22 (posted 2/18) 
W 2/20 
Read through Section 2.2. Section 2.1: 121 odd. 

F 2/15 10am in class 
Read p.82 and all of Section 1.7 (pp86102). This is a critical section 
you should
spend at least 1 hour on it before class Friday. Section 1.6: 917 odd, 19&21 (read bottom p.78 to top of p.79), 31 (see p.82), 35 HW 1 Results: If you got below 90 on HW1, I STRONGLY suggest revisiting the selfassessment applets "Conditional Propositions, Negation Of Proposition, Quantified Statements, Negation Of Quantified Statements". We will be building on the current level of difficulty rather than reducing.  Homework 3. Wherever appropriate, give
explanations instead
of just writing the answer. Section 1.4: 2b, 4d, 6ce, 8c, 10fg, 12n, 20cd, 24cd, 28gj, 30e, 34, 44 (posted 2/8/08) Section 1.5: 2, 4de, 6, 12 (posted 2/8/08) Section 1.5 cont'd: 14bd, 16c, 18, 24, 28 (posted 2/11) Section 1.6: Two problems 2 (Use the intermediate form of proof  that is, state when universal or existential instantiation or generalization is applied) 6 (Use the short form of proof, like the last proof in lecture on Monday) (posted 2/11) 
W 2/13 
Read through page 87. Understand universal modus ponens, p.71 Section 1.5: 19, 2333 odd Section 1.6: 17 odd Challenge. Section 1.5: 35. 

M 2/11 
Section 1.5: 1, 3, 7, 917 odd. Wikipedia on modus ponens. See links in this page for modus tollens and other valid arguments. 

F 2/8 10am in class 
Reminder: There is a possible final grade
penalty for 6 or more absences. Refer to the Section 1.4 (Nested Quantifiers) notes posted in the documents section of Blackboard: Formulate quanitifed statements for (i) the limit of a sequence a_1,a_2,... being L (Section 11.1 p739 of Stewart Calculus 5e edition), and (ii) the division algorithm theorem on page 202. In both cases the solutions are contained in the notes on pp34. Section 1.4:147 odd. Skip around to every 4th to 6th problem, but do several around a problem you don't fully understand. Challenge: Section 1.4: 49, 51 (Show how to bring a quantifier to the left of a predicate)  Homework 2. Wherever appropriate, give explanations
instead
of just writing the answer. Section 1.3: 4, 6cdef, 10c, 16, 18df, 22b, 28ce, 32bce, 44, 48 (posted 2/1) Section 1.3 continued: 50, 52, 54 (posted 2/4) 
W 2/6  You've done the reading and selfassessments for 2/4, right? You
should spend a little more time on "Quantified Statements". Suggested Problems. Sect. 1.3: 2737 odd, 41, 43, 4553 odd Challenge (Optional application problems): 5561 odd  
M 2/4  Read through page 58. In the Self Assessment page, work through "Conditional Propositions", "Negation of Proposition" and "Quantified Statements". Suggested Problems. Sect. 1.3: Odds 125 Any of the above material could be tested.  
F 2/1 10am in class 
Make sure to have read through page 54. Blackboard typo on Wednesday: On step 3 for finding a formula for f(p,q), I wrote "disjunction" but used the wrong symbol ^ in the pattern (...)^(...)^...^(...). The correct pattern is (...)v(...)v...v(...). See Wikipedia for further information on conjunctive normal form and its use in NPcompleteness. 
Homework 1. Section 1.1: 8acef, 12, 16ad, 18acde, 24a, 28be, 30e, 36bd, 56 (posted 1/25) Section 1.2: 6, 8d, 10b, 12c (argue either (i) for all cases the hypothesis is true, the conclusion is also true, or (ii) by repeated reduction using logical equivalence), 22, 28, 32, 48, 50ab, 60a 
W 1/30  Read through page 54. In the Logical Equivalence demo: click through to the "Chapter 1 Logical Equivalence" Java applet. Finish working 1.2 Example 5, using the "animate" mode if necessary. Also use the applet to set up and work through at least one of the suggested problems on logical reduction. #23 is a good challenge using both Table 6&7. Suggested Problems. Sect. 1.2: Odds 115, 17, 19, 21 (reduce from 19), 23, 25, 27 ("equal contract"), 29 (transitivity of implication), 35, 43, 47, 49, 57, 59 Challenge. Sect. 1.2: 39, 44, 45, 51, 55, 61  
M 1/28  Sections 1.11.3, through page 32, paying special attention to Tables
68 on pp2425. Logical Equivalence demo: click through to the "Chapter 1 Logical Equivalence" Java applet. Click the "Animated" button, select 1.2 Example 5 in the dropdown box, and click the "next" button to follow through the logical equivalences. More on this applet for Wednesday's assignment. Suggested Problems. Sect. 1.1: 1, 3, 7, 11, 13, 17, 19, 21, 23, 29, 33, 37, 47, 55, 59, 63 (If you find a problem too easy, skip to the next one. These are the types of problems you are expected to be able to work.) Challenge. Sect. 1.1 43, 65 (note [1])  
F 1/25  Section 1.1, especially conditionals on pp69. You must understand page
6. Truth Tables interactive demo: click through to the "Chapter 1 Truth Tables" Java applet and practice filling out truth tables. "Makes satisfiable" means "makes true". 
[1] Challenge problems are more difficult than those typically assigned on quizzes or exams. You should try these if you 1) want to get the most out of this course possible, 2) are an Applied Math major, or 3) intend to go to graduate school.
[2] Friday homework posting. Homework due on Fridays is gradually posted as we cover the material and is finalized by noon on the Monday before the homework is due. Homework is due 10am in class, 9:50am in my mailbox (E1 Rm210); no late homework is accepted.
[3] Watch all table rows! The required reading and suggested problems for the next class day may be in the 2nd or 3rd row from the top!
page maintained by Robert Ellis / http://math.iit.edu/~rellis/