MATH 230-01 Intro to Discrete Math S`11 (Ellis) -- IIT Applied Mathematics

MATH 230-01 Intro. to Discrete Math. (Ellis) Spring 2011

Skip down to homework assignments and daily required reading

Instructor: Robert Ellis	Office: E1 Bldg, Rm 105C	Email:
Lectures	MWF 1:50pm-2:40pm	Perlstein Hall 109
Office Hours	T 12:45pm-1:45pm (430 priority) R 2:35pm-3:35pm (230 priority)	Office phone 567-5336
	Appointments and emailed questions are welcome
Textbook	Rosen, Discrete Mathematics and its Applications, 6th edition, McGraw Hill
ARC Tutoring	Recommended tutors: Claire, Cory, Daniel, Mike M. (Math); Daniel, Lam (CS). Best proofs help: Cory M 6-7pm.

First day handout (pdf) (course contract & exam schedule)
Extra credit opportunities and policy (see below)

Exams
	Quizzes	Exam 1	Exam 2	Final
	W 2/2, F 3/25,4/22 Q1,Q1 key (others: see Blackboard)	F 2/18 key on Blackboard	F 4/8 key on Blackboard	F 5/6 2-4pm
Practice Exams
Term	Quizzes	Exam 1	Exam 2	Final
Spring `09	Q1, Q1 key	ExA ExB Key	Ex2 Key Practice for 2.3-4.2	FinalA Key A/B
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

Sample homework cover sheet; or, something equivalent can be signed on the top of the first homework page

Companion website link: http://highered.mcgraw-hill.com/classware/selfstudy.do?isbn=0072880082

Due Date

Reading & Suggested problems ^{3, 1}

Turn-In HW Assignment ² ^*
(Warning: read the due dates!)

F 5/6

Final Exam 2:00pm-4: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 self-assessments and interactive demonstrations previously mentioned.

The slides from Sections 4.3-8.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:00pm-4:00pm

F 4/29

Read: Sections 8.1, 8.5

Work the self-assessment on counting -- this material will be on the final.

Suggested exercises. Section 6.1: 1-17 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: 5, 9, 19b, 21 (show Example 12 is "sharp"!), 33, 37 (see Example 10)

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

Section 5.3: 1-27 odd (pick a few).

Section 5.4: 1-9 odd, 19, 23
Challenge. Section 5.1: 44, 45, 58, 62

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:50-2: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, 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.

Quiz 3 1:50-2: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, 311-317

Suggested Problems. Section 4.3: 13, 17, 19
Challenge. Section 4.3: 15, 16

F 4/15

Read: Section 4.3

Suggested Problems. Section 4.3: 1-9 odd (pick 2)
Challenge. Section 4.2: 18-22 even (discrete geometry), 30 (strong induction flaw), 41-43 (equivalence of well-ordering, induction, and strong induction)

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: 1-7 odd (pick 1 or 2)

M 4/11

Read: Section 4.2

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. Section 4.1: 51, 57, 59, 65-57, 75

HW 11. Show work/write clear proofs.

Sect. 3.5:

4ef	Use the improved prime factorization procedure described on W 3/30, showing all failed and successful divisions.

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.7-3.4 (BUT: unavoidably prior material will be involved.)

Study these

Ch1 Self-assessment: Proof Strategy

Ch2 Self-assessments

Ch3 Self-assessment

Both Ch3 Interactive Demonstrations

HWs 6-10

The guide to proof writing

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: 3-17 odd (pick a couple)

M 4/4

Menger Day 2011

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: 1-17 odd, 23-27 odd

For CS interest. Sect. 3.6: 32-44; One`s complement and Two`s complement exercises for improving speed of arithmetic.

Challenge. Sect. 3.6: Cantor Expansions 46-48
Extra reading: Primality Testing and Integer Factorization

Menger Day 2011

Quiz 3. 1:50pm-2:00pm

Study the Chapter 3 Self-Assessment: 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 crowd-sources the primes search.

Suggested Problems. Sect. 3.5: 1-5 odd, 11-31 odd

Challenge. Sect. 3.5: 7, 9, 33-37

HW 10. Show all proofs or supporting calculations.

Sect. 3.3: 12ab, 26

28ab	You may quote the number of comparisons as a function of n derived in class for bubble sort. You must show your work to derive the number of comparisons (integer/real comparisons, not loop-bookkeeping comparisons) for selection sort.

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 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

Sect. 3.4: 1-27 odd, 31

M 3/28

Continuing in Sect. 3.4

F 3/25

Read: Section 3.4

Self-Assessments (goal: 90% correct, quickly): Growth of Functions

Optional Reading: The Caesar Cypher, RSA (public key encryption)

Challenge. Sect. 3.2: 55, 60, 61-63

Quiz 2 1:50pm-2:00pm

Study the Chapter 2 Self-Assessments: Sets, Concept of Function, One-to-One 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),

56	find an optimal solution that is not the same as the greedy solution; see Making Change applet
A	Prove bounds on number of coins in optimal change in the Euro coin system (see problem description). This was done for US optimal change as part of the proof of Lemma 1, p.175.

