Instructor: Robert Ellis  Office: E1 Bldg, Rm 105C  Email: 
Lectures 
MWF 1:502:40pm  Alumni Memorial Hall 222 
Office Hours 
Walkin; TRF best times  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)
Exams  

Quiz 1  Quiz 2,3,...  Exam 1  Exam 2  Final  
Quiz 1 Key  April 17  March 4 ExA ExB Key 
April 22 Ex2 Key Practice for 2.34.2 
FinalA Key A/B  
Practice Exams  
Term  Quizzes  Exam 1  Exam 2  Final  
Spring `08 
Quiz 1,
Quiz 1 key, Quiz 2, Quiz 2 key 
1,
1 key
extra practice 
2,
2 key
extra practice 
Final,
Final key
extra practice (revised May 7, 2009) 
Sample homework cover sheet; or, something equivalent can be signed on the top of the first homework page
Due Date  Reading & Suggested problems ^{3, 1} v  TurnIn Assignment ^{2}  

W 5/13 
FINAL EXAM 10:30am12:30pm Alumni Memorial Hall 222 
FINAL EXAM  
T 5/12  Exam Review Session, E1
103, 6:458:30pm practice sheet for final (revised May 7, 2009) See also Exam 2 practice, Exam 1 practice, Exam 2 Key, Exam 1 Key  
F 5/8 
Read Section 8.1. Suggested exercises. Section 6.1: 117 odd, 21, 25, 29, 35 
Homework 15. For full credit, show your work. For counting problems,
writing quantities with no labels or no explanations will not receive full
credit. Section 5.2: 4, 12, 16 (numbers selected are distinct), 24 Section 5.3: 4, 12, 16, 20 Section 5.4: 4, 12, 22a Section 6.1: 6, 16, 26, 36 Note: whatever we cover on 5/8 from Section 8.1 could appear on the final. 

W 5/6 
Read Section 6.1 and 6.2 through Theorem 1. Work the selfassessment on counting  this material will be on the final. Suggested exercises. Section 5.4: 19 odd, 19, 23 Challenge: 27, 29 

M 5/4 
Read Section 5.4. Suggested exercises. Section 5.3: 127 odd (pick a few). Challenge: 29, 43 

F 5/1 1:50pm in class 
Read Section 5.3. Work through the selfassessment on recursive definitions. Suggested exercises. Section 5.1: 3, 11, 17, 21, 27, 33, 39, 51, 55; Section 5.2: 5, 9, 19b, 21 (show Example 12 is "sharp"!), 33, 37 (see Example 10); Challenge. Section 5.1: 44, 45, 58, 62; Section 5.2: 2628, 36 (Ramsey Theory); 38 (possible nonexistence in Ex. 37), 41 (approximating irrationals with rationals) See also The ErdősSzekeres Theorem for longest subsequences 
Homework 14.
Wherever appropriate, give explanations instead
of just writing the answer. Section 4.4: 2 and 6: Use a tree like Figure 1 on page 316 for the trace. 10 (write pseudocode), 24 (write pseudocode), 44 (construct a tree like Figure 2 on page 318) Section 5.1. Don't just write computations. For full credit label quantities and cite "product rule", "sum rule", etc.! 2, 8, 10, 12, 14, 20, 28, 32, 40, 42, 52, 54 

W 4/29 
Read Section 5.2. Suggested exercises. Section 5.1: 1, 9, 13, 19, 25 

M 4/27 
Read Section 5.1. Suggested Exercises. Section 4.4: 1, 5, 9, 15, 19, 23, 25, 2735 odd Challenge. Section 4.4: 26, 27 (fast exponentiation), 41 All CS majors and programmers need to do the following:  Go through the Wikipedia animated demo for Quicksort  Work Section 4.4 5055 and  Read Section 4.5. 

F 4/24 1:50pm in class 
Read through the end of Section 4.4. The modular exponentiation
algorithm is optional. 
Homework 13.
Wherever appropriate, give explanations instead
of just writing the answer. Section 4.3: 24bc, 26, 28ab, 44, 50 

W 4/22  Exam 2
Revised practice problems for 2.34.2 
Exam 2  
T 4/21  6pm8pm Exam 2 review session, location E1 103 Material: Revised practice problems for 2.34.2 

M 4/20 
Read Section 4.4. Section 4.3: 13, 17, 19 Extra Challenge. Section 4.3: 15, 16  
F 4/17 1:50pm in class 
Quiz 2 topics: the selfassessments on
mathematical induction and on recursive definitions. (Exam 2 will cover from Sections 2.34.3.) Read Section 4.4 through p.315. The modular exponentiation algorithm is optional. 
Homework 12.
Wherever appropriate, give explanations instead
of just writing the answer. Section 4.1: 34, 40, 48 (explain fully), 70, 74a Section 4.2: 6, 10, 32, 38 Section 4.3: 4ad, 8bd, 12 

W 4/15 
Suggested Problems. Section 4.2: 17, 29 Section 4.3: 19 odd (pick 2) Extra Challenge. Section 4.2: 1822 even (discrete geometry), 30 (strong induction flaw), 4143 (equivalence of wellordering, induction, and strong induction) 

M 4/13 
Reading: no new reading. You should have read through Section 4.3 so far. Suggested Problems: Section 4.2: 17 odd (pick one or 2) Additional Reading: A really neat Andean abacuslike machine for accounting that uses Fibonacci numbers and arithmetic in various bases. 

F 4/10 1:50pm in class 
Read the rest of Section 4.2, and Section 4.3 Suggested Problems. Section 4.1: 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 
Homework 11.
Wherever appropriate, give explanations instead
of just writing the answer. Section 3.5: 4ef, 12cd, 20a, 22a, 26, 28abc, 32 (similar to Lemma 1, p.228) Section 3.6: (show steps!) 2a, 4c, 8c, 24c, 26 Section 4.1: 4 (answer in complete sentences), 10, 18, 22 

W 4/8 
Read the rest of Section 4.1, and Section 4.2 through p.287. Sugested problems. Section 4.1: 317 odd (pick a couple) 

M 4/6 
If you are interested in cryptography, read Section 3.7 (not part of the course). Browse through Section 3.8, carefully reading anything that does not look familiar (also not part of this course). Read Section 4.1 through p.273. Suggested Problems. Sect. 3.6: 117 odd, 2327 odd; Challenge: Cantor Expansions 4648 Extra reading: Primality Testing and Integer Factorization 

F 4/3 1:50pm in class 
Read Section 3.6. Suggested Problems. Sect. 3.5: Routine: 15 odd, 1131 odd; Challenge: 7, 9, 3337 
Homework 10.
Wherever appropriate, give explanations instead
of just writing the answer. Section 3.3: 8, 10ab, 12ab, 26 Section 3.4: 4, 6, 8, 12, 20, 24, 32b 

W 4/1 
Read Section 3.5. Discover the next Mersenne Prime on your own computer! See the GIMPS page. There are over 4000 participants, and one was recently awarded $50,000. Suggested Problems. Sect. 3.4: 127 odd, 31 

M 3/30 
Read about NPComplete
problems, for which no known fast solution exists. The seemingly simple
question of satisfiability of the
truth of certain logical propositions is a hard problem.
Work the selfAssessment on growth of functions. Suggested Problems. Sect. 3.3: 113 odd, 23, 27 

F 3/27 
Read Section 3.4. Optional Reading: The Caesar Cypher, RSA (public key encryption) Challenge. Section 3.2: 55, 60, 6163 
Homework 9.
Wherever appropriate, give explanations instead
of just writing the answer. Section 3.1: 28 (write in format like the solution to Example 1), 36, (step=value of i), 40, 46, 54, 56 (find a counterexample to greedy=optimal) Section 3.2 (Unless specifically requested to do otherwise, you can use the limit method from class notes to determine the growth of a function): 4, 8ab, 14ad, 20ab, 22bd, 28a, 36 (prove or give c/ex) 

W 3/25 
Read Section 3.3. Work through the java interactive applets: Making Change and Sorting. Section 3.2: 143 odd 

M 3/23 
No assignment  
F 3/13 1:50pm 
Read Section 3.2, all pages. Suggested Problems. Section 3.1: 2735 odd, 41, 53 Related material: the greedy algorithm, the British coin system Challenge: Section 3.1: 37, 43, 49, 5859; reread "The Halting Problem" and work 6062; learn about the minimum spanning tree problem. 
Homework 8.
Wherever appropriate, give explanations instead
of just writing the answer. Section 2.3: 38 (compute but don't prove), 40a, 44, 52, 66 (for 66 write a proof based on the definition or the conditions in the remark below Example 21 on page 141) Section 2.4: 6ag, 10ac, 14ac, 16c, 24, 28, 32bc (For the uncountable sets, just state "uncountable"), 40 Section 3.1: 6, 12, 18, 24 (Assume A=a_{1},...,a_{m} and B=b_{1},...,b_{n}) write pseudocode for these 

W 3/11 
Read Section 3.2 through page 185. Interactive applets: Become familiar with changemaking and sorting through the interactive applets called "Making change" and "Sorting Algorithms". Suggested Problems. Section 3.1: 125 odd. 

M 3/9 
Read Section 3.1. Work the self assessment OnetoOne and Onto Properties of Functions Suggested Problems. Section 2.4: 1321 odd, 27, 3139 odd Extra Challenge: Section 2.4: 4048, and the finite calculus worksheet discussed in class on Friday 3/7 

F 3/6 
Read Section 2.4 to the end. Suggested Exercises. Section 2.4: 119 odd 
Homework 7.
Wherever appropriate, give explanations instead
of just writing the answer. Section 2.3: 6ace, 8adg, 12bc (give proof), 14ab (give proof), 16ab, 20, 26d, 28abc, 36a 

W 3/4 
Exam 1 Through Section 2.2; practice exams above 

M 3/2 
Read Section 2.4 through page 158 Work through the selfassessment on concept of function Suggested Exercises. Section 2.3: 171 odd (skip around); Challenge: 7678 

F 2/27 
Read Section 2.4 through page 154. 
Homework 6.
Wherever appropriate, give explanations instead
of just writing the answer. Set proofs can use (a) logical equivalence in
setbuilder notation, (b) forward and reverse containment, or (c) set membership table.
Section 2.1: 2a, 14, 22cd, 32, 36c Section 2.2: 2cd, 10a, 12, 16c, 26c, 30c (Hint: inspect the set membership table like the example in class), 32, 48d (write a proof like in class) 

W 2/25 
Work through selfassessment on sets Suggested Exercises. Section 2.1: 135 odd; Challenge: 3739 Section 2.2: 1, 3, 9, 13, 15, 19, 2531 odd; Challenge: 5960 (Multisets), 6163 (Fuzzy sets) 

M 2/23 
Read through Section 2.3.
Section 2.2: 39, 43, 45, 51, 57 (why would we use successors?) Challenge: 5963 
20 minute inclass Quiz
Material will be similar to the selfassessments entitled "Conditional Propositions," "Direct, Contraposition, and Contradiction Proofs," "Negation Of Quantified Statements," and "Quantified Statements". 

F 2/20 1:50pm in class 
Read Section 2.2. Take the selfassessment on "Proof Strategy" (click here and look for the title). Your goal should be at least 90% correctness. Sect. 2.2: 111 odd 
Homework 5 Write complete explanations for your answers whenever appropriate. ("Complete" does not necessarily mean "long".) Section 1.6: 12, 24, 32, 34, 38 Section 1.7: 4, 10, 14, 22, 28, 34 (Hint: look halfway) 

W 2/18 
Read Section 2.1. Take the selfassessment on "Direct, Contraposition, and Contradiction Proofs" (click here and look for the title). Your goal should be at least 90% correctness. Section 1.7: 119 odd, 27, 31. Challenge: 35, 37, 4448 Sect. 2.1: 135 odd. Challenge: 38, 39 

F 2/13 
Read through Section 1.7, page 102. Section 1.6: 917 odd, 19&21 (read bottom p.78 to top of p.79), 31 (see p.82), 35 
Homework 4. Section 1.5: 4abe, 8 (encode using implication), 14ac, 16b, 20a, 24, 28 Section 1.6: 4, 16 

W 2/11 
Read through Section 1.7, page 93. See also Wikipedia on modus ponens; and links in this page for modus tollens and other valid arguments. Section 1.5: 1, 3, 7, 917 odd, 2333 odd Section 1.6: 17 odd Challenge. Section 1.5: 34, 35 

M 2/9 
Read through page 85.  
F 2/6 1:50pm in class 
Read through page 81. 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 pages 34 of the notes "Section 1.4 Nested Quantifiers" in the documents area of Blackboard. Section 1.4:2547 odd. Skip around if easy, do more if having trouble. Challenge: Section 1.4: 49, 51 (Show how to bring a quantifier to the left of a predicate)  Homework 3. Wherever appropriate, give explanations
instead
of just writing the answer. Section 1.3: 4, 6acef, 10d, 16, 18be, 22c, 28cd, 34b, 44, 48b, 50, 52bc Section 1.4: 2c, 6d, 8d, 10ehi, 20ab, 24ab, 28ef, 30d, 34, 44 

W 2/4  Read through page 72. You've done the reading and selfassessments for 2/4, right? Spend a little more time on "Quantified Statements". Suggested Problems. Sect. 1.3: 2737 odd, 41, 43, 4553 odd Sect. 1.4: 123 odd. Skip around if easy, do more if having trouble. Challenge (Optional application problems) Sect. 1.3: 5561 odd  
M 2/2  Read through page 64. 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 1/30 1:50pm in class 
Read through page 58. Extra reading: see Wikipedia for further information on conjunctive normal form and its use in NPcompleteness, and on the satisfiability problem. These are central to understanding how hard computationally a logically formulated problem is. 
Homework 2. Section 1.2: 6, 8a, 10b, 12b (For 12b do a linebyline equivalence reduction and state the rule for each line) 24, 28, 30, 48, 54, 58 

W 1/28  Read through page 54. In the Logical Equivalence demo: click through to the "Chapter 1 Logical Equivalence" Java applet. Work Example 5, referring to class notes and 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 Tables 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/26 1:50pm in class 
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]) 
Homework 1. Section 1.1: 8ae, 10ac, 14, 16cd, 18beg, 24b, 28af, 36ad, 58 

F 1/23  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/