Skip down to homework assignments and daily required reading
Instructor: Robert Ellis 
Office: E1 Bldg, Rm 105C 
Email: 
Lectures 
MWF
1:50pm2:40pm 
Perlstein Hall 109 
Office Hours 
T
12:45pm1:45pm (430 priority) 
Office
phone 5675336 

Appointments and emailed questions are welcome 

Textbook 
Rosen,
Discrete Mathematics and its Applications, 6th edition, McGraw Hill 

Recommended
tutors: Claire, Cory, Daniel, Mike M. (Math); Daniel, Lam (CS). Best proofs
help: Cory M 67pm. 
First day handout (pdf)
(course contract & exam schedule)
Extra credit opportunities
and policy (see below)
Exams 


Quizzes 
Exam 1 
Exam 2 
Final 

F 2/18 
F 4/8 
F 5/6
24pm 

Practice Exams 

Term 
Quizzes 
Exam 1 
Exam 2 
Final 
Spring
`09 

Spring
`08 
Sample
homework cover sheet; or, something equivalent can be signed on the top of
the first homework page
Companion
website link: http://highered.mcgrawhill.com/classware/selfstudy.do?isbn=0072880082
Due Date 
Reading & Suggested problems ^{3, 1} 
TurnIn HW Assignment ^{2} ^{*} 

F 5/6 
Final Exam 2:00pm4:00pm Notice of all potential grading
errors must be made by 2pm. Topics: The final is cumulative, except
that the material from after Exam 2 will appear somewhat more frequently. Study these: All previous exams and quizzes. All selfassessments and
interactive demonstrations previously mentioned. The slides from Sections 4.38.1
on Blackboard. A practice sheet focusing on material
in Chapter 4 and beyond. Section 4.4: Focus on Fibonacci
numbers and MergeSort. 
Final Exam 2:00pm4:00pm 

F 4/29 
Read: Sections
8.1, 8.5 Work the selfassessment
on counting  this material will be on the final. Suggested exercises. Section 6.1: 117 odd,
21, 25, 29, 35 
HW 14. Clearly
circle or otherwise indicate your answer for all counting and probability
questions. In your final answers, it is not necessary to simplify/expand
binomial coefficients that contain no variable. Sect. 4.4: 6, 44
(you could show two snapshots of the recursion tree: one with all splits on
the way down, and the other with all merges on the way up.) Sect. 5.1: 14,
20abcd, 28, 40, 42, 54 Sect. 5.2: 4, 16, 42 Sect. 5.3: 4, 12, 32 Sect. 5.4: 4, 24 

W 4/27 
Read: Sections 6.1 Suggested exercises. Section 5.1: 3, 11,
17, 21, 27, 33, 39, 51, 55; Section 5.2: 2628, 36
(Ramsey Theory); 38
(possible nonexistence in Ex. 37), 41 (approximating irrationals with rationals) Section 5.3: 127 odd
(pick a few). Section 5.4: 19 odd,
19, 23 Section 5.3: 29, 43 Section 5.4: 27, 29 

M 4/25 
Read: Sections
5.2, 5.3, 5.4 Suggested exercises. Section 5.1: 1, 9, 13,
19, 25 

F 4/22 
Quiz 3 1:502:00pm. Study these: (1) Chapter
4 Self Assessments on mathematical induction and recursive functions; and (2) The interactive
demonstration applet for Merge Sort (select `Animated` and press play) Read: Section 5.1 Suggested Problems. Section
4.4: 1, 5,
9, 15, 19, 23, 25, 2735 odd 
Quiz 3 1:502:00pm. HW 13. Write clear proofs, clearly identifying basis and inductive
steps. Do not clutter your proofs with `side work.` Sect. 4.2: 4, 10 (collect data in order to form your
hypothesis), 32, 38 Sect. 4.3: 4bc, 6cd, 8, 18 

W 4/20 
Read: Section
4.4 to end 

