# SRJC Course Outlines

 4/1/2023 10:33:27 PM MATH 4 Course Outline as of Fall 2006 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 17.5 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
Repeatability:  00 - Two Repeats if Grade was D, F, NC, or NP
Also Listed As:
Formerly:

Catalog Description:
Untitled document
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 (V2)

Recommended Preparation:
Math 1A.

Limits on Enrollment:

Schedule of Classes Information
Description: Untitled document
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:Completion of MATH 27 or higher (V2)
Recommended: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: BMC Communication and Analytical ThinkingMath 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:
Untitled document
Upon successful completion of the course, students will be able to:
1.  Properly structure mathematical algorithms and proofs.
2.  Do proofs by induction.
3.  Understand and apply algorithms from elementary number theory.
4.  Be able to apply set theory.
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
Untitled document
Instructional methodology may include, but is not limited to:  lecture,
demonstrations, oral recitation, discussion, supervised practice,
independent study, outside project or other assignments.
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
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
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, 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:
Untitled document
1. Daily reading outside of class (approximately 0-50 pages per week).
2. Problem set assignments from required text(s) or supplementary
materials chosen by the instructor.
3. Exams and quizzes.
4. Projects.