MATH 230-001 Introduction to Discrete Mathematics (Ellis)

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

Lectures

 MWF 10-10:50am Life Sciences 152

Office Hours

 W 11am-noon & 1:30-2:30pm 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)

IIT Math 230 sections schedule

Quiz keys: Quiz 1A, 1B, 2A, 2B  Exam keys: 1A, 1B, 2A, 2B
Final Exam Version A, Version B

5-suit poker homework key

 

Practice final is here
Quiz 2 date: Monday 4/13/08.
Exam 2 date: Wednesday 4/23/08. Practice Exam 2 here.
Exam 1 date: Wednesday, 3/12/08. Sections 1.1--2.3. Practice test here

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

Due Date Reading & Suggested problems 3, 1 Turn-In Assignment 2
F 5/9
10am in class 		Homework 14. Extended-deck 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.2-6.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 self-assessment on recursive definitions.
See also The Erdős-Szekeres 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: 26-28, 36 (Ramsey Theory); 38 (possible non-existence 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: 28-35, 45, 47.
Critical for CS majors and minors: 50-55 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 self-assessment on mathematical induction
Read through the end of 4.3.
Section 4.2: 1-7 odd (pick 1 or 2), 17, 29
Challenge. Section 4.2: 18, 20, 22 (discrete geometry), 30 (strong induction flaw), 41-43 (equivalence of well-ordering, induction, and strong induction)
Section 4.3:1-9 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: 3-17 odd (pick a couple); 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
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: 1-17 odd, 23-27 odd
Challenge: Cantor Expansions 46-48
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, 35-37 		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.
Self-Assessment 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: 27-30 (hashing and pseudorandom numbers), 33-35 (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 pp5-8 of xeroxed handout on 3.3.
W 3/26
10am in class 		Reading: Through p.190. Halting problem optional.
Interactive applets: Master change-making and sorting through the interactive applets called "Making change" and "Sorting Algorithms".
Section 3.1: 1-35 odd (pick several), 39, 41, 53. Challenge: 37, 43, 49, 58-59; Read "The Halting Problem" and work 60-62.
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.1-2.3
Practice test here 		Exam 1, Sections 1.1-2.3
F 3/7
 Read through p173.
Start studying for Exam 1:
*Chapter 1 and Chapter 2 self-assessments,
*Homeworks 1-6,
*Lecture material and examples.
The exam will require writing proofs, and will have short answer or multiple choice like Quiz 1.
Section 2.4: 1-9 odd, 13-21 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 1-1 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: 11-27 odd
F 2/29
10am in class 		Work the self-assessment "Concept of a function" (floor and ceiling functions defined on pp.142-143)
Section 2.3: 1-9 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: 59-63
M 2/25
 Quiz on Monday 2/25.
Read through p138.
Work the self assessment on sets
Section 2.1: 23-35 odd.
Section 2.2: 1, 3, 9, 13, 15, 19, 25-31 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 self-assessment applets.
Sect. 2.1: 23-35 odd
Sect. 2.2: 1-11 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 pp80-81 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: 1-21 odd.
F 2/15
10am in class 		Read p.82 and all of Section 1.7 (pp86-102). This is a critical section -- you should spend at least 1 hour on it before class Friday.
Section 1.6: 9-17 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 self-assessment 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, 23-33 odd
Section 1.6: 1-7 odd
Challenge. Section 1.5: 35.
M 2/11
 Section 1.5: 1, 3, 7, 9-17 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 pp3-4.
Section 1.4:1-47 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 self-assessments for 2/4, right? You should spend a little more time on "Quantified Statements".
Suggested Problems. Sect. 1.3: 27-37 odd, 41, 43, 45-53 odd
Challenge (Optional application problems): 55-61 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 1-25
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 NP-completeness. 		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 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/28 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])
F 1/25 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/