Sect. 3.2: (You may use the limit method discussed in class for 8ab and 20ab only.)
4, 8ab, 16, 20ab, 24bd, 28a, 36 (prove or give c/ex)

Sect. 3.3: 8, 10ab

W 3/23

Read: Section 3.3

Suggested Problems. Section 3.2: 1-43 odd

M 3/21

F 3/11

Read: Section 3.2 to end

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.

HW 8.

Sect. 2.4: 10bcdf, 14b, 18b, 20, 24,

32bc	If countable, clearly describe a bijection with the positive integers or natural numbers; if uncountable, clearly describe a reason, but do not prove.

36 (similar to proof in class of 37)

Sect. 3.1: (write pseudocode for 8,18,24)
8, 18,

24	Assume input has form: a₁,a₂,..,a_n: distinct integers; b₁,b₂,..,b_m: distinct integers; f: function from {a₁,a₂,..,a_n} to {b₁,b₂,..,b_m}. Also assume that f(a_i) returns the image of a_i under f. (One solution employs a nested loop.)

34, 38 (see Sorting Algorithm applet),

56	find an optimal solution that is not the same as the greedy solution; see Making Change 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 line-by-line highlighting and variable trace (!). Caution: minor code variations.

Suggested Problems. Section 3.1: 1-25 odd.

M 3/7

Read: Section 3.1

Self-Assessments (goal: 90% correct, quickly): One-to-One and Onto Properties of Functions

Suggested Problems. Section 2.4: 1-21 odd, 27, 31-39 odd
Extra Challenge: Section 2.4: 40-48

F 3/4

Self-Assessments (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

Self-Assessments (goal: 90% correct, quickly): Proof strategy, sets

Section 2.3: 1-71 odd (skip around);

Challenge: 76-78

M 2/28

Read: Section 2.4 through p.158

F 2/25

Section 2.2: 1, 3, 9, 13, 15, 19, 25-31 odd; Challenge: 59-60 (Multisets), 61-63 (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.1-1.6

Study these

Self-Assessments (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 S`08 and S`09 (except set theory and Sect. 1.7 material not in Sect. 1.6); Quiz 1 S`08; Quiz 1 S`09. Homeworks 1-5, Class notes.

Exam 1

W 2/16

Read: Section 2.3

Sect. 2.1: 1-35 odd. Challenge: 38, 39

M 2/14

Read: Section 2.2

Section 1.7: 1-19 odd, 27, 31. Challenge: 35, 37, 44-48

F 2/11

Read: Section 2.1

Take the Self-Assessment on "Direct, Contraposition, and Contradiction Proofs." Section 1.7: 1-19 odd, 27, 31. Challenge: 35, 37, 44-48

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: 9-17 odd, 19&21 (read bottom p.78 to top of p.79), 31 (see p.82), 35

M 2/7

Section 1.6: 1-7 odd

Quiz 1 (1:50pm-2: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: 11-17 odd, 23-33 odd
Challenge. Section 1.5: 34, 35

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:

6, 10ab, 16

Solve as in class: represent with propositional variables, identify any intermediate conclusions, justify every step.

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, 9-11

F 1/28

Read: Section 1.5
Suggested Problems. 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)

HW 3.

Explain answers for full credit.

Sect. 1.1:

62	(deferred from HW 2) Solve by hand with a truth table or argument, OR solve with the Truth table applet by making and printing two truth tables, one setting a propositional variable to True, and a second setting the same variable to False.

Section 1.3: 8, 10de, 16, 20ace, 22c, 24ab, 32cd, 36, 44, 48b (hint: a 2-case 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."
Suggested Problems. Sect. 1.3: Odds 1-25, 27-37 odd, 41, 43, 45-53 odd
Challenge (Optional application problems): 55-61 odd

F 1/21

Read: Section 1.4.

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.

(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,

62	using the Truth table applet. Print out your truth table and write your explanation on the printout.

Sect. 1.2: 4b, 8cd, 14,

26	using the Logical Equivalence java applet to print your solution,

30, 32, 46, 48, 54,

58	using the Truth table applet by computing the column of the conjunction of all of the given disjunctions. Print out your truth table and write your explanation on the printout.

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.
Show ~(p=>q) is logically equivalent to p^~q.

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

F 1/14

Read: Section 1.2 and Section 1.3 through p.37.
Be familiar with Tables 6-8 on pp.24-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 while referring to Tables 6-8. More on this applet for M 1/17 assignment.
Example: Use the truth table applet to show (p->q)->r is not logically equivalent to p->(q->r) (includes printing instructions).
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])

(If no parts are specified, do all parts. Full credit requires showing steps or giving an explanation.)

HW 1.
Sect. 1.1: 2, 4abcfg, 8ade, 10abcde, 14, 16, 18 (see p.6), 26

W 1/12

Read: 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, select an exercise from the drop-down, and practice filling out truth tables.

*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!

Extra credit policy

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 R-Sa 4/7-4/9/11; write a summary report (see requirements here).

4. Participate as part of a 1-3 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

500-600 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/