M 4/18 
Read: Section 4.4, 311317 Suggested Problems. Section 4.3: 13, 17, 19 

F 4/15 
Read: Section
4.3 Suggested
Problems. Section 4.3: 19 odd (pick 2) 
HW 12. Show
work/write clear proofs. Sect. 4.1: 18, 22, 34, 40, 48 (explain fully), 70, 74a 

W 4/13 
Read: Section 4.3 Suggested Problems. Section 4.2: 17 odd (pick 1 or 2) 

M 4/11 
Read: Section
4.2 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 
HW 11. Show
work/write clear proofs. Sect. 3.5:
12bc, 20bf, 22bf, 26, 32 (Hint: gcd(a,m) divides m is key) Sect. 3.6: 10, 20,
24cd, 28ab Sect. 4.1: 4, 6, 10 

F 4/8 
Exam 2: Focus on sections 1.73.4 (BUT: unavoidably
prior material will be involved.) Study these Ch1 Selfassessment:
Proof Strategy Ch2 Selfassessments Ch3 Selfassessment Both Ch3 Interactive
Demonstrations HWs 610 The limit method to see if f(x) is
O(g(x)), etc. Previous exams and keys (Note:
Exams 1 and 2 are earlier than in the past, and so material on past exams
does not line up exactly. You will have to look at all previous exams.) 
Exam 2 

W 4/6 
Sugested problems. Section 4.1: 317 odd (pick a couple) 

M 4/4 
Read: Section 4.1. Skim: Section 3.8, reading carefully anything that looks unfamiliar. Section 3.7: If you are interested in number theory or
cryptography, read this section carefully. Suggested Problems. Sect. 3.6: 117 odd, 2327 odd For CS
interest. Sect. 3.6: 3244; One`s complement and Two`s complement exercises for
improving speed of arithmetic. Challenge. Sect. 3.6: Cantor Expansions 4648 
Quiz 3. 1:50pm2:00pm Study the Chapter 3 SelfAssessment:
Growth of functions, plus algorithms for sorting, searching, and making
change. The format will be multiple choice with
possibly some short answer or free response. 

F 4/1 
Read: Section 3.6 Discover the next Mersenne Prime on your own computer! See the GIMPS page that crowdsources the primes
search. Suggested
Problems. Sect. 3.5: 15 odd, 1131 odd Challenge.
Sect. 3.5:
7, 9, 3337 
HW
10. Show all proofs or supporting calculations. Sect.
3.3: 12ab, 26
Sect.
3.4: 6, 8, 12 (the forward direction of Thm.
3), 24, 28 (read p.206), 32c (read p.207) 

W 3/30 
Read: Section 3.5 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. Sect. 3.4: 127 odd, 31 


M 3/28 
Continuing
in Sect. 3.4 


F 3/25 
Read: Section 3.4 SelfAssessments
(goal: 90% correct, quickly): Growth
of Functions Optional Reading: The Caesar
Cypher, RSA (public key encryption) Challenge.
Sect. 3.2: 55,
60, 6163 
Quiz 2 1:50pm2:00pm Study the Chapter 2 SelfAssessments:
Sets, Concept of Function, OnetoOne and Onto Properties of Functions HW 9. Warning: The first three questions, from
Sect. 3.1, were on HW 8. Grading on them was postponed due to the textbook
website issues. You must either detach these questions from your HW 8, or
rewrite them, and resubmit them with HW 9. Sect. 3.1: 34, 38 (see Sorting
Algorithm applet),
Sect. 3.2: (You may use the limit method
discussed in class for 8ab and 20ab only.) Sect. 3.3: 8, 10ab 

W 3/23 
Read: Section 3.3 Suggested
Problems. Section 3.2: 143 odd 

M 3/21 

F 3/11 
Read: Section 3.2 to end Suggested
Problems. Section 3.1: 2735 odd, 41, 53 
HW
8. Sect.
2.4: 10bcdf, 14b, 18b, 20, 24,
36 (similar to proof in class of 37) Sect.
3.1: (write pseudocode for 8,18,24)
34, 38 (see Sorting
Algorithm applet),


