powered by
Center for Curriculum and Transfer Articulation
Discrete Mathematical Structures
Course: MAT227

First Term: 2020 Spring
 Lecture   3.0 Credit(s)   3.0 Period(s)   3.0 Load  
Subject Type: Academic
Load Formula: S - Standard Load


Description: Course emphasizes discrete mathematics connections to computer science by exposing students to foundational concepts of set theory, logic, counting, induction, proof techniques, graph theory, and algorithms.




MCCCD Official Course Competencies
1. Establish the validity of logical propositions. (I)
2. Compare the cardinality of given sets. (I)
3. Study the correctness of a proof (I)
4. Classify a proof. (I)
5. Solve a recurrence relation. (II)
6. Identify the properties of a relation. (II)
7. Create proofs using relations, order relations, and equivalence relations. (II)
8. Calculate permutations and combinations of sets. (III)
9. Calculate the empirical probability of an event. (III)
10. Solve problems involving modular arithmetic. (IV)
11. Identify the properties of a graph. (V)
12. Determine paths, cycles, and connectivity given a graph. (V)
13. Represent a graph with its incidence matrix. (V)
14. Use Big-O notation to study the growth of a given function. (VI)
MCCCD Official Course Competencies must be coordinated with the content outline so that each major point in the outline serves one or more competencies. MCCCD faculty retains authority in determining the pedagogical approach, methodology, content sequencing, and assessment metrics for student work. Please see individual course syllabi for additional information, including specific course requirements.
 
MCCCD Official Course Outline
I. Logic
   A. Sets
      1. Notation and representation
      2. Operations
      3. Cardinality
   B. Logic
      1. Propositional logic
      2. Predicate logic
      3. Logical equivalence
   C. Proofs
      1. Direct proofs
      2. Proof by contraposition
      3. Proof by contradiction
      4. Proof by counterexample
   D. Induction
      1. Proof by induction
      2. Proof by strong induction
II. Relations
   A. Functions
      1. Domain and codomain
      2. Injections, surjections, and bijections
      3. Sequences
   B. Relations
      1. Partial total orders
      2. Equivalence relations
      3. Properties of relations
   C. Recurrence relations
      1. Definition and modeling applications
      2. Solution of recurrence relation
      3. Polynomial fitting
III. Counting
   A. Counting principles
      1. Additive principle
      2. Multiplicative principle
      3. Principle of inclusion exclusion
   B. Counting arrangements
      1. Permutations
      2. Combinations
      3. Binomial coefficient
   C. Discrete probability
      1. Empirical definition
      2. Independence and conditional probability
      3. Random variables and expected value
IV. Introduction to number theory
   A. Modular arithmetic
      1. Divisibility
      2. Division algorithm
      3. Congruence
   B. Integer representations
      1. Primes
      2. Change of base
      3. Application to cryptography
V. Graphs
   A. Graphs basics
      1. Edges, vertices, and degrees
      2. Adjacency and incidence
      3. Simple, connected, and directed graphs
   B. Paths
      1. Euler paths and circuits
      2. Hamiltonian paths and cycles
   C. Trees
      1. Terminology
      2. Spanning
      3. Optimization
VI. Algorithms
   A. Intro to algorithms
      1. Definitions
      2. Operations counting
   B. Analysis of algorithms
      1. Growth function
      2. Big O notation
 
MCCCD Governing Board Approval Date: May 28, 2019

All information published is subject to change without notice. Every effort has been made to ensure the accuracy of information presented, but based on the dynamic nature of the curricular process, course and program information is subject to change in order to reflect the most current information available.