Course Title CS 208 Discrete Mathematics
Course Schedule 18 October – 12 December 2004
Class Session Days/Time Monday and Wednesday 1930 - 2200
Prerequisite Any math course greater than MA 131
Credit Hours The course is designed to provide a
3-credit hour course.
Required Text Johnsonbaugh, R., “Discrete Mathematics”,
Prentice Hall, 2005, 6th Edition.
Electronic Resources To help with Discrete Mathematics
problems—check out www.purplemath.com
The Website contains expanded explanations of difficult material and links to other sites for additional information about discrete mathematics topics.
Supplements Computer exercises occur throughout the book
on particular topics which are available at
the Web Site that accompanies this textbook.
Instructor’s Name Kathleen Green, PhD
Telephone 208-383-9070 (W)
Availability Feel free to call me between the hours of 8:00 am to 5:00 pm,Monday through Friday. If I am not available, please leave your message and I’ll call you back as quickly as I can.
The mission of Park University, an entrepreneurial institution of learning, is to provide access to academic excellence, which will prepare learners to think critically, communicate effectively and engage in lifelong learning while serving a global community.
Park University will be renowned international leader in providing innovative educational opportunities for learners with the global society.
This course introduces the student to selected finite systems pertinent to the study of computer science. Course topics will include the following: mathematical induction, sets, relations, functions, matrices, graphs, trees, combinatorial analysis, Boolean algebra, and other structures.
FACULTY’S EDUCATIONAL PHILOSOPHY
The instructor’s intent is to communicate with students rather than to lecture to them, and to convince the student that the study of discrete mathematics can be lively, interesting, and a rewarding experience. If the course succeeds you’ll be well started in mathematics or computer science—both use the same language and much of the same kind of thinking. There’s a secret to working tough problems: Try it repeatedly between periods of other activity, like sleeping. Go as far as you can, quit, and see what happens the next morning. Often you’ll have made progress, “by osmosis.” So my advice is to work a little bit every day on this subject rather than a lot just before a deadline. You may spend the same total amount of time either way; but you learn far more, or find better solutions to problems, if you spread out your efforts. Why? Because you’ll have more periods of osmosis. You’ll get more out of class.
“On completion of this course, the student should be able to:<br>
1. Focus using logic on the relationship among statements as opposed to the content of any particular statement.
Discuss some general methods of proofs, one of which, mathematical induction, is used throughout mathematics and computer science.
2. Deal with the language of mathematics. Some of the topics are: sets, sequences, number systems, relations, and functions.
3. Understand the complexity of algorithms, which refers to the time and space required to execute algorithms, and the analysis of the resources required for particular algorithms.
4. Develop several tools for counting.
5. Define a sequence by giving the nth value in terms of certain of its predecessors using recurrence relation.
6. Discuss some important concepts in graph theory, including paths and cycles.
7. Make extensive use of trees.
8. Maximize the flow in a network.
9. Explore the relationship of Boolean algebra to circuits.
Johnsonbaugh, R., “Discrete Mathematics,” Prentice Hall, 2005, 6th Edition.
“Academic Honesty is required of all members of a learning community. Hence, Park will not tolerate cheating or plagiarism on tests, examinations, papers or other course assignments. Students who engage in such dishonesty may be given failing grades or expelled from Park.”
Plagiarism—the appropriation or imitation of the language or ideas of another person and presenting them as one’s original work—sometimes occurs through carelessness or ignorance. Students who are uncertain about proper documentation of sources should consult their instructors.”
CLASSROOM RULES OF CONDUCT
The student shall, at all times, conduct themselves in a responsible and orderly manner, and shall appear for class in a sober and receptive condition. Violation of these conditions is cause for dismissal.
ATTENDANCE AND PARTIDIPATION POLICY (not applicable for Independent Study students)
Instructors are required to keep attendance records and report absences. The instructor may excuse absences for cogent reasons, but missed work must be made up within the term of enrollment. Work missed through unexcused absences must also be made up within the term of enrollment, but unexcused absences may carry further penalties. In the event of two consecutive weeks of unexcused absences in a term of enrollment, the student will be administratively withdrawn, resulting in a grade of “F”. An Incomplete will not be issued to a student who has unexcused or excessive absences recorded for a course. Students receiving Military Tuition Assistance (TA) or Veterans Administration (VA) educational benefits must not exceed three unexcused absences in the term of enrollment. Excessive absences will be reported to the appropriate agency and may result in a monetary penalty to the student. Reports of F grade (attendance or academic) resulting from excessive absence for students receiving financial assistance from agencies not mentioned above will be reported to the appropriate agency.
Each of you needs to actively participate in discussions relating to the subject materials for each week for full participation credit and to make this class an enjoyable learning experience for us all. You should read, analyze, and respond to questions and comments from fellow students and me. These may include additional questions from me, as the discussions evolve, not just the questions assigned at the end of the chapters. Don’t be afraid to express your opinion of the topics that we will discuss. Differences of opinion are normal; but the important thing about any disagreement is to differ with respect and to provide an explanation and clear factual basis for your different point of view.
LATE SUBMISSION OF COURSE MATERIALS
The instructor will not accept assignments late. Assignments not submitted on the due date will receive a grade of “zero”. Purchase your textbook well enough in advance, not having a textbook is NO excuse.
COURSE ASSESSMENT GRADING PLAN
Point Values for the Course Assignments
Homework Assignments 30 pts 100 – 90 A
MidTerm Examination 30 pts 89 – 80 B
Final Examination 30 pts 79 – 70 C
Participation 10 pts 69 – 60 D
Below 60 F
1. MidTerm and Final Examinations – Students are expected to take the MidTerm and Final Examination at the designated time and place. No makeup Exams will be given. The MidTerm Exam is scheduled for the Forth Week and the Final Exam is scheduled for the Eighth Week. Exam questions will test your understanding of the lectures and material presented in the textbook and demonstrations. Emphasis is placed on testing your understanding of the material presented in the course, rather than in testing memorization of facts and figures.
Each of the examinations given during the course will focus on the material just prior of that examination.
2. Homework Worksheets – Worksheets will be due by the end of the Term. The worksheet can be submitted electronically (via email) as MS Word documents to the Instructor.
Week One: 18 October 2004
Chapter 1: Logic and Proofs
1.2 Conditional Propositions and Logical Equivalence
1.4 Nested Quantifiers
· Read Chapter 1 in the text, Discrete Mathematics.
· Do problems on WorkSheet – Chapter One.
Week One: 20 October 2004
Chapter 1: Logic and Proofs
1.6 Resolution Proofs
1.7 Mathematical Induction
1.8 Strong Form of Induction and the Well-Ordering Property
Week Two: 25 October 2004
Chapter2: The Language of Mathematics
2.3 Sequences and Strings
· Read Chapter 32 in the text, Discrete Mathematics.
· Do problems on WorkSheet – Chapter Two.
Week Two: 27 October 2004
Chapter 3: Relations
3.2 Equivalence Relations
3.3 Matrices of Relations
3.4 Relational Databases
· Read Chapter 3 in the text, Discrete Mathematics.
· Do problems on WorkSheet – Chapter Three.
Week Three: 01 November 2004
Chapter 4: Algorithms
4.2 Examples of Algorithms
4.3 Analysis of Algorithms
4.4 Recursive Algorithms
· Read Chapter 4 in the text, Discrete Mathematics. Do problems on WorkSheet – Chapter Four.
Week Three: 03 November 2004
Chapter 5: Introduction to Number Theory
5.2 Representations of Integers and Integer Algorithms
5.3 The Euclidean Algorithm
5.4 The RSA Public-Key Cryptosystem
· Read Chapter 5 in the text, Discrete Mathematics.
· Do problems on WorkSheet-Chapter Five.
Week Four: 08 November 2004
Chapter 6: Counting Methods and the Pigeonhole Principle
6.1 Basic Principles
6.2 Permutations and Combinations
6.3 Algorithms for Generating Permutations and Combinations
6.4 Introduction to Discrete Probability
6.5 Discrete Probability Theory
6.6 Generalized Permutations and Combinations
6.7 Binomial Coefficients and Combinatorial Identities
6.8 The Pigeonhole Principle
· Read Chapter 6 in the text, Discrete Mathematics.
· Do problems on WorkSheet-Chapter Six.
Week Four: 10 November 2004
Week Five: 15 November 2004
Chapter 7: Recurrence Relations
7.2 Solving Recurrence Relations
7.3 Applications to the Analysis of Algorithms
· Read Chapter 7 in the text, Discrete Mathematics.
· Do problems on WorkSheet-Chapter 7.
Week Five: 17 November 2004
Chapter 8: Graph Theory
8.2 Paths and Cycles
8.3 Hamiltonian Cycles and the Traveling Salesperson
8.4 A Shortest-Path Algorithm
8.5 Representations of Graphs
8.6 Isomorphisms of Graphs
8.7 Planar Graphs
8.8 Instant Insanity
· Read Chapter 8 in the text, Discrete Mathematics.
· Do problems On WorkSheet – Chapter 8.
Week Six: 22 November 2004
Chapter 9: Trees
9.2 Terminology and Characterizations of Trees
9.3 Spanning Trees
9.4 Minimal Spanning Trees
9.5 Binary Trees
9.6 Tree Traversals
9.7 Decision Trees and the Minimum Time for Sorting
9.8 Isomorphisms of Trees
9.9 Game Trees
· Read Chapter 9 in the text, Discrete Mathematics.
· Do problems on WorkSheet – Chapter 9.
Week Six: 24 November 2004
Chapter 11: Boolean Algebras and Combinatorial Circuits
11.1 Combinatorial Circuits
11.2 Properties of Combinatorial Circuits
11.3 Boolean Algebras
11.4 Boolean Functions and Synthesis of Circuits
· Read Chapter 11 in the text, Discrete Mathematics.
· Do problems on WorkSheet – Chapter 11.
Week Seven: 29 November 2004
Chapter 12: Automata, Grammars, and Languages
12.1 Sequential Circuits and Finite-State Machines
12.2 Finite-State Automata
12.3 Languages and Grammars
12.4 Nondeterministic Finite-State Automata
12.5 Relationships Between Languages and Automata
· Read Chapter 12 in the text, Discrete Mathematics.
· Do problems on WorkSheet - Chapter 12.
Week Seven: 01 December 2004
Chapter 13: Computational Geometry
13.1 The Closest-Pair Problem
13.2 An Algorithm to Compute the Convex Hull
Read Chapter 13 in the text, Discrete Mathematics.
· Do problems on WorkSheet – Chapter 13.
Week Eight: 06 December 2004
Week Eight: 08 December 2004