Dr. Shannon Overbay
MATH 231 Discrete Structures
SPRING 2017
Section 02, M W F 09:00-09:50 Jepson 123
Office Hours: Math Lab (Herak 224): TBD Office: TBD
Text: Discrete Mathematics and Its Applications (6th or 7th edition) Kenneth Rosen
Grading System: During the course there will be four in-class examinations, each worth 100 points and a comprehensive final examination worth 200 points. There will be an additional 100 points of homework (some will be written homework and some will be online homework at webwork.gonzaga.edu).
Your grade will be based on points earned out of a possible 700.
A 630-700
B 560-629
C 490-559
D 420-489
F 0-419
Plusses or minuses may be attached to these grades at the discretion of the instructor.
Makeup Examinations: Exams must be taken at the normally scheduled time if at all possible. If an exam must be missed due to an athletic or other school event, arrangements should be made at least one week in advance of the normally scheduled exam date. Late makeup exams are only given in case of a documented emergency.
Homework: Assigned homework has the following three purposes: (1) To specify the material students will be responsible for, (2) To provide relevant examples for class discussions and, most importantly, (3) To provide material through which the student can enhance their knowledge of the subject. Selected even-numbered homework problems will be assigned and collected during class on specified dates and certain homework will be completed online (webwork.gonzaga.edu). Additional odd numbered problems will occasionally be assigned for practice, but will not be handed in.
Disabled Student Services: Anyone requiring special accommodations for a documented disability should make arrangements through the DREAM office ×4134.
Academic Honesty: Academic Honesty should be maintained at all times. Any incidents of copying or cheating will result in a failing grade. Please refer to the student handbook for a description of the Academic Honesty policy.
Extra Credit: There will be no extra credit given in this course.
Cell Phones: Phones should be turned off during class and no texting during class!
Attendance: You are expected to attend class. Missing more than six class periods may result in a V grade or a lowering of the course grade by one or more letter grades.
*********************************************************************************************************************************************
Section 02, M W F 09:00-09:50 Jepson 123
Office Hours: Math Lab (Herak 224): TBD Office: TBD
Text: Discrete Mathematics and Its Applications (6th or 7th edition) Kenneth Rosen
Grading System: During the course there will be four in-class examinations, each worth 100 points and a comprehensive final examination worth 200 points. There will be an additional 100 points of homework (some will be written homework and some will be online homework at webwork.gonzaga.edu).
Your grade will be based on points earned out of a possible 700.
A 630-700
B 560-629
C 490-559
D 420-489
F 0-419
Plusses or minuses may be attached to these grades at the discretion of the instructor.
Makeup Examinations: Exams must be taken at the normally scheduled time if at all possible. If an exam must be missed due to an athletic or other school event, arrangements should be made at least one week in advance of the normally scheduled exam date. Late makeup exams are only given in case of a documented emergency.
Homework: Assigned homework has the following three purposes: (1) To specify the material students will be responsible for, (2) To provide relevant examples for class discussions and, most importantly, (3) To provide material through which the student can enhance their knowledge of the subject. Selected even-numbered homework problems will be assigned and collected during class on specified dates and certain homework will be completed online (webwork.gonzaga.edu). Additional odd numbered problems will occasionally be assigned for practice, but will not be handed in.
Disabled Student Services: Anyone requiring special accommodations for a documented disability should make arrangements through the DREAM office ×4134.
Academic Honesty: Academic Honesty should be maintained at all times. Any incidents of copying or cheating will result in a failing grade. Please refer to the student handbook for a description of the Academic Honesty policy.
Extra Credit: There will be no extra credit given in this course.
Cell Phones: Phones should be turned off during class and no texting during class!
Attendance: You are expected to attend class. Missing more than six class periods may result in a V grade or a lowering of the course grade by one or more letter grades.
*********************************************************************************************************************************************
*THIS SYLLABUS IS SUBJECT TO CHANGE*
Be sure to verify all exam and homework dates with instructor.
M 231 Tentative Course Schedule for Spring 2016:
Sections are for the 7th Edition of Rosen (6th Edition in parentheses)
1-11-16 NO CLASS 3-21-16 6.5 (5.5)
1-13-16 1.1 (1.1) 3-23-16 5.3 (4.3)
1-15-16 1.3 (1.2) 3-25-16 NO CLASS EASTER
1-18-16 NO CLASS MLK 3-28-16 NO CLASS EASTER
1-20-16 1.4 (1.3) 3-30-16 8.1 (7.1)
1-22-16 1.5 (1.4) 4-01-16 NO CLASS CONFERENCE
1-25-16 1.7 (1.6) 4-04-16 8.2 (7.2)
1-27-16 1.7 (1.6) 4-06-16 Review
1-29-16 1.8 (1.7) 4-08-16 Exam 3
2-01-16 2.1/2.2 (2.1/2.2) 4-11-16 10.1/10.3 (9.1/9.3)
2-03-16 2.3 (2.3) 4-13-16 10.4/10.5 (9.4/9.5)
2-05-16 Review 4-15-16 10.7 (9.7)
2-08-16 Exam 1 4-18-16 10.8 (9.8)
2-10-16 2.4 (2.4) 4-20-16 11.1/11.4/11.5 (10.1/10.4/10.5)
2-12-16 4.1 (3.4) 4-22-16 9.1/9.3 (8.1/8.3)
2-15-16 NO CLASS PRES. DAY 4-25-16 Review 9.5 (8.5)
2-17-16 4.2 (3.6) 4-27-16 Exam 4
2-19-16 4.3 (3.5) 4-29-16 Final Review
2-22-16 4.4 (3.7) FINAL EXAM:
2-24-16 5.1 (4.1)
2-26-16 5.1 (4.1) 1:00-3:00 p.m., Tuesday, 5-03-16
2-29-16 5.2 (4.2)
3-02-16 Review
3-04-16 Exam 2
3-07-16 NO CLASS SPRING BREAK
3-09-16 NO CLASS SPRING BREAK
3-11-16 NO CLASS SPRING BREAK
3-14-16 6.1/6.2 (5.1/5.2)
3-16-16 6.3 (5.3)
3-18-16 6.4 (5.4)
MATH 231 DISCRETE STRUCTURES TOPIC LIST Spring 2016
Discrete Mathematics and Its Applications, Rosen, 7th edition (6th edition in parentheses)
I) LOGIC, PROOF TECHNIQUES, SETS (EXAM I)
1.1 Propositional Logic (1.1)
1.3 Propositional Equivalences (1.2)
1.4 Predicates and Quantifiers (1.3)
1.5 Nested Quantifiers (1.4)
1.7 Introduction to Proofs (1.6)
1.8 Proof Methods and Strategy (1.7)
2.1 Sets (2.1)
2.2 Set Operations (2.2)
II) INTEGERS, INDUCTION, FUNCTIONS, SEQUENCES/SUMMATIONS (EXAM II)
2.3 Functions (2.3)
2.4 Sequences and Summations (2.4)
4.1 The Integers and Division (3.4)
4.2 Integers and Algorithms (3.6)
4.3 Primes and Greatest Common Divisors (3.5)
4.4 Applications of Number Theory (3.7)
5.1 Mathematical Induction (4.1)
5.2 Strong Induction and Well-Ordering (4.2)
5.3 Recursive Definitions and Structural Induction (4.3)
III) COUNTING, BINOMIAL THEOREM, RECURRENCE RELATIONS (EXAM III)
6.1 The Basics of Counting (5.1)
6.2 The Pigeonhole Principle (5.2)
6.3 Permutations and Combinations (5.3)
6.4 Binomial Coefficients (5.4)
6.5 Generalized Permutations and Combinations (5.5)
8.1 Recurrence Relations (7.1)
8.2 Solving Recurrence Relations (7.2)
IV) GRAPH THEORY AND RELATIONS (EXAM IV)
10.1 Graphs and Graph Models (9.1)
10.2 Graph Terminology and Special Types of Graphs (9.2)
10.3 Representing Graphs and Graph Isomorphism (9.3)
10.4 Connectivity (9.4)
10.5 Euler and Hamilton Paths (9.5)
10.7 Planar Graphs (9.7)
10.8 Graph Coloring (9.8)
11.1 Introduction to Trees (10.1)
11.4 Spanning Trees (10.4)
11.5 Minimum Spanning Trees (10.5)
9.1 Relations and Their Properties (8.1)
9.3 Representing Relations (Graphically and with Adjacency Matrices) (8.3)
9.5 Equivalence Relations (8.5)
Spring 2015 Discrete Structures Suggested Practice Problems
Rosen 7th Edition (Rosen 6th Edition in parentheses)
EXAM 1 EXAM 4
1.1 1-43 odd (1.1 1-37 odd) 10.1 1-9 odd (9.1 1-9 odd)
1.3 1-33 odd (1.2 1-33 odd) 10.2 1-9 odd, 20, 21-25 odd, 26, 25-43 odd
1.4 1-19 odd, 35, 53 (1.3 1-19 odd, 35, 53) (9.2 1-9 odd, 20, 21-25 odd, 26, 27-37 odd)
1.5 1-13 odd, 25-33 odd (1.4 1-13 odd, 25-33 odd) 10.3 1-25 odd, 29, 35-43 (9.3 same exercises)
1.7 1-17 odd, 27-31 odd (1.6 1-17 odd, 27-31 odd) 10.4 1-5 odd, 21, 23 (9.4 1-5 odd, 17-21 odd)
1.8 3, 7, 9, 11, 15 (1.7 3, 7, 11, 27) 10.5 1-9 odd, 26, 27, 28, 31-45 odd (9.5 same)
2.1 1-31 odd (2.1 1-31 odd) 10.7 1-13 odd, 23, 25 (9.7 same exercises)
2.2 1-39 odd, 53 (2.2 1-39 odd) 10.8 5-15 odd (9.8 same exercises)
11.1 1, 3, 7, 9, 11 (10.1 same exercises)
EXAM 2 11.4 1-7 odd (10.4 same exercises)
2.3 1-23 odd, 31, 33 (2.3 1-19 odd, 27, 29) 11.5 1-7 odd (10.5 same exercises)
2.4 1-5 odd, 9, 29, 31 (2.4 1-5 odd, 9, 13, 15) 9.1 1-15 odd (8.1 same exercises)
4.1 1-9 odd, 21, 23, 29 (3.4 1-9 odd, 17, 19) 9.3 1-7 odd, 19-31 odd (8.3 same exercises)
4.2 1-17 odd, 23 (3.6 1-17 odd, 23) 9.5 1, 2, 21, 23, 24, 41 (8.5 same exercises)
4.3 1-5 odd, 15, 17, 25, 27, 31, 33, 39 (3.5 1-5 odd, 11, 13, 21, 23)
4.4 1-5 odd, 9, 11 (3.7 1-7 odd, 11)
5.1 3-11 odd, 21, 31, 33 (4.1 3-11 odd, 21, 31, 33)
5.2 3, 25 (4.2 3)
EXAM 3
6.1 1-35 odd (5.1 1-33 odd)
6.2 1-9 odd, 13, 15 (5.2 1-9 odd, 15)
6.3 1-23 odd, 27 (5.3 1-23 odd, 27)
6.4 1-15 odd, 19, 21 (5.4 1-15 odd, 19, 21)
6.5 1-21 odd, 31 (5.5 1-21 odd, 31)
5.3 1-9 odd, 23, 25 (4.3 1-9 odd, 23, 25)
8.1 7-13 odd, 19 (7.1 1-5 odd, 11, 23-29 odd)
8.2 3-7 odd (7.2 3-7 odd)
Course Learning Outcomes:
-Students will be able to construct logic tables, translate logical propositions from symbols to English and vice-versa, and construct arguments with logical equivalences.
-Students will be able to construct direct proofs, indirect proofs, proofs by contradiction, proofs by cases, induction proofs, divisibility proofs, and proofs of one-to-one and onto.
-Students will write and solve linear recurrences of degree one and two. Students will demonstrate correct usage of the ‘big four’ of counting and will be able to apply the binomial theorem to determine coefficients.
-Students will translate between different bases, calculate gcd(a,b) and lcm(a,b), find prime factorizations, apply the division algorithm, and apply the Euclidean algorithm.
-Students will identify appropriate properties of graphs (e.g. planar, Eulerian, Hamiltonian, bipartite) and relations (e.g. symmetric, reflexive, transitive). Students will determine minimum spanning trees using Prim’s and Kruskal’s algorithms
M 231 Tentative Course Schedule for Spring 2016:
Sections are for the 7th Edition of Rosen (6th Edition in parentheses)
1-11-16 NO CLASS 3-21-16 6.5 (5.5)
1-13-16 1.1 (1.1) 3-23-16 5.3 (4.3)
1-15-16 1.3 (1.2) 3-25-16 NO CLASS EASTER
1-18-16 NO CLASS MLK 3-28-16 NO CLASS EASTER
1-20-16 1.4 (1.3) 3-30-16 8.1 (7.1)
1-22-16 1.5 (1.4) 4-01-16 NO CLASS CONFERENCE
1-25-16 1.7 (1.6) 4-04-16 8.2 (7.2)
1-27-16 1.7 (1.6) 4-06-16 Review
1-29-16 1.8 (1.7) 4-08-16 Exam 3
2-01-16 2.1/2.2 (2.1/2.2) 4-11-16 10.1/10.3 (9.1/9.3)
2-03-16 2.3 (2.3) 4-13-16 10.4/10.5 (9.4/9.5)
2-05-16 Review 4-15-16 10.7 (9.7)
2-08-16 Exam 1 4-18-16 10.8 (9.8)
2-10-16 2.4 (2.4) 4-20-16 11.1/11.4/11.5 (10.1/10.4/10.5)
2-12-16 4.1 (3.4) 4-22-16 9.1/9.3 (8.1/8.3)
2-15-16 NO CLASS PRES. DAY 4-25-16 Review 9.5 (8.5)
2-17-16 4.2 (3.6) 4-27-16 Exam 4
2-19-16 4.3 (3.5) 4-29-16 Final Review
2-22-16 4.4 (3.7) FINAL EXAM:
2-24-16 5.1 (4.1)
2-26-16 5.1 (4.1) 1:00-3:00 p.m., Tuesday, 5-03-16
2-29-16 5.2 (4.2)
3-02-16 Review
3-04-16 Exam 2
3-07-16 NO CLASS SPRING BREAK
3-09-16 NO CLASS SPRING BREAK
3-11-16 NO CLASS SPRING BREAK
3-14-16 6.1/6.2 (5.1/5.2)
3-16-16 6.3 (5.3)
3-18-16 6.4 (5.4)
MATH 231 DISCRETE STRUCTURES TOPIC LIST Spring 2016
Discrete Mathematics and Its Applications, Rosen, 7th edition (6th edition in parentheses)
I) LOGIC, PROOF TECHNIQUES, SETS (EXAM I)
1.1 Propositional Logic (1.1)
1.3 Propositional Equivalences (1.2)
1.4 Predicates and Quantifiers (1.3)
1.5 Nested Quantifiers (1.4)
1.7 Introduction to Proofs (1.6)
1.8 Proof Methods and Strategy (1.7)
2.1 Sets (2.1)
2.2 Set Operations (2.2)
II) INTEGERS, INDUCTION, FUNCTIONS, SEQUENCES/SUMMATIONS (EXAM II)
2.3 Functions (2.3)
2.4 Sequences and Summations (2.4)
4.1 The Integers and Division (3.4)
4.2 Integers and Algorithms (3.6)
4.3 Primes and Greatest Common Divisors (3.5)
4.4 Applications of Number Theory (3.7)
5.1 Mathematical Induction (4.1)
5.2 Strong Induction and Well-Ordering (4.2)
5.3 Recursive Definitions and Structural Induction (4.3)
III) COUNTING, BINOMIAL THEOREM, RECURRENCE RELATIONS (EXAM III)
6.1 The Basics of Counting (5.1)
6.2 The Pigeonhole Principle (5.2)
6.3 Permutations and Combinations (5.3)
6.4 Binomial Coefficients (5.4)
6.5 Generalized Permutations and Combinations (5.5)
8.1 Recurrence Relations (7.1)
8.2 Solving Recurrence Relations (7.2)
IV) GRAPH THEORY AND RELATIONS (EXAM IV)
10.1 Graphs and Graph Models (9.1)
10.2 Graph Terminology and Special Types of Graphs (9.2)
10.3 Representing Graphs and Graph Isomorphism (9.3)
10.4 Connectivity (9.4)
10.5 Euler and Hamilton Paths (9.5)
10.7 Planar Graphs (9.7)
10.8 Graph Coloring (9.8)
11.1 Introduction to Trees (10.1)
11.4 Spanning Trees (10.4)
11.5 Minimum Spanning Trees (10.5)
9.1 Relations and Their Properties (8.1)
9.3 Representing Relations (Graphically and with Adjacency Matrices) (8.3)
9.5 Equivalence Relations (8.5)
Spring 2015 Discrete Structures Suggested Practice Problems
Rosen 7th Edition (Rosen 6th Edition in parentheses)
EXAM 1 EXAM 4
1.1 1-43 odd (1.1 1-37 odd) 10.1 1-9 odd (9.1 1-9 odd)
1.3 1-33 odd (1.2 1-33 odd) 10.2 1-9 odd, 20, 21-25 odd, 26, 25-43 odd
1.4 1-19 odd, 35, 53 (1.3 1-19 odd, 35, 53) (9.2 1-9 odd, 20, 21-25 odd, 26, 27-37 odd)
1.5 1-13 odd, 25-33 odd (1.4 1-13 odd, 25-33 odd) 10.3 1-25 odd, 29, 35-43 (9.3 same exercises)
1.7 1-17 odd, 27-31 odd (1.6 1-17 odd, 27-31 odd) 10.4 1-5 odd, 21, 23 (9.4 1-5 odd, 17-21 odd)
1.8 3, 7, 9, 11, 15 (1.7 3, 7, 11, 27) 10.5 1-9 odd, 26, 27, 28, 31-45 odd (9.5 same)
2.1 1-31 odd (2.1 1-31 odd) 10.7 1-13 odd, 23, 25 (9.7 same exercises)
2.2 1-39 odd, 53 (2.2 1-39 odd) 10.8 5-15 odd (9.8 same exercises)
11.1 1, 3, 7, 9, 11 (10.1 same exercises)
EXAM 2 11.4 1-7 odd (10.4 same exercises)
2.3 1-23 odd, 31, 33 (2.3 1-19 odd, 27, 29) 11.5 1-7 odd (10.5 same exercises)
2.4 1-5 odd, 9, 29, 31 (2.4 1-5 odd, 9, 13, 15) 9.1 1-15 odd (8.1 same exercises)
4.1 1-9 odd, 21, 23, 29 (3.4 1-9 odd, 17, 19) 9.3 1-7 odd, 19-31 odd (8.3 same exercises)
4.2 1-17 odd, 23 (3.6 1-17 odd, 23) 9.5 1, 2, 21, 23, 24, 41 (8.5 same exercises)
4.3 1-5 odd, 15, 17, 25, 27, 31, 33, 39 (3.5 1-5 odd, 11, 13, 21, 23)
4.4 1-5 odd, 9, 11 (3.7 1-7 odd, 11)
5.1 3-11 odd, 21, 31, 33 (4.1 3-11 odd, 21, 31, 33)
5.2 3, 25 (4.2 3)
EXAM 3
6.1 1-35 odd (5.1 1-33 odd)
6.2 1-9 odd, 13, 15 (5.2 1-9 odd, 15)
6.3 1-23 odd, 27 (5.3 1-23 odd, 27)
6.4 1-15 odd, 19, 21 (5.4 1-15 odd, 19, 21)
6.5 1-21 odd, 31 (5.5 1-21 odd, 31)
5.3 1-9 odd, 23, 25 (4.3 1-9 odd, 23, 25)
8.1 7-13 odd, 19 (7.1 1-5 odd, 11, 23-29 odd)
8.2 3-7 odd (7.2 3-7 odd)
Course Learning Outcomes:
-Students will be able to construct logic tables, translate logical propositions from symbols to English and vice-versa, and construct arguments with logical equivalences.
-Students will be able to construct direct proofs, indirect proofs, proofs by contradiction, proofs by cases, induction proofs, divisibility proofs, and proofs of one-to-one and onto.
-Students will write and solve linear recurrences of degree one and two. Students will demonstrate correct usage of the ‘big four’ of counting and will be able to apply the binomial theorem to determine coefficients.
-Students will translate between different bases, calculate gcd(a,b) and lcm(a,b), find prime factorizations, apply the division algorithm, and apply the Euclidean algorithm.
-Students will identify appropriate properties of graphs (e.g. planar, Eulerian, Hamiltonian, bipartite) and relations (e.g. symmetric, reflexive, transitive). Students will determine minimum spanning trees using Prim’s and Kruskal’s algorithms