MATHEMATICS 116
Juniata College
Discrete Structures
Fall 2008
Grading |
Course Schedule |
Course policies |
Description:
Mathematics 116 introduces mathematical structures and concepts such as:
functions, relations, logic, induction, counting, and graph theory. Their application
to Computer Science is emphasized. This course now carries a Q designation,
which means it has a QS (Quantitative Statistics) component in addition to the
QM (Quantitative Math) and component. The“basic statistical competency”
will be met by studying data representation, measures of central tendency and
dispersion, and basic probability.
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 8:00 - 8:55am C-212, Brumbaugh
Academic Center
Tu 8:00 - 8:55am
P-107, Brumbaugh Academic Center
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-10: 0534359450
ISBN-13:
978-0534359454
Grading:
100 pts.
Exam 1 - Friday, Sept. 19
100 pts.
Exam 2 - Monday, Oct. 20
100 pts.
Exam 3 - Monday, Nov. 17
100 pts.
Exam 4 - Tuesday, Dec. 09
up to 150 pts. Quizzes
up to 100 pts. Labs and Written Homework
25 pts.
Class Participation, Attendance, and Professionalism
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. There will be time at the start of
each class to discuss the problems assigned from the previous class. The
student should have a notebook or folder devoted to completed problems, and
be prepared to share this notebook or folder with the instructor.
Tuesday Labs:
Every Tuesday the class will meet in room P-107, which is a computer lab. Most
weeks students will work on computer-based labs, which support the topics discussed
in lectures. Students will use Moodle to upload their completed lab files.
Exams:
Exams will be written and the use of any type of personal communication devices
or audio devices is forbidden.
| Day | Topic | In-class Work | Homework |
| 00 08/25 |
Intro | Student Info Read Preface xi-xiii and Section 1.1 |
|
| 01 08/26 |
1.1 - Logical Form and Logical Equiv. | 1.1 - 2, 3, 6, 8, 9, 12, 13, 14, 15, 17 | |
| 02 08/27 |
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 08/29 |
Finish 1.2 | 1.2 - 22abd, 23abd, 26, 32, 34, 43, 46 | |
| 04 09/01 |
1.3 - Valid and Invalid Arguments Quiz 01 |
Fall 2007 Quiz 01 Fall 2007 Quiz 01 Key |
1.3 - 2, 5, 8, 23, 24, 27, 30, 31, 38a |
| 05 09/02 |
2.1 - Intro to Predicates and Quantified Stmts I |
Predicates
and Domains from Doug Ensley at Shippensburg Univ. Quantified Statements from Doug Ensley at Shippensburg Univ. go ahead and try: Domains and Negation from Doug Ensley at Shippensburg Univ. Negation of Predicates w/Implications from Doug Ensley at Shippensburg Univ. |
2.1 - 1, 4, 9, 11, 13, 15, 16, 17, 18, 19, 20, 22, 23 |
| 06 09/03 |
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 | |
| 07 09/05 |
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/08 |
2.4 - Arguments w/Quantified Statements Quiz 02 |
Fall 2007 Quiz 02 Fall 2007 Quiz 02 Key |
2.4 - 2, 6, 7, 9, 13, 16, 19, 33 |
| 09 09/09 |
3.1 - Direct Proof and Counterexample |
Counterexamples
from Doug Ensley at Shippensburg Univ. Fill in the Blanks from Doug Ensley at Shippensburg Univ. go ahead and try: Proof Reader from Doug Ensley at Shippensburg Univ. Srambled Proofs from Doug Ensley at Shippensburg Univ. |
3.1 - 1, 2, 7, 9, 12, 14, 18, 19, 20 |
| 10 09/10 |
Finish 3.1 | 3.1 - 24, 28, 30, 31, 38, 39, 41, 47 | |
| 11 09/12 |
3.5 - Direct Proof and Counterexample 3.6 - Indirect Argument Quiz 03 |
Fall 2007 Quiz 03 Fall 2007 Quiz 03 Key |
3.5 - 1, 2, 3, 4, 6, 7, 8, 11, 12 |
| 12 09/15 |
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 09/16 |
Sequences, Series, and Inductive Thinking | Maple Introduction Closed Forms for Recursive Sequences from Doug Ensley at Shippensburg Univ. |
|
| 14 09/17 |
4.2 - Induction Intro | |
4.2 - 2, 3, 4 |
| 15 09/19 |
Exam 1 | Fall 2007 Exam 1 Fall 2007 Exam 1 Key |
|
| 16 09/22 |
More Induction | Closed
Forms for Series from Doug Ensley at Shippensburg Univ. Srambled Induction Proofs from Doug Ensley at Shippensburg Univ. |
Blank Inductive Proofs Detailed Sample Proof |
| 17 09/23 |
4.2 - Mathematical Induction I | 4.2 - 6, 8, 12, 16, 19, 21, 24, 25, 27 | |
| 18 09/24 |
4.3 - Mathematical Induction II | 4.3 - 3, 5, 7, 24, 29 | |
| 19 09/26 |
Induction Wrap-Up Quiz 04 |
Fall 2007 Quiz 04 Fall 2007 Quiz 04 Key |
|
| 20 09/29 |
5.1 - Basic Defn. of Set Theory |
|
5.1 - 1, 2, 3, 4, 7, 8, 9, 10, 13a, 21, 29 |
| 21 09/30 |
Finish 5.1 |
First, look at these three links: Finally, when you have time: |
5.1 - 5, 18, 19, 23, 26, 28 |
| 10/01 | No Class: INGEMAR Conference |
||
| 10/03 | No Class: INGEMAR Conference |
||
| 10/06 | Fall Break | ||
| 10/07 | Fall Break | ||
| 22 10/08 |
Averages and Standard Deviation | Averages and Standard Deviation Homework | |
| 10/10 | No Class: CCSC-E Conference |
||
| 23 10/13 |
z-scores and Normal Distributions Notes to help determine whether data is normally distributed |
||
| 24 10/14 |
Averages and Standard Deviation Lab |
z-scores and Normal Distributions Homework | |
| 25 10/15 |
6.1 - Introduction to Counting and Probability | 6.1 - 3, 5, 7, 9, 12, 13, 18, 21, 23, 26, 28, 31, 32 | |
| 26 10/17 |
Exam Review | ||
| 27 10/20 |
Exam 2 | Fall 2007 Exam 2 Fall 2007 Exam 2 Key |
|
| 28 10/21 |
Probability and Counting Lab I | ||
| 29 10/22 |
6.2 - Possibility Trees and the Multiplication Rule | 6.2 - 1, 3, 9, 12, 14, 16, 19, 21, 23, 29, 30, 32, 36 | |
| 30 10/24 |
6.3 - Counting Elements of Disjoint Sets: The Addition Rule | 6.3 - 2, 3, 4, 8, 9, 11, 21, 24, 27, 28 | |
| 31 10/27 |
6.4 - Counting Subsets of a Set: Combinations | 6.4 - 1, 3, 5, 6, 7, 10, 15, 16, 18, 19 | |
| 32 10/28 |
Probability and Counting Lab II |
from Doug Ensley at Shippensburg Univ.: |
|
| 33 10/29 |
6.5 - r-Combinations w/Repetition Allowed | 6.5 - 1, 3, 6, 10 | |
| 34 10/31 |
Probability Wrap-up Quiz 05 |
||
| 35 11/03 |
7.1 - Functions defined on General Sets 7.2 - One-to-One, Onto, and Inverse Functions |
7.1 - 1, 3, 4, 5, 8, 12, 13, 14, 15, 16, 25, 26 7.2 - 1, 2, 3, 6, 7, 8, 9, 14, 20, 21, 24, 28, 36, 37, 42, 43, 46 |
|
| 36 11/04 |
Lab on Functions |
Arrow Diagrams for Functions from Doug Ensley at Shippensburg Univ. |
|
| 37 11/05 |
7.3 - The Pigeonhole Principle | 7.3 - 1, 3, 4, 9, 12, 13, 25, 26, 28, 29 | |
| 38 11/07 |
10.1 - Relations | Two-Set
Arrow Diagrams for Relations from Doug Ensley at Shippensburg Univ.
One-Set Arrow Diagrams for Binary Relations from Doug Ensley at Shippensburg Univ. |
10.1 - 2, 3, 6, 7, 9, 11, 13, 17, 23, 24, 28 |
| 39 11/10 |
10.2 - Reflexivity, Symmetry, and Transitivity Quiz 06 |
10.2 - 1, 3, 5, 7, 9, 11, 12, 13, 14, 23, 24, 25 | |
| 40 11/11 |
Warshall's Algorithm for Transitive Closure | Outline for Warshall's Algorithm Psuedo-code for Warshall's (slightly different from our version) |
|
| 41 11/12 |
10.3 - Equivalence Relations | 10.3 - 1, 2, 3, 4, 7, 8, 16a, 17, 23, 26, 30 | |
| 42 11/14 |
10.5 - Partial Order Relations | 10.5 - 1, 2, 3, 8, 10, 13 | |
| 43 11/17 |
Exam 3 | Fall 2007 Exam 3 Fall 2007 Exam 3 Key |
|
| 44 11/18 |
10.5 - Partial Order Relations, cont. 11.1 - Intro to Graphs |
Six
Degrees of Separation Oracle of Bacon |
10.5 - 11, 16, 51 11.1 - 12, 13, 41 |
| 45 11/19 |
Finish 11.1 11.2 - Paths and Circuits |
11.1 - 1, 3, 5, 6, 8, 15, 16, 19, 22, 24, 25, 26, 28, 36 11.2 - 3, 4, 7a, 8, 11-22 |
|
| 46 11/21 |
Finish 11.2 |
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 go ahead and try: Graph Isomorphism from Doug Ensley at Shippensburg Univ. |
11.2 - 23-31, 36, 42, 47 |
| 47 11/24 |
11.4 - Isomorphism of Graphs | 11.4 - 1-9, 12, 13, 14, 15, 16, 19 | |
| 48 11/25 |
11.5 - Trees | 11.5 - 1, 3, 7-14, 22, 23, 30 | |
| 11/26 | Thanksgiving Break | ||
| 11/28 | Thanksgiving Break | ||
| 49 12/01 |
Finish 11.5 | 11.5 - 32-42, 51 | |
| 50 12/02 |
11.6 - Spanning Trees | 11.6 - 1, 2, 3, 5, 6, 7, 8, 11, 23, 24 | |
| 51 12/03 |
12.1 - Formal Languages and Regular Expressions Quiz 07 |
12.1 - 1, 16, 19, 22, 25, 26 | |
| 52 12/05 |
12.2 - Finite State Automata | 12.2 - 1, 2, 3, 5, 8, 10, 12abc, 13abc, 20a, 22a, 23a, 25a, 26a | |
| 53 12/08 |
Exam Review | ||
| 53 12/09 |
Exam 4 in room C-225 |
Useful links:
Doug Ensley's Homepage
Standard Course Policies:
For the most up-to-date, see http://faculty.juniata.edu/kruse/policies.htm