MATHEMATICS 116
Juniata College
Discrete Structures
Fall 2009
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-210,
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, 18.Sept
100 pts.
Exam 2 - Monday, 12.Oct
100 pts.
Exam 3 - Monday, 16.Nov
100 pts.
Exam 4 - Tuesday, 08.Dec
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, and students will be expected to bring a laptop to complete the labs. 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.
Athletics and Extra-curricular activities: Students whose attendance might be affected by participation in extra-curricular activities should contact the instructor with their schedule (if available) during the first week of the semester.
Accomodations: If a student has an accomodation, the student is responsible for initiating the process to set up the accomodation. For example, if a student has an accomodation allowing them extra time to complete an exam, the student must approach the instructor to make arrangements for a time and place to take the exam.
| Day | Topic | In-class Work | Homework |
| 08/24 | Intro | Class Participation, Attendance, and Professionalism | Student Info Read Preface xi-xiii and Section 1.1 |
| 08/25 | 1.1 - Logical Form and Logical Equiv. | Lab 01 - Truth Tables due 8:00am Fri, 28.Aug upload in Moodle |
1.1 - 2, 3, 6, 8, 9, 12, 13, 14, 15, 17 |
| 08/26 | Logic Gates Simulator | 1.1 - 25, 29, 34, 39, 42, 44 1.2 - 1, 2, 3, 4, 5, 7, 12, 13, 16, 17, 20abd |
|
| 08/28 | Finish 1.2 | 1.2 - 22abd, 23abd, 26, 32, 34, 43, 46 | |
| 08/31 | 1.3 - Valid and Invalid Arguments Quiz 01 |
Fall 2009 Quiz 01 Fall 2009 Quiz 01 Key |
1.3 - 2, 5, 8, 23, 24, 27, 30, 31, 38a |
| 09/01 | 2.1 - Intro to Predicates and Quantified Stmts I | Lab02 - Symbolic Logic Lab 02 Key |
2.1 - 1, 4, 9, 11, 13, 15, 16, 17, 18, 19, 20, 22, 23 |
| 09/02 | 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 | |
| 09/04 | 2.3 - Statements Containing Multiple Quantifiers | Quantification Example | 2.3 - 1, 3, 9, 10, 13, 14, 15, 21, 28, 32, 33, 38, 39 |
| 09/07 | 2.4 - Arguments w/Quantified Statements Quiz 02 |
Fall 2009 Quiz 02 Fall 2009 Quiz 02 Key |
2.4 - 2, 6, 7, 9, 13, 16, 19, 33 |
| 09/08 | 3.1 - Direct Proof and Counterexample | Lab 03 - Quantified Confusion Lab 03 Key |
3.1 - 1, 2, 7, 9, 12, 14, 18, 19, 20 IT/CS Picnic at Prof. Rhodes' house |
| 09/09 | Finish 3.1 | 3.1 - 24, 28, 30, 31, 38, 39, 41, 47 | |
| 09/11 | 3.5 - Direct Proof and Counterexample 3.6 - Indirect Argument Quiz 03 |
Fall 2009 Quiz 03 Fall 2009 Quiz 03 Key |
3.5 - 1, 2, 3, 4, 6, 7, 8, 11, 12 |
| 09/14 | 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 |
| 09/15 | Sequences, Series, and Inductive Thinking | Maple Introduction Lab 04 - Sequences and Series due 8:00am FRI 25.SEPT upload in Moodle you may work with a partner Closed Forms for Recursive Sequences from Doug Ensley at Shippensburg Univ. |
|
| 09/16 | Exam Review | |
|
| 09/18 | Exam 01 | Fall 2009 Exam 01 Fall 2009 Exam 01 Key |
|
| 09/21 | 4.2 - Induction Intro |
Closed Forms for Series from Doug Ensley at Shippensburg Univ. Srambled Induction Proofs from Doug Ensley at Shippensburg Univ. |
4.2 - 2, 3, 4 |
| 09/22 | Induction |
Extra-credit: If a student attempts to present an inductive proof to the instructor, by Wed, 30.Sept at 8:00am, they will earn 2 extra-credit pts. Depending on the correctness of their proof they could earn a total of 5 extra-credit pts. | |
| 09/23 | 4.2 - Mathematical Induction I | 4.2 - 6, 8, 12, 16, 19, 21, 24, 25, 27 |
|
| 09/25 | More Induction | ||
| 09/28 | 4.3 - Mathematical Induction II An Interesting Discussion of Euler's Sums |
|
4.3 - 3, 5, 7, 24, 29 |
| 09/29 | 5.1 - Basic Defn. of Set Theory |
First, look at these three links: Next, start the Maple Lab Finally, when you have time: |
5.1 - 1, 2, 3, 4, 7, 8, 9, 10, 13a, 21, 29 |
| 09/30 | Induction Wrap-Up Quiz 04 |
Fall 2009 Quiz 04 Fall 2009 Quiz 04 Key |
|
| 10/02 | Finish 5.1 | 5.1 - 5, 18, 19, 23, 26, 28 | |
| 10/05 | Averages and Standard Deviation | Averages and Standard Deviation Homework | |
| 10/06 | Averages and Standard Deviation Lab |
Lab 06 - Averages and Normal
Curves due 12:00 Noon, Fri 09.Oct upload in Moodle |
|
| 10/07 | z-scores and Normal Distributions Notes to help determine whether data is normally distributed |
z-scores and Normal Distributions Homework | |
| 10/09 | Exam Review | ||
| 10/12 | Exam 02 | Fall 2009 Exam 02 Fall 2009 Exam 02 Key |
|
| 10/13 | Counting and Probability Lab I | Lab 07 - Probability and Normal
Curves |
|
| 10/14 | 6.1 - Introduction to Counting and Probability | 6.1 - 3, 5, 7, 9, 12, 13, 18, 21, 23, 26, 28, 31, 32 | |
| 10/16 | Counting and Probability in "Numb3rs" and spam filtering | Anti-Spam Essays Bayesian Filter |
|
| 10/19 | Fall Break | ||
| 10/20 | Fall Break | ||
| 10/21 | 6.2 - Possibility Trees and the Multiplication Rule | 6.2 - 1, 3, 9, 12, 14, 16, 19, 21, 23, 29, 30, 32, 36 | |
| 10/23 | 6.3 - Counting Elements of Disjoint Sets: The Addition Rule | 6.3 - 2, 3, 4, 8, 9, 11, 21, 24, 27, 28 | |
| 10/26 | 6.4 - Counting Subsets of a Set: Combinations | 6.4 - 1, 3, 5, 6, 7, 10, 13, 15, 16, 18, 19 | |
| 10/27 | Probability and Counting Lab II |
Lab 08 - Counting and Probability due 9:00am Tues 03.Nov you may work with one partner upload in Moodle from Doug Ensley at Shippensburg Univ.: |
|
| 10/28 | 6.5 - r-Combinations w/Repetition Allowed Probability Wrap-up |
6.5 - 1, 3, 10, 16 | |
| 10/30 | No Class: CCSC-E Conference |
||
| 11/02 | 7.1 - Functions defined on General Sets |
7.1 - 1, 3, 4, 5, 8, 12, 13, 14, 15, 16, 25, 26 | |
| 11/03 | 7.2 - One-to-One, Onto, and Inverse Functions Lab on Functions |
Arrow Diagrams for Functions from Doug Ensley at Shippensburg Univ. |
7.2 - 1, 2, 3, 6, 7, 8, 9, 14, 20, 21, 24, 28, 36, 37, 42, 43, 46 |
| 11/04 | 7.3 - The Pigeonhole Principle Quiz 05 |
Fall 2009 Quiz 05 Fall 2009 Quiz 05 Key |
7.3 - 1, 3, 4, 9, 12, 13, 25, 26, 28, 29 |
| 11/06 | 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 |
| 11/09 | 10.2 - Reflexivity, Symmetry, and Transitivity | 10.2 - 1, 3, 5, 7, 9, 11, 12, 13, 14, 23, 24, 25 | |
| 11/10 | Warshall's Algorithm for Transitive Closure | Outline for Warshall's Algorithm Psuedo-code for Warshall's (slightly different from our version) |
|
| 11/11 | 10.3 - Equivalence Relations Quiz 06 |
Fall 2008 Quiz 06 Fall 2008 Quiz 06 Key |
10.3 - 1, 2, 3, 4, 7, 8, 16a, 17, 23, 26, 30 |
| 11/13 | 10.5 - Partial Order Relations | 10.5 - 1, 2, 3, 8, 10, 11, 13, 16, 51 | |
| 11/16 | Exam 03 | Fall 2008 Exam 03 Fall 2008 Exam 03 Key |
|
| 11/17 | 11.1 - Intro to Graphs | Six
Degrees of Separation Oracle of Bacon |
11.1 - 12, 13, 41 |
| 11/18 | 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 |
|
| 11/20 | 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 |
| 11/23 | 11.4 - Isomorphism of Graphs | 11.4 - 1-9, 12, 13, 14, 15, 16, 19 | |
| 11/24 | Review of Sections 10.5, 11.1, 11.2 | Euler Circuitsfrom Doug Ensley at Shippensburg Univ. |
|
| 11/25 | Thanksgiving Break | ||
| 11/27 | Thanksgiving Break | ||
| 11/30 | 11.5 - Trees | 11.5 - 1, 3, 7-14, 22, 23, 30, 32-42, 51 | |
| 12/01 | 11.6 - Spanning Trees | 11.6 - 1, 2, 3, 5, 6, 7, 8, 11, 23, 24 | |
| 12/02 | 12.1 - Regular Expressions | 12.1 - 1, 16, 19, 22, 25, 26 | |
| 12/04 | 12.2 - Finite State Automata Quiz 07 |
Fall 2008 Quiz 07 Fall 2008 Quiz 07 Key |
12.2 - 1, 2, 3, 5, 8, 10, 12abc, 13abc, 20a, 22a, 23a, 25a, 26a |
| 12/07 | Exam Review | ||
| 12/08 | Exam 04 in room ??? |
Useful links:
Doug Ensley's Homepage
Standard Course Policies:
For the most up-to-date, see http://faculty.juniata.edu/kruse/policies.htm