MATHEMATICS 115
Juniata College
Discrete Structures
Fall 2005
Grading |
Course Schedule |
Course policies |
Description:
Mathematics 115 introduces mathematical structures and concepts such as:
functions, relations, logic, induction, counting, and graph theory. Their
application to Computer Science is emphasized.
Objectives:
The student is expected to develop an understanding of some of the mathematical
structures fundamental to computer science including: functions, relations,
sets, logic, inductions, counting problems, and graph theory. Applications
of these structures to solving real-world problems will also be considered.
Class Times:
MWF 1:00 - 1:55 pm Brumbaugh Academic
Center, C-232
Instructor:
Dr. Gerald Kruse
C-205A Brumbaugh Academic Center
641-3595
kruse@juniata.edu
Office Hours:
For the most up-to-date, see http://faculty.juniata.edu/kruse/office.htm
Textbook:
Discrete Mathematics with Applications, 3rd Edition,
Brooks/Cole Publishing Company, 2004., by Susanna Epp. ISBN
0-534-35945-0.
Grading:
Exam 1
15%
Exam 2
15%
Exam 3
15%
Final Exam
20%
Quizzes
25%
Class Participation, Attendance, and HW
10%
Quizzes:
Quizes will be given weekly. There will be NO make-ups for missed quizes.
However, the lowest two quiz scores will be dropped when calculating the
final grade.
Homework assignments:
Several homework problems will be assigned every class, with one or two problems
turned in each week to be checked for satisfactory completion. Doing
and understanding these homework problems will be a big component of the
student comprehending the course material. The student should have
a notebook or folder devoted to completed problems.
| Day | Topic | In-class Work | Homework |
| 00 08/29 |
Intro | Student Info Read Preface xi-xiii and Section 1.1 |
|
| 01 08/31 |
1.1 - Logical Form and Logical Equiv. | 1.1 - 2, 3, 6, 8, 9, 12, 13, 14, 15, 17 | |
| 02 09/02 |
Finish 1.1 |
1.1 - 25, 29, 34, 39, 42, 44 1.2 - 1, 2, 3, 4, 5, 7, 12, 13, 16, 17, 20abd |
|
| 03 09/05 |
Finish 1.2 | 1.2 - 22abd, 23abd, 26, 32, 34, 43, 46 | |
| 04 09/07 |
1.3 - Valid and Invalid Arguments | 1.3 - 2, 5, 8, 23, 24, 27, 30, 31, 38a | |
| 05 09/09 |
2.1 - Intro to Predicates and Quantified Stmts I | 2.1 - 1, 4, 9, 11, 13, 15, 16, 17, 18, 19, 20, 22, 23 Predicates and Domains from Doug Ensley at Shippensburg Univ. Quantified Statements from Doug Ensley at Shippensburg Univ. |
|
| 06 09/12 |
2.2 - Intro to Predicates and Quantified Stmts II |
2.2 - 1, 2, 3, 4, 7, 8, 10, 13, 15, 23, 24, 28, 35, 38, 40 Domains and Negation from Doug Ensley at Shippensburg Univ. Negation of Predicates w/Implications from Doug Ensley at Shippensburg Univ. |
|
| 07 09/14 |
2.3 - Statements Containing Multiple Quantifiers | Quantification Example | 2.3 - 1, 3, 9, 10, 13, 14, 15, 21, 28, 32, 33, 38, 39 |
| 08 09/16 |
2.4 - Arguments w/Quantified Statements | 2.4 - 2, 6, 7, 9, 13, 16, 19, 33 | |
| 09 09/19 |
3.1 - Direct Proof and Counterexample |
3.1 - 1, 2, 7, 9, 12, 14, 18, 19, 20 Counterexamples from Doug Ensley at Shippensburg Univ. Fill in the Blanks from Doug Ensley at Shippensburg Univ. |
|
| Mountain Day! | |||
| 10 09/23 |
Finish 3.1 |
3.1 - 24, 28, 30, 31, 38, 39, 41, 47 Proof Reader from Doug Ensley at Shippensburg Univ. Srambled Proofs from Doug Ensley at Shippensburg Univ. |
|
| 11 09/26 |
Exam 1 Review 3.5 - Direct Proof and Counterexample 3.6 - Indirect Argument |
3.5 - 1, 2, 3, 4, 6, 7, 8, 11, 12, 14, 22 3.6 - 1, 5, 27 |
|
| 09/28 | Exam 1 | ||
| 12 09/30 |
4.1 - Sequences and Series | Inductive Thinking Worksheet |
4.1 - 1, 3, 5, 8, 11, 13, 16, 19, 20, 23, 32, 35, 40, 43, 46, 52, 56,
58 Section 4.1 HW Solutions |
| 13 10/03 |
Sequences, Series, and Induction Labs in P-107 | Maple Introduction Closed Forms for Recursive Sequences from Doug Ensley at Shippensburg Univ. Closed Forms for Series from Doug Ensley at Shippensburg Univ. |
|
| 14 10/05 |
4.2 - Induction Intro | 4.2 - 2, 3, 4 | |
| 15 10/07 |
4.2 - Mathematical Induction I |
4.2 - 6, 8, 12, 16, 19, 21, 24, 25, 27 Blank Inductive Proofs Detailed Sample Proof |
|
| 16 10/12 |
4.3 - Mathematical Induction II | 4.3 - 3, 5, 7, 24, 29 | |
| 17 10/14 |
Induction Wrap-up | Srambled Induction Proofs from Doug Ensley at Shippensburg Univ. | |
| 18 10/17 |
5.1 - Basic Defn. of Set Theory |
5.1 - 1, 2, 3, 4, 7, 8, 9, 10, 13a, 21, 29 Set Notation from Doug Ensley at Shippensburg Univ. Set Operations from Doug Ensley at Shippensburg Univ. Counterexamples from Doug Ensley at Shippensburg Univ. Two Set Venn Diagrams from Doug Ensley at Shippensburg Univ. Three Set Venn Diagrams from Doug Ensley at Shippensburg Univ. |
|
| 19 10/19 |
Finish 5.1 5.2 - Properties of Sets |
5.1 - 5, 18, 19, 23, 26, 28 5.2 - 1, 2, 3, 4 Complement Maplet Set Difference Maplet Power Set Maplet Cartesian Product Maplet |
|
| 20 10/21 |
Finish 5.2 5.3 - Disproofs, etc. |
5.2 - 5, 12, 13 5.3 - 1, 2, 4, 9, 10, 19, 21 |
|
| 21 10/24 |
7.1 - Functions defined on General Sets | 7.1 - 1, 3, 4, 5, 8, 12, 13, 14, 15, 16, 25, 26 | |
| 22 10/26 |
7.2 - One-to-One, Onto, and Inverse Functions | 7.2 - 1, 2, 3, 6, 7, 8, 9, 14, 20, 21, 24, 28, 36, 37, 42, 43, 46 | |
| 10/28 | Exam 2 | ||
| 23 10/31 |
7.3 - The Pigeonhole Principle | 7.3 - 1, 3, 4, 9, 12, 13, 25, 26, 28, 29 | |
| 24 11/02 |
10.1 - Relations | 10.1 - 2, 3, 6, 7, 9, 11, 13, 17, 23, 24, 28 | |
| 25 11/04 |
10.2 - Reflexivity, Symmetry, and Transitivity | 10.2 - 1, 3, 5, 7, 9, 11, 12, 13, 14, 23, 24, 25 | |
| 26 11/07 |
Warshall's Algorithm for Transitive Closure | Outline for Warshall's Algorithm | |
| 27 11/09 |
10.3 - Equivalence Relations | 10.3 - 1, 2, 3, 4, 7, 8, 16a, 17, 23, 26, 30 | |
| 28 11/11 |
10.5 - Partial Order Relations | 10.5 - 1, 2, 3, 8, 10, 11, 13, 16, 51 | |
| 29 11/14 |
11.1 - Intro to Graphs | Six Degrees of Separation | 11.1 - 12, 13, 41 |
| 30 11/16 |
Finish 11.1 | Oracle of Bacon | 11.1 - 1, 3, 5, 6, 8, 15, 16, 19, 22, 24, 25, 26, 28, 36 |
| 11/18 | Exam 3 | ||
| 31 11/21 |
11.2 - Paths and Circuits | 11.2 - 3, 4, 7a, 8, 11-22 | |
| 32 11/28 |
Finish 11.2 11.3 - Matrix Representation of Graphs |
11.2 - 23-31, 36, 42, 47 11.3 - 2, 3, 4, 5, 6, 7 Eulerian Paths and Circuits from Doug Ensley at Shippensburg Univ. Hamiltonian Paths and Circuits from Doug Ensley at Shippensburg Univ. Sean Forman's TSP Generator |
|
| 33 11/30 |
11.4 - Isomorphism of Graphs |
11.4 - 1-9, 12, 13, 14, 15, 16, 19 Graph Isomorphism from Doug Ensley at Shippensburg Univ. |
|
| 34 12/02 |
11.5 - Trees | 11.5 - 1, 3, 7-14, 22, 23, 30 | |
| 35 12/05 |
Finish 11.5 | 11.5 - 32-42, 51 | |
| 36 12/07 |
11.6 - Spanning Trees | 11.6 - 1, 2, 3, 5, 6, 7, 8, 11, 23, 24 | |
| 37 12/09 |
12.2 - Finite State Automata | 12.2 - 1, 2, 3, 5, 8, 10, 12abc, 13abc, 20a, 22a, 23a, 25a, 26a | |
| 38 12/12 |
12.1 - Formal Languages and Regular Expressions Final Exam Review |
Useful links:
Doug Ensley's Homepage
Standard Course Policies:
For the most up-to-date, see http://faculty.juniata.edu/kruse/policies.htm