MATH 230-01 Introduction to Discrete Mathematics (Ellis) Spring 2009

Skip down to homework assignments
Instructor: Robert Ellis Office: E1 Bldg, Rm 105C Email:

Lectures

 MWF 1:50-2:40pm Alumni Memorial Hall 222

Office Hours

 Walk-in; TRF best times Office phone 567-5336
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.3-4.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

Homework Due Dates (READ the superscript notes 1,2,3...)

Due Date Reading & Suggested problems 3, 1 vTurn-In Assignment 2
W 5/13
 FINAL EXAM
10:30am-12:30pm
Alumni Memorial Hall 222 		FINAL EXAM
T 5/12
 Exam Review Session, E1 103, 6:45-8: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: 1-17 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 self-assessment on counting -- this material will be on the final.
Suggested exercises. Section 5.4: 1-9 odd, 19, 23
Challenge: 27, 29 		 
M 5/4
 Read Section 5.4.
Suggested exercises. Section 5.3: 1-27 odd (pick a few).
Challenge: 29, 43 		 
F 5/1
1:50pm in class 		Read Section 5.3.
Work through the self-assessment 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: 26-28, 36 (Ramsey Theory); 38 (possible non-existence in Ex. 37), 41 (approximating irrationals with rationals)
See also The Erdős-Szekeres 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, 27-35 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 50-55 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.3-4.2 		Exam 2
T 4/21 6pm-8pm Exam 2 review session, location E1 103
Material: Revised practice problems for 2.3-4.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 self-assessments on mathematical induction and on recursive definitions.
(Exam 2 will cover from Sections 2.3-4.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: 1-9 odd (pick 2)
Extra Challenge. Section 4.2: 18-22 even (discrete geometry), 30 (strong induction flaw), 41-43 (equivalence of well-ordering, 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: 1-7 odd (pick one or 2)
Additional Reading: A really neat Andean abacus-like 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: 19-23 odd (pick at least one); 31, 33 (pick one); 39-43 odd (pick one); Important to try: 47 and 49; pie fight & tiling: 71, 73
Challenge. 51, 57, 59, 65-57, 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: 3-17 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: 1-17 odd, 23-27 odd; Challenge: Cantor Expansions 46-48
Extra reading: Primality Testing and Integer Factorization 		 
F 4/3
1:50pm in class 		Read Section 3.6. Suggested Problems. Sect. 3.5: Routine: 1-5 odd, 11-31 odd; Challenge: 7, 9, 33-37 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: 1-27 odd, 31 		 
M 3/30
 Read about NP-Complete 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 self-Assessment on growth of functions.
Suggested Problems. Sect. 3.3: 1-13 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, 61-63 		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: 1-43 odd 		 
M 3/23
 No assignment  
F 3/13
1:50pm 		Read Section 3.2, all pages.
Suggested Problems. Section 3.1: 27-35 odd, 41, 53
Related material: the greedy algorithm, the British coin system
Challenge: Section 3.1: 37, 43, 49, 58-59; reread "The Halting Problem" and work 60-62; 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=a1,...,am and B=b1,...,bn) write pseudocode for these
W 3/11
 Read Section 3.2 through page 185.
Interactive applets: Become familiar with change-making and sorting through the interactive applets called "Making change" and "Sorting Algorithms".
Suggested Problems. Section 3.1: 1-25 odd. 		 
M 3/9
 Read Section 3.1.
Work the self assessment One-to-One and Onto Properties of Functions
Suggested Problems. Section 2.4: 13-21 odd, 27, 31-39 odd
Extra Challenge: Section 2.4: 40-48, 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: 1-19 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 self-assessment on concept of function
Suggested Exercises. Section 2.3: 1-71 odd (skip around); Challenge: 76-78
  
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 set-builder 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 self-assessment on sets
Suggested Exercises. Section 2.1: 1-35 odd; Challenge: 37-39
Section 2.2: 1, 3, 9, 13, 15, 19, 25-31 odd; Challenge: 59-60 (Multisets), 61-63 (Fuzzy sets)
  
M 2/23
 Read through Section 2.3.
Section 2.2: 39, 43, 45, 51, 57 (why would we use successors?) Challenge: 59-63 		20 minute in-class Quiz
Material will be similar to the self-assessments 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 self-assessment on "Proof Strategy" (click here and look for the title). Your goal should be at least 90% correctness.
Sect. 2.2: 1-11 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 self-assessment on "Direct, Contraposition, and Contradiction Proofs" (click here and look for the title). Your goal should be at least 90% correctness.
Section 1.7: 1-19 odd, 27, 31. Challenge: 35, 37, 44-48
Sect. 2.1: 1-35 odd. Challenge: 38, 39 		 
F 2/13
 Read through Section 1.7, page 102.
Section 1.6: 9-17 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, 9-17 odd, 23-33 odd
Section 1.6: 1-7 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 3-4 of the notes "Section 1.4 Nested Quantifiers" in the documents area of Blackboard.
Section 1.4:25-47 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 self-assessments for 2/4, right? Spend a little more time on "Quantified Statements".
Suggested Problems. Sect. 1.3: 27-37 odd, 41, 43, 45-53 odd
Sect. 1.4: 1-23 odd. Skip around if easy, do more if having trouble.
Challenge (Optional application problems) Sect. 1.3: 55-61 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 1-25
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 NP-completeness, 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 line-by-line 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 1-15, 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.1-1.3, through page 32, paying special attention to Tables 6-8 on pp24-25.
Logical Equivalence demo: click through to the "Chapter 1 Logical Equivalence" Java applet. Click the "Animated" button, select 1.2 Example 5 in the drop-down 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 pp6-9. 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/