# SRJC Course Outlines

12/3/2021 8:36:35 PM | MATH 4 Course Outline as of Summer 2019
| 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 |

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 (MATH); OR Course Completion of MATH 25 and MATH 58; OR appropriate placement based on AB 705 mandates

**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 (MATH); OR Course Completion of MATH 25 and MATH 58; OR appropriate placement based on AB 705 mandates

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__**Student Learning Outcomes:**

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

1. Recognize valid forms of arguments using predicate logic.

2. Construct mathematical proofs of propositions from elementary number theory.

3. Apply combinatorics and set theory to counting problems.

4. Analyze formal languages using finite-state automata.

**Objectives:**

During this course, students will:

1. Properly structure mathematical algorithms and proofs.

2. Prove theorems by induction.

3. Apply algorithms from elementary number theory.

4. Use set theory and Boolean algebra to construct proofs and solve 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 and use recursion to analyze algorithms.

8. Analyze the efficiency of algorithms.

9. Recognize relations and their properties.

10. Use graph theory and matrix representations to develop appropriate models.

**Topics and Scope**

I. Logic

A. Logical form, tautology, and symbolic representation in prepositional logic

B. Equivalence and minimization of Boolean circuits

C. Valid and invalid arguments

D. Quantified statements and predicate logic

E. Proof strategies

F. Logic programming

II. Mathematical Induction

A. Sequences

B. Weak and strong induction

C. Well-ordering principle

D. Correctness of algorithms

III. Combinatorics

A. Counting

B. Probability

C. Possibility trees

D. Multiplication rule

E. Addition rule

F. Inclusion/exclusion

G. Permutations

H. Combinations and Binomial Theorem

I. Counting of multisets

IV. Set Theory

A. Definitions

B. Binary operations

C. Properties

D. Partitions

E. Power sets

F. Boolean algebra

V. Functions

A. Definition

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

C. Composition of functions

VI. Recursion

A. Sequences defined recursively

B. Solving recurrence relations by iteration

C. Solutions of second-order linear homogeneous recurrence relations with constant

coefficients

VII. Algorithm Efficiency

A. Comparison of real valued functions and their graphs

B. Big O notation

C. Calculations of efficiency

VIII. Relations

A. Relations on sets

B. Reflexivity

C. Symmetry

D. Transitivity

E. Equivalence relations and modular arithmetic

F. Relational Databases

IX. Graph Theory

A. Paths, Euler and Hamiltonian circuits

B. Matrix representations of graphs

C. Trees and its applications: decision trees, Huffman codes

D. Graph algorithms: minimal spanning tree, Warshall's algorithm

X. Formal Languages and Automata

A. Languages and regular expressions

B. Finite-state automata

**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% |
||

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. 8th ed. Johnsonbaugh, Richard. Pearson. 2017

Discrete Mathematics With Applications. 4th ed. Epp, Susanna. Cengage Learning. 2011 (classic)

Discrete Mathematics and Its Applications. 7th ed. Rosen, Kenneth. McGraw-Hill. 2011 (classic)

Discrete Mathematics. Irani, Sandy. zyBooks. online