W 3/9 
Read: Section 3.2 through p.186 Interactive
Demonstration Applets: Making
Change, Sorting
Algorithms
(execute pseudocode by hand to understand
algorithms) Animated
sorting algorithms with linebyline highlighting and variable trace (!).
Caution: minor code variations. Suggested Problems. Section 3.1: 125 odd. 

M 3/7 
Read: Section 3.1 SelfAssessments
(goal: 90% correct, quickly): OnetoOne and Onto Properties of Functions Suggested
Problems. Section 2.4: 121 odd, 27, 3139 odd 

F 3/4 
SelfAssessments
(goal: 90% correct, quickly): Concept of Function 
HW 7. Sect. 2.2: 12, 14, 18c, 20, 26, 30, 46 Sect. 2.3: 6ace, 8adg, 12bc, 14ab, 16ab, 20,
26d, 28abc, 36a 

W 3/2 
Read: Section 2.4 to end SelfAssessments (goal: 90%
correct, quickly): Proof
strategy, sets Section
2.3: 171
odd (skip around); Challenge: 7678 


M 2/28 
Read: Section 2.4 through p.158 


F 2/25 
Section
2.2: 1, 3,
9, 13, 15, 19, 2531 odd; Challenge: 5960 (Multisets),
6163 (Fuzzy sets) 


W 2/23 

HW 6. Write proofs with good structure,
combining math and explanatory text. Sect. 1.7: 4, 8, 12, 18, 28, 32 Sect. 2.1: 10, 16, 22, 30, 36 

M 2/21 



F 2/18 
Exam 1: Sections 1.11.6 Study
these SelfAssessments
(goal: 90% correct, quickly): Conditional Propositions; Direct,
Contraposition, and Contradiction Proofs; Negation of Proposition; Negation
of Quantified Statements; Quantified Statements. Interactive
applets: Truth
tables; Logical
equivalence. 
Exam 1 

W 2/16 
Read:
Section 2.3 Sect. 2.1: 135 odd. Challenge: 38,
39 


M 2/14 
Read: Section 2.2 Section 1.7:
119 odd, 27, 31. Challenge: 35, 37, 4448 


F 2/11 
Read:
Section 2.1 Take
the SelfAssessment
on "Direct, Contraposition, and Contradiction Proofs." Section 1.7: 119
odd, 27, 31. Challenge: 35, 37, 4448 
HW
5. Write proofs with good structure, indicating the proof type
(e.g., direct, contrapositive, contradiction). Most
proofs start by stating the assumption and end by stating the conclusion. For
full credit, proofs must include "glue text" such as this, not just
notation. Sect.
1.6: 6, 14, 16, 24, 30, 38 

W 2/9 
Read: Section 1.7 Section 1.6: 917 odd, 19&21 (read bottom p.78 to top of p.79), 31 (see
p.82), 35 


M 2/7 
Section 1.6: 17 odd 
Quiz
1 (1:50pm2:00pm) Topics: Using
truth tables (e.g., compound propositions, logical equivalence, tautologies,
contradictions); Self
assessments "Conditional Propositions," "Negation of
Propositions." 

F 2/4 
Section 1.5: 1117 odd, 2333 odd In the Self
Assessment page, work through "Negation of Quantified
Statements." 
HW 4. Sect. 1.4: 8, 12jkn, 20bc, 24ad, 28bhj, 30e,
32c, 44 Sect. 1.5:
18, 24, 26 

M 1/31 
Read:
Section 1.6 See also Wikipedia on modus ponens; and
links in this page for modus tollens and
other valid arguments. Section 1.5: 1,
3, 7, 911 


F 1/28 
Read: Section 1.5 
HW 3. Explain answers for full
credit. Sect. 1.1:
Section 1.3: 8, 10de, 16, 20ace, 22c, 24ab,
32cd, 36, 44, 48b (hint: a 2case proof assumes first that A is true, then
that A is false), 50, 52bd 

