SRJC Course Outlines

10/11/2024 8:00:17 AMMATH 4 Course Outline as of Fall 2021

Changed Course
CATALOG INFORMATION

Discipline and Nbr:  MATH 4Title:  DISCRETE MATHEMATICS  
Full Title:  Discrete Mathematics
Last Reviewed:9/14/2020

UnitsCourse Hours per Week Nbr of WeeksCourse Hours Total
Maximum4.00Lecture Scheduled4.0017.5 max.Lecture Scheduled70.00
Minimum4.00Lab Scheduled06 min.Lab Scheduled0
 Contact DHR0 Contact DHR0
 Contact Total4.00 Contact Total70.00
 
 Non-contact DHR0 Non-contact DHR Total0

 Total Out of Class Hours:  140.00Total 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:
Untitled document
Introductory 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 AB705 placement into Math Tier 1 or higher


Recommended Preparation:
Course Completion of MATH 1A

Limits on Enrollment:

Schedule of Classes Information
Description: Untitled document
Introductory 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 AB705 placement into Math Tier 1 or higher
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:
 B4Math/Quantitative ReasoningFall 2001
 
IGETC:Transfer Area Effective:Inactive:
 2AMathematical Concepts & Quantitative ReasoningFall 2001
 
CSU Transfer:TransferableEffective:Fall 2001Inactive:
 
UC Transfer:TransferableEffective:Fall 2001Inactive:
 
C-ID:

Certificate/Major Applicable: Major Applicable Course



COURSE CONTENT

Student Learning Outcomes:
At the conclusion of this course, the student should be able to:
Untitled document
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: Untitled document
At the conclusion of this course, the student should 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 and Boolean algebra to construct and write 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 and programs.
8.   Analyze the efficiency of algorithms.
9.   Recognize relations and their properties.
10. Use graph theory and matrix representations to develop appropriate models.
11. Apply matrices to analyze graphs and trees.

Topics and Scope
Untitled document
I. Logic
    A. Logical form, tautology, and symbolic representation in propositional logic
    B. Equivalence and minimization of Boolean circuits
    C. Valid and invalid arguments
    D. Quantified statements and predicate logic
    E. Proof strategies with number theory
    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
    J. Pigeonhole Principle
IV. Set Theory
    A. Definitions
    B. Binary operations
    C. Properties
    D. Partitions
    E. Power sets
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 with number theory and modular arithmetic
    F. Relational databases
    G. Matrix representation
IX. Graph Theory
    A. Paths, Euler and Hamiltonian paths and circuits
    B. Matrix and visual representations of graphs
    C. Representations of trees, diagrams
    D. Trees and its applications: decision trees, Huffman codes
    E. Graph algorithms, including directed graphs, binary relations, shortest path and minimal spanning tree, and Warshall's algorithm (minimal weighted paths)
    F. Tree traversal algorithms      
    G. Articulation points (cut vertices) and computer networks
X. Boolean Algebra Structure
    A. Logic networks
    B. Minimization
XI. Formal Languages and Automata
    A. Languages and regular expressions
    B. Finite-state automata
    C. Modeling arithmetic, computation, and languages including algebraic structures, formal languages

Assignments:
Untitled document
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. Quiz(zes) (0-8)
4. Exams (2-7)
5. Final Exam
6. Project(s) (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 assignments
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%
Quiz(zes), exams, final exam
Other: Includes any assessment tools that do not logically fit into the above categories.Other Category
0 - 10%
Project(s)


Representative Textbooks and Materials:
Untitled document
Discrete Mathematics. 8th ed. Johnsonbaugh, Richard. Pearson. 2017
Discrete Mathematics and Its Applications. 7th ed. Rosen, Kenneth. McGraw-Hill. 2011 (classic)
Discrete Mathematics. Irani, Sandy. zyBooks. online

Print PDF