12/26/2024 10:54:04 PM	MATH 4 Course Outline as of Fall 2013	Changed Course
CATALOG INFORMATION
Discipline and Nbr:  MATH 4	Title:  DISCRETE MATHEMATICS
Full Title:  Discrete Mathematics
Last Reviewed:9/14/2020

Units		Course Hours per Week			Nbr of Weeks	Course Hours Total
Maximum	4.00	Lecture Scheduled	4.00		17.5 max.	Lecture Scheduled	70.00
Minimum	4.00	Lab Scheduled	0		6 min.	Lab Scheduled	0
		Contact DHR	0			Contact DHR	0
		Contact Total	4.00			Contact Total	70.00
		Non-contact DHR	0			Non-contact DHR Total	0

Total Out of Class Hours:  140.00

Total Student Learning Hours: 210.00

Title 5 Category:  AA Degree Applicable
Grading:  Grade Only
Repeatability:  00 - Two Repeats if Grade was D, F, NC, or NP
Also Listed As: 
Formerly: 

Catalog Description:

A lower division discrete mathematics course including formal logic, Boolean logic and logic circuits, mathematical induction, introduction to number theory, set theory, principles of combinatorics, functions, relations, recursion, algorithm efficiency and graph theory.

Prerequisites/Corequisites:
Completion of MATH 27 or higher (VF); OR Course Completion of MATH 25 and MATH 58; OR Qualifying Test Score in Math Algebra and Course Completion of MATH 58; OR Qualifying Test Score in Math Trigonometry and Course Completion of MATH 25; OR Qualifying Test Score in Math Algebra and Qualifying Test Score in Math Trigonometry

Recommended Preparation:
Course Completion of MATH 1A

Limits on Enrollment:

Schedule of Classes Information
Description:

A lower division discrete mathematics course including formal logic, Boolean logic and logic circuits, mathematical induction, introduction to number theory, set theory, principles of combinatorics, functions, relations, recursion, algorithm efficiency and graph theory.

(Grade Only)
Prerequisites:Completion of MATH 27 or higher (VF); OR Course Completion of MATH 25 and MATH 58; OR Qualifying Test Score in Math Algebra and Course Completion of MATH 58; OR Qualifying Test Score in Math Trigonometry and Course Completion of MATH 25; OR Qualifying Test Score in Math Algebra and Qualifying Test Score in Math Trigonometry
Recommended:Course Completion of MATH 1A
Limits on Enrollment:
Transfer Credit:CSU;UC.
Repeatability:00 - Two Repeats if Grade was D, F, NC, or NP

ARTICULATION, MAJOR, and CERTIFICATION INFORMATION

Associate Degree:		Effective:	Fall 1981	Inactive:
Area:	B MC	Communication and Analytical Thinking Math Competency
CSU GE:	Transfer Area			Effective:	Inactive:
	B4	Math/Quantitative Reasoning		Fall 2001
IGETC:	Transfer Area			Effective:	Inactive:
	2A	Mathematical Concepts & Quantitative Reasoning		Fall 2001
CSU Transfer:	Transferable	Effective:	Fall 2001	Inactive:
UC Transfer:	Transferable	Effective:	Fall 2001	Inactive:
C-ID:

Certificate/Major Applicable: Major Applicable Course

COURSE CONTENT

Outcomes and Objectives:
At the conclusion of this course, the student should be able to:

Upon successful completion of the course, students will be able to:

1.   Properly structure mathematical algorithms and proofs.

2.   Prove theorems by induction.

3.   Apply algorithms from elementary number theory.

4.   Use set theory to solve mathematical problems.  

5.   Apply combinatorics to counting problems, including use of Pigeonhole

     Principle, permutations, combinations, and probability.

6.   Analyze functions, inverse functions, and finite state automata.

7.   Solve recurrence relations.

8.   Analyze the efficiency of algorithms.

9.   Recognize relations and their properties.

10. Use graph theory to develop and analyze appropriate models.

Topics and Scope

I.    Logic

     A. Logical form and equivalence

     B. Conditional statements

     C. Valid and invalid arguments

     D. Predicates

     E. Quantified statements

     F. Arguments with quantified statements

II.   Elementary Number Theory and Proofs

     A. Direct proofs

     B. Counterexamples

     C. Rational numbers

     D. Divisibility

     E. Floor and ceiling functions

     F. Proofs by contradiction

     G. Proofs by contraposition

     H. Algorithms

III.  Mathematical Induction

     A. Sequences

     B. Weak and strong induction

     C. Well ordering principle

     D. Correctness of algorithms

IV.  Combinatorics

     A. Counting

     B. Probability

     C. Possibility trees

     D. Multiplication rule

     E. Addition rule

     F. Inclusion/exclusion

     G. Permutations

     H. Combinations

     I.  Counting of multisets

V.   Set Theory

     A. Definitions

     B. Binary operations

     C. Properties

     D. Partitions

     E. Power sets

     F. Boolean algebras

VI . Functions

     A. Definition

     B. One-to-one, onto, and inverse functions

     C. Finite state automata

     D. Formal languages

     E. Composition of functions

VII. Recursion

     A. Sequences defined recursively

     B. Solving recurrence relations by iteration

     C. Solutions of second-order linear homogeneous recurrence relations

        with constant coefficients

VIII. Algorithm Efficiency

     A. Comparison of real valued functions and their graphs

     B. O-notation

     C. Calculations of efficiency

IX.  Relations

     A. Relations on sets

     B. Reflexivity

     C. Symmetry

     D. Transitivity

     E. Equivalence relations

X.   Graph Theory

     A. Definitions

     B. Paths and circuits

     C. Trees

Assignments:

1. Reading assignments (0-50 pages per week).

2. Homework assignments (15-30) consisting of 5-35 problems from required text(s) or supplementary

   materials chosen by the instructor.

3. Exams (2-6) including final exam, and quizzes (0-8).

4. Projects (0-2): research papers on a specific topic (5-10 pages) or presentations given as posters or short talks.  Papers and presentations must be related to topics taught in the course.

Methods of Evaluation/Basis of Grade.

Writing: Assessment tools that demonstrate writing skill and/or require students to select, organize and explain ideas in writing.		Writing 0 - 0%
None
This is a degree applicable course but assessment tools based on writing are not included because problem solving assessments are more appropriate for this course.
Problem solving: Assessment tools, other than exams, that demonstrate competence in computational or non-computational problem solving skills.		Problem Solving 5 - 20%
Homework problems
Skill Demonstrations: All skill-based and physical demonstrations used for assessment purposes including skill performance exams.		Skill Demonstrations 0 - 0%
None
Exams: All forms of formal testing, other than skill performance exams.		Exams 70 - 95%
Problem solving exams, objective exams and quizzes
Other: Includes any assessment tools that do not logically fit into the above categories.		Other Category 0 - 10%
Projects

Representative Textbooks and Materials:

Discrete Mathematics With Applications (4th ed.).  Epp, Susanna S.

Brooks/Cole Cengage Learning:  2011.

Discrete Mathematics (7th ed.).  Johnsonbaugh, Richard.  Prentice Hall:

2009.

Print PDF