W 1/26 
See Wikipedia
for examples of ternary logical systems, having three truth values. In the Self
Assessment page, work through "Quantified Statements." 


M 1/24 
In the Self
Assessment page, work through "Conditional Propositions", and
"Negation of Propositions." 


F 1/21 
Read:
Section 1.4. 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. 
(Unless specified, you may choose whether or not to print your
solution from a java applet. But you must do this cleverly for some problems
to avoid 2+ pages per problem. For example, 32 has 6
parts but must be printed on one page if done by java applet.) HW
2. Sect. 1.1: 28de, 30abe, 32, 36, 44,
Sect.
1.2: 4b, 8cd, 14,
30, 32, 46, 48, 54,


W 1/19 
Read: Section 1.3. Understand the four
examples in Blackboard>Course Documents from F 1/14 of truth
tables and logical
equivalence reductions using the Java applets. Suggested Problems. Show
p=>q is logically equivalent to ~pvq. 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 


F 1/14 
Read:
Section 1.2 and Section 1.3 through p.37. 
(If no parts are specified, do all parts. Full credit requires
showing steps or giving an explanation.) HW
1. 

W 1/12 
Read: Section 1.1, especially
conditionals on pp69. You must understand page 6. 

*Warning: Use of editions
other than the 6^{th} edition is at
your own risk.
[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 5pm on the Tuesday
before the homework is due. Homework is due 1:50pm in class, 12:40pm 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!
Up to 2 points of extra credit on your final course percentage can be earned. The broad requirement is active participation in a meaningfully enriching activity with significant and clearly identifiable mathematical content. By default, each such activity is worth 1/2 point. The strictest possible grading scale without extra credit is A:89 B:78 C:67 D:56; thus with 2 points of extra credit this becomes A:87 B:76 C:65 D:54. Caution: extra credit must be viewed as over and above all efforts for the course, not as a replacement for, say, turning in a homework. You cannot get duplicate credit for a function that you are already participating in for another class. Here is a list of opportunities; you are welcome to request approval for specific opportunities (e.g., lectures or seminars) along these guidelines.
1. Participate in the student/candidate discussion, attend the candidate lecture, and submit a thoughtfully completed feedback form for one of the senior lecturer candidates that the Applied Mathematics department is interviewing (see doodle link sent via Blackboard).
2. Attend the Menger Day Lecture by Prof. Peter Winkler, M 4:30pm 4/4/11; write a summary report (see requirements here).
3. Attend a plenary talk at the ISMAA meeting in Naperville, IL on RSa 4/74/9/11; write a summary report (see requirements here).
4. Participate as part of a 13 person team in the ISMAA student contest at the ISMAA meeting in Naperville, IL on the afternoon of F 4/8/11, and obtain a nonzero score.
5. Participate in the 4^{th} annual undergraduate math contest hosted by the Applied Math department, in April 2011 (time TBA), and obtain a nonzero score.
Requirements
for a summary report
Submission format
500600 words, by Email, google doc, word doc, or pdf file of typewritten text only.
Recommended report outline
A summary report for a mathematics lecture/presentation
could have the following structure:
I. Introduction of the topic and main theme of the report, as well as the name
and title of the speaker, date, location, etc.
II. Listing of key definitions, theorems, or supporting ideas, including equations or natural language description of the mathematics involved.
III. Discussion of interesting relationships observed, conclusions draw, examples given, etc.
IV. Mention of what further questions, research, conjectures, etc. remain to be investigated.
V. Key references from which more can be learned.
Quoting, sources, and avoiding plagiarism
For copied material, esp. definitions, theorems, direct quotes from speaker, etc.:
It is okay to quote (copy) in limited ways provided full credit is given to the source of the material. Reports submitted with uncredited quotes will automatically disqualify the attempt.
page maintained by Robert Ellis / http://math.iit.edu/~rellis/