Fayetteville State University
College of Basic and Applied Sciences
Department of Mathematics & Computer Science
MATH 150 Discrete Mathematics
Spring 2008
I. Locator Information:
Instructor: Dr. Wu Jing
Course # and Name: MATH 150 Discrete Mathematics Office Location: Smith Hall 213
Semester Credit Hours: 3 Classroom: SBE113
Office hours: W 8:00am-12:00pm TR 8:00-9:00 am & 12:30-1:30pm
Day and Time Class Meets: TR 9:30am---10:45am Office Phone: 910-672-2205
Email address: Homepage: http://faculty.uncfsu.edu/wjing
The following statement should appear on the first page of each course syllabus:
FSU Policy on Electronic Mail: Fayetteville State University provides to each student, free of charge, an electronic mail account () that is easily accessible via the Internet. The university has established FSU email as the primary mode of correspondence between university officials and enrolled students. Inquiries and requests from students pertaining to academic records, grades, bills, financial aid, and other matters of a confidential nature must be submitted via FSU email. Inquiries or requests from personal email accounts are not assured a response. The university maintains open-use computer laboratories throughout the campus that can be used to access electronic mail.Rules and regulations governing the use of FSU email may be found at
http://www.uncfsu.edu/PDFs/EmailPolicyFinal.pdf
II. Course Description:
This is the first part of two-semester course sequence that provides the mathematical base for computer science. However, discrete mathematics has much broader application field that includes operations research, business, engineering, economics, chemistry, and biology. Topics covered include logic and proofs, operations on sets, Venn diagrams, Cartesian products and counting, relations, equivalence relations, functions, graphs as relations, the concept of an algorithm, recurrences for the analysis of algorithms, combinatorics, discrete probability, and introduction to graphs. Prerequisite: MATH131 or equivalent.
III. TEXTBOOK:
Johnsonbaugh, Richard, Discrete Mathematics (6th ed) Upper Saddle River: Prentice-Hall, 2005
IV. SPECIFIC COURSE OBJECTIVES
Upon the completion of this course, the student shall be able to:
1. Implement the notions of prepositional logic, quantifiers, and rules of inference.
2. Apply mathematical induction.
3. Recognize a binary relation on a set.
4. Employ the concept of a function as a special case of a binary relation.
5. Classify a given binary relation on a set as being an equivalence relation, a partial order or neither.
6. Construct a partition given an equivalence relation on a set.
7. Use different number systems.
8. Employ the notions of an algorithm, recursive algorithm, and complexity of an algorithm.
9. Apply different counting methods using permutations and combinations.
10. State the basic concepts of discrete probability.
11. Solve second-order linear homogeneous recurrence relations with constant coefficients.
12. Apply recurrence relations to the analysis of algorithms.
13. Recognize paths, cycles, and Euler cycles in a graph.
V. COURSE COMPETENCIES
DPI STANDARDS
The DPI standards covered are listed below. Students shall:
8.1 Know the symbolism of Mathematical logic.
8.2 Demonstrate a thorough knowledge of the concepts of equivalence and implication.
8.5 Posses a thorough knowledge of the role of proof in the study and development of mathematics.
8.6 Create original proofs in the various branches of mathematics including direct proofs, indirect proofs,
and proofs using mathematical induction.
8.7 Understand recursive definition of sequences and functions, and use recursion and technology to model
and study the properties of real world processes.
9.1 Use the set theoretic operations: union, intersection, and complementation.
9.3 Demonstrate a thorough knowledge of the concept of a set theoretic relation.
9.4 Demonstrate a thorough knowledge of the concept of a function including knowledge of the concepts:
range, domain, one-to-one, into, onto, and inverse.
NCATE STANDARDS
The NCATE Standards covered in this course are listed below.
1.1 Programs prepare prospective teachers who:
1.1.1 Use a problem-solving approach to investigate and understand mathematics content.
1.1.2 Formulate and solve problems from both mathematical and everyday situations.
1.2.1 Communicate mathematical ideas in writing, using everyday and mathematical language, including
symbols.
1.2.2 Communicate mathematical ideas orally, using both everyday and mathematical language.
1.3 Programs prepare prospective teachers who can make and evaluate mathematical conjectures and
arguments and validate their own mathematical thinking.
1.4 Programs prepare prospective teachers who:
1.4.1 Show an understanding of the interrelationship within mathematics.
1.4.2 Connection of mathematics to other disciplines and real-world situations.
1.5 Programs prepare prospective teachers who:
1.5.1 Understand and apply of concepts of number, number theory, and number systems.
1.6 Programs prepare prospective teachers who:
1.6.1 Use of calculators in computational and problem-solving situations.
1.6.2 Use computer software to explore and solve mathematical problems.
VI. EVALUATION CRITERIA/GRADING SCALE
Homework will be collected regularly. There will be four tests, and a comprehensive final exam. The lowest test score and the lowest homework score will be dropped. The weight given to various activities for evaluation is as follows: tests-40%, final exam-20%, homework-40%. There will be some extra credit from unannounced quizzes. Any student that misses no more than THREE lectures throughout the entire course will be awarded THREE bonus points towards their final grade.
Grading Scale:
A 90 - 100% B 80 - 89% C 70 - 79% D 60 - 69% F Below 60%
VII. TENTATIVE COURSE OUTLINE *
1.1. Propositions
1.2. Conditional Propositions and Logic Equivalence
1.3. Quantifiers
1.4. Nested Quantifiers
1.5. Proofs
1.6. Resolution Proofs
1.7. Mathematical Induction
Test #1
2.1. Sets
2.2. Functions
2.3. Sequences and Strings
3.1. Relations
3.2. Equivalence Relations
3.3. Matrices of Relations
Test #2
4.1. Introduction
4.2. Examples of Algorithms
4.3. Analysis of Algorithms
4.4. Recursive Algorithms
5.1. Divisors
5.2. Representations of Integers and Integer Algorithms
5.3. The Euclidean Algorithm
Test #3
6.1. Basic Counting Principles
6.2. Permutations and Combinations
6.3. Algorithms for Generating Permutations and Combinations
6.4. Introduction to Discrete Probability
6.6. Generalized Permutations
6.7. Binomial Coefficients and Combinatorial Identities
Test #4
7.1. Introduction to Recurrence Relations
7.2. Solving Recurrence Relations
7.3. Applications to the Analysis of Algorithms
Final Exam (comprehensive)
* This schedule is subject to change for the optimum benefit of the class as a whole. Therefore it is important to stay alert and attend class regularly.
VIII. COURSE REQUIREMENTS
1. Students are responsible for availing themselves of all class meetings.
2. Students are expected to enter the classroom on time and remain until the class ends so that distractions
may be kept at a minimum. Please be considerate of your fellow students.
3. Students are encouraged to ask questions of the instructor in class and to respond to those posed by the
instructor. They should not discourage others from asking or answering questions. Other students often
have the same questions on their minds, but are hesitant to ask.
4. Students are expected to complete all class assignments and to spend adequate time at home on their
class work to insure that the course outcomes are met.
5. Talking in class between students is strictly unacceptable. Discussions should be directed to the instructor.
6. Late homework will no longer be accepted after it has been graded and returned to class.
7. Questions on the grading of a test are allowed only during the class period when the test is returned.
8. If you miss a test you can have a make-up test only with a documented excuse.
IX. TEACHING STRATEGIES
The teaching strategies for this course will be: lectures and group discussion
X. REFERENCES
Goodaire, Edgar G., Parmenter, Michael M., Discrete Mathematics with Graph Theory, 2nd ed. Upper Saddle River: Prentice-Hall, 2002
Gossett, Eric, Discrete Mathematics with Proofs, Upper Saddle River: Prentice-Hall, 2003
Ross, Kenneth A., Wright, Charles R.B., Discrete Mathematics. 5th ed. Upper Saddle River: Prentice-Hall